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:

• $g_{0}(n)=0$
• $g_{k+1}(n)=g_{k}(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 α < ε₀.

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₃ 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.

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. However for the assignment of fundamental sequences found in the first match up occurs at the level ε₀. 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.

The slow-growing hierarchy depends extremely sensitively on the choice of the underlying fundamental sequences.

Relation to term rewriting

Cichon provided an interesting connection between the slow-growing hierarchy and derivation length for term rewriting.

References

• Gallier, Jean H. (1991). "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory". Ann. Pure Appl. Logic. 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E. MR 1129778Template:Inconsistent citations{{cite journal}}: CS1 maint: postscript (link) 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".)