# 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:^{[1]}

- [math]\displaystyle{ g_0(n) = 0 }[/math]
- [math]\displaystyle{ g_{\alpha+1}(n) = g_\alpha(n) + 1 }[/math]
- [math]\displaystyle{ g_\alpha(n) = g_{\alpha[n]}(n) }[/math] 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 α < ε_{0}.

## Relation to fast-growing hierarchy

The slow-growing hierarchy grows much more slowly than the fast-growing hierarchy. Even *g*_{ε0} is only equivalent to *f*_{3} and *g*_{α} only attains the growth of *f*_{ε0} (the first function that Peano arithmetic cannot prove total in the hierarchy) when α is the Bachmann–Howard ordinal.^{[2]}^{[3]}^{[4]}

However, Girard proved that the slow-growing hierarchy eventually *catches up* with the fast-growing one.^{[2]} 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.^{[5]} However, for the assignment of fundamental sequences found in ^{[3]} the first match up occurs at the level ε_{0}.^{[6]} For Buchholz style tree ordinals it could be shown that the first match up even occurs at [math]\displaystyle{ \omega^2 }[/math].

Extensions of the result proved^{[5]} to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated [math]\displaystyle{ \Pi^1_1 }[/math]-comprehension where the slow- and fast-growing hierarchy match up.^{[7]}

The slow-growing hierarchy depends extremely sensitively on the choice of the underlying fundamental sequences.^{[6]}^{[8]}^{[9]}

## Relation to term rewriting

Cichon provided an interesting connection between the slow-growing hierarchy and derivation length for term rewriting.^{[3]}^{[non-primary source needed]}

## References

- Gallier, Jean H. (1991). "What's so special about Kruskal's theorem and the ordinal Γ
_{0}? A survey of some results in proof theory".*Ann. Pure Appl. Logic***53**(3): 199–260. doi:10.1016/0168-0072(91)90022-E. http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387. PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)

## Notes

- ↑ J. Gallier, What's so special about Kruskal's theorem and the ordinal Γ
_{0}? A survey of some results in proof theory (2012, p.63). Accessed 8 May 2023. - ↑
^{2.0}^{2.1}Girard, Jean-Yves (1981). "Π^{1}_{2}-logic. I. Dilators".*Annals of Mathematical Logic***21**(2): 75–219. doi:10.1016/0003-4843(81)90016-4. ISSN 0003-4843. - ↑
^{3.0}^{3.1}^{3.2}Cichon (1992). "Termination Proofs and Complexity Characterisations".*Proof Theory*. Cambridge University Press. pp. 173–193. - ↑ Cichon, E. A.; Wainer, S. S. (1983). "The slow-growing and the Grzegorczyk hierarchies".
*The Journal of Symbolic Logic***48**(2): 399–408. doi:10.2307/2273557. ISSN 0022-4812. - ↑
^{5.0}^{5.1}Wainer, S. S. (1989). "Slow Growing Versus Fast Growing".*The Journal of Symbolic Logic***54**(2): 608–614. doi:10.2307/2274873. - ↑
^{6.0}^{6.1}Weiermann, A (1997). "Sometimes slow growing is fast growing".*Annals of Pure and Applied Logic***90**(1–3): 91–99. doi:10.1016/S0168-0072(97)00033-X. - ↑ Weiermann, A. (1995). "Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones".
*Archive for Mathematical Logic***34**(5): 313–330. doi:10.1007/BF01387511. - ↑ Weiermann, A. (1999), "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.
- ↑ Weiermann, Andreas (2001). "Γ
_{0}May be Minimal Subrecursively Inaccessible".*Mathematical Logic Quarterly***47**(3): 397–408. doi:10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y.

Original source: https://en.wikipedia.org/wiki/Slow-growing hierarchy.
Read more |