slow-growing hierarchy

In computability theory, computational complexity theory and proof theory, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions g_α: N → N (where N is the set of natural numbers, {0, 1, ...}). It contrasts with the fast-growing hierarchy.

Definition

Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The slow-growing hierarchy of functions g_α: N → N, for α < μ, is then defined as follows:J. Gallier, [https://www.cis.upenn.edu/~jean/kruskal.pdf What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory] (2012, p.63). Accessed 8 May 2023.

$g_0(n) = 0$
$g_{\alpha+1}(n) = g_\alpha(n) + 1$
$g_\alpha(n) = g_{\alpha[n]}(n)$ for limit ordinal α.

Here α[n] denotes the n^th element of the fundamental sequence assigned to the limit ordinal α.

The article on the Fast-growing hierarchy describes a standardized choice for fundamental sequence for all α < ε₀.

Example

$g_1(n) = 1$
$g_m(n) = m$
$g_\omega(n) = n$
$g_{\omega+m}(n) = n+m$
$g_{\omega m}(n) = mn$
$g_{\omega^m}(n) = n^m$
$g_{\omega^\omega}(n) = n^n$
$g_{\varepsilon _0}(n) = n\uparrow\uparrow n$

Relation to fast-growing hierarchy

The slow-growing hierarchy grows much more slowly than the fast-growing hierarchy. Even g_ε₀ is only equivalent to f₃ and g_α only attains the growth of f_ε₀ (the first function that Peano arithmetic cannot prove total in the hierarchy) when α is the Bachmann–Howard ordinal.{{Cite journal | last1=Girard | first1=Jean-Yves | author1-link=Jean-Yves Girard | title=Π¹₂-logic. I. Dilators | doi=10.1016/0003-4843(81)90016-4 | mr=656793 | year=1981 | journal=Annals of Mathematical Logic | issn=0003-4843 | volume=21 | issue=2 | pages=75–219 | doi-access=free }}{{cite book|last=Cichon|title=Proof Theory|year=1992|publisher=Cambridge University Press|pages=173–193|editor1=P. Aczel |editor2=H. Simmons |editor3=S. Wainer |chapter=Termination Proofs and Complexity Characterisations}}{{Cite journal | last1=Cichon | first1=E. A. | last2=Wainer | first2=S. S. | title=The slow-growing and the Grzegorczyk hierarchies | doi=10.2307/2273557 | mr=704094 | year=1983 | journal=The Journal of Symbolic Logic | issn=0022-4812 | volume=48 | issue=2 | pages=399–408 | jstor=2273557 | s2cid=1390729 }}

However, Girard proved that the slow-growing hierarchy eventually catches up with the fast-growing one. Specifically, that there exists an ordinal α such that for all integers n

:g_α(n) < f_α(n) < g_α(n + 1)

where f_α are the functions in the fast-growing hierarchy. He further showed that the first α this holds for is the ordinal of the theory ID_<ω of arbitrary finite iterations of an inductive definition.{{cite journal |jstor=2274873 |pages=608–614 |last1=Wainer |first1=S. S. |title=Slow Growing Versus Fast Growing |volume=54 |issue=2 |journal=The Journal of Symbolic Logic |year=1989 |doi=10.2307/2274873|s2cid=19848720 }} However, for the assignment of fundamental sequences found in the first match up occurs at the level ε₀.{{cite journal |doi=10.1016/S0168-0072(97)00033-X |title=Sometimes slow growing is fast growing |year=1997 |last1=Weiermann |first1=A |journal=Annals of Pure and Applied Logic |volume=90 |issue=1–3 |pages=91–99|doi-access=free }} For Buchholz style tree ordinals it could be shown that the first match up even occurs at $\omega^2$ .

Extensions of the result proved to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated $\Pi^1_1$ -comprehension where the slow- and fast-growing hierarchy match up.{{cite journal |last=Weiermann |first=A. |year=1995 |title= Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones|journal= Archive for Mathematical Logic|volume= 34 |issue=5 |pages=313–330 |doi= 10.1007/BF01387511|s2cid=34180265 }}

The slow-growing hierarchy depends extremely sensitively on the choice of the underlying fundamental sequences.Weiermann, A. (1999), [https://books.google.com/books?id=2IHm3RT2bBoC&pg=PA403 "What makes a (pointwise) subrecursive hierarchy slow growing?"] Cooper, S. Barry (ed.) et al., Sets and proofs. Invited papers from the Logic colloquium '97, European meeting of the Association for Symbolic Logic, Leeds, UK, July 6–13, 1997. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 258; 403-423.{{Cite journal |doi = 10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y|title = Γ₀ May be Minimal Subrecursively Inaccessible|journal = Mathematical Logic Quarterly |volume = 47|issue = 3|pages = 397–408|year = 2001|last1 = Weiermann|first1 = Andreas}}

References

{{Cite journal|mr=1129778|last= Gallier|first= Jean H.|authorlink= Jean Gallier |title= What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory|journal= Ann. Pure Appl. Logic|volume= 53 |year=1991|issue= 3|pages= 199–260|url=https://scholar.archive.org/work/usvtd34xj5f43n5ymwzrlroxfe|doi=10.1016/0168-0072(91)90022-E|doi-access=}} See especially "A Glimpse at Hierarchies of Fast and Slow Growing Functions", pp. 59–64 of linked version.

Notes

Category:Computability theory

Category:Proof theory

Category:Hierarchy of functions