Fast-growing hierarchy

In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy) is an ordinal-indexed family of rapidly increasing functions f_α: N → N (where N is the set of natural numbers {0, 1, ...}, and α ranges up to some large countable ordinal). A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε₀. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.

Definition

Let μ be a large countable ordinal such that a fundamental sequence (a strictly increasing sequence of ordinals whose supremum is a limit ordinal) is assigned to every limit ordinal less than μ. A fast-growing hierarchy of functions f_α: N → N, for α < μ, is then defined as follows:

• $f_{0}(n)=n+1,$
• $f_{\alpha +1}(n)=f_{\alpha }^{n}(n),$
• $f_{\alpha }(n)=f_{\alpha [n]}(n)$ if α is a limit ordinal.

Here f_αⁿ(n) = f_α(f_α(...(f_α(n))...)) denotes the n^th iterate of f_α applied to n, and α[n] denotes the n^th element of the fundamental sequence assigned to the limit ordinal α. (An alternative definition takes the number of iterations to be n+1, rather than n, in the second line above.)

The initial part of this hierarchy, comprising the functions f_α with finite index (i.e., α < ω), is often called the Grzegorczyk hierarchy because of its close relationship to the Grzegorczyk hierarchy; note, however, that the former is here an indexed family of functions f_n, whereas the latter is an indexed family of sets of functions ${\mathcal {E}}^{n}$. (See Points of Interest below.)

Generalizing the above definition even further, a fast iteration hierarchy is obtained by taking f₀ to be any increasing function g: N → N.

For limit ordinals not greater than ε₀, there is a straightforward natural definition of the fundamental sequences (see the Wainer hierarchy below), but beyond ε₀ the definition is much more complicated. However, this is possible well beyond the Feferman–Schütte ordinal, Γ₀, up to at least the Bachmann–Howard ordinal. Using Buchholz psi functions one can extend this definition easily to the ordinal of transfinitely iterated $\Pi _{1}^{1}$-comprehension (see Analytical hierarchy).

A fully specified extension beyond the recursive ordinals is thought to be unlikely; e.g., Prӧmel et al. [1991](p. 348) note that in such an attempt "there would even arise problems in ordinal notation".

The Wainer hierarchy

The Wainer hierarchy is the particular fast-growing hierarchy of functions f_α (α ≤ ε₀) obtained by defining the fundamental sequences as follows [Gallier 1991][Prӧmel, et al., 1991]:

For limit ordinals λ < ε₀, written in Cantor normal form,

• if λ = ω^α₁ + ... + ω^α_k−1 + ω^α_k for α₁ ≥ ... ≥ α_k−1 ≥ α_k, then λ[n] = ω^α₁ + ... + ω^α_k−1 + ω^α_k[n],
• if λ = ω^α+1, then λ[n] = ω^αn,
• if λ = ω^α for a limit ordinal α, then λ[n] = ω^α[n],

and

• if λ = ε₀, take λ[0] = 0 and λ[n + 1] = ω^λ[n] as in [Gallier 1991]; alternatively, take the same sequence except starting with λ[0] = 1 as in [Prӧmel, et al., 1991].
  For n > 0, the alternative version has one additional ω in the resulting exponential tower, i.e. λ[n] = ω^ω...ω with n omegas.

Some authors use slightly different definitions (e.g., ω^α+1[n] = ω^α(n+1), instead of ω^αn), and some define this hierarchy only for α < ε₀ (thus excluding f_ε0 from the hierarchy).

To continue beyond ε₀, see the Fundamental sequences for the Veblen hierarchy.

Points of interest

Following are some relevant points of interest about fast-growing hierarchies:

• Every f_α is a total function. If the fundamental sequences are computable (e.g., as in the Wainer hierarchy), then every f_α is a total computable function.
• In the Wainer hierarchy, f_α is dominated by f_β if α < β. (For any two functions f, g: N → N, f is said to dominate g if f(n) > g(n) for all sufficiently large n.) The same property holds in any fast-growing hierarchy with fundamental sequences satisfying the so-called Bachmann property. (This property holds for most natural well orderings.)
• In the Grzegorczyk hierarchy, every primitive recursive function is dominated by some f_α with α < ω. Hence, in the Wainer hierarchy, every primitive recursive function is dominated by f_ω, which is a variant of the Ackermann function.
• For n ≥ 3, the set ${\mathcal {E}}^{n}$ in the Grzegorczyk hierarchy is composed of just those total multi-argument functions which, for sufficiently large arguments, are computable within time bounded by some fixed iterate f_n-1^k evaluated at the maximum argument.
• In the Wainer hierarchy, every f_α with α < ε₀ is computable and provably total in Peano arithmetic.
• Every computable function that's provably total in Peano arithmetic is dominated by some f_α with α < ε₀ in the Wainer hierarchy. Hence f_ε0 in the Wainer hierarchy is not provably total in Peano arithmetic.
• The Goodstein function has approximately the same growth rate (i.e. each is dominated by some fixed iterate of the other) as f_ε0 in the Wainer hierarchy, dominating every f_α for which α < ε₀, and hence is not provably total in Peano Arithmetic.
• In the Wainer hierarchy, if α < β < ε₀, then f_β dominates every computable function within time and space bounded by some fixed iterate f_α^k.
• Friedman's TREE function dominates f_Γ0 in a fast-growing hierarchy described by Gallier (1991).
• The Wainer hierarchy of functions f_α and the Hardy hierarchy of functions h_α are related by f_α = h_ω^α for all α < ε₀. The Hardy hierarchy "catches up" to the Wainer hierarchy at α = ε₀, such that f_ε0 and h_ε0 have the same growth rate, in the sense that f_ε0(n-1) ≤ h_ε0(n) ≤ f_ε0(n+1) for all n ≥ 1. (Gallier 1991)
• Girard (1981) and Cichon & Wainer (1983) showed that the slow-growing hierarchy of functions g_α attains the same growth rate as the function f_ε0 in the Wainer hierarchy when α is the Bachmann–Howard ordinal. Girard (1981) further showed that the slow-growing hierarchy g_α attains the same growth rate as f_α (in a particular fast-growing hierarchy) when α is the ordinal of the theory ID_<ω of arbitrary finite iterations of an inductive definition. (Wainer 1989)

Functions in fast-growing hierarchies

The functions at finite levels (α < ω) of any fast-growing hierarchy coincide with those of the Grzegorczyk hierarchy: (using hyperoperation)

• f₀(n) = n + 1 = 2 [1] n − 1
• f₁(n) = f₀ⁿ(n) = n + n = 2n = 2 [2] n
• f₂(n) = f₁ⁿ(n) = 2ⁿ · n > 2ⁿ = 2 [3] n for n ≥ 2
• f_k+1(n) = f_kⁿ(n) > (2 [k + 1])ⁿ n ≥ 2 [k + 2] n for n ≥ 2, k < ω.

Beyond the finite levels are the functions of the Wainer hierarchy (ω ≤ α ≤ ε₀):

• f_ω(n) = f_n(n) > 2 [n + 1] n > 2 [n] (n + 3) − 3 = A(n, n) for n ≥ 4, where A is the Ackermann function (of which f_ω is a unary version).
• f_ω+1(n) = f_ωⁿ(n) ≥ f_{n [n + 2] n}(n) for all n > 0, where n [n + 2] n is the n^th Ackermann number.
• f_ω+1(64) > f_ω⁶⁴(6) > Graham's number (= g₆₄ in the sequence defined by g₀ = 4, g_k+1 = 3 [g_k + 2] 3). This follows by noting f_ω(n) > 2 [n + 1] n > 3 [n] 3 + 2, and hence f_ω(g_k + 2) > g_k+1 + 2.
• f_ε0(n) is the first function in the Wainer hierarchy that dominates the Goodstein function.

Approximate growth rates in comparison to other googological notations

• $f_{0}(n)=n+1,$
• $f_{1}(n)=2n,$
• $f_{2}(n)=2^{n},$
• $f_{3}(n)>2{\uparrow \uparrow }n$ (see Knuth's up-arrow notation)
• $f_{4}(n)>2{\uparrow \uparrow \uparrow }n$
• $f_{m}(n)>2{\uparrow ^{m-1}}n$
• $f_{\omega }(n)>2{\uparrow ^{n-1}}n=\{n,n,n\}$ (see Bird's Array Notation)
• $f_{\omega +1}(n)=\{n,n,1,2\}$
• $f_{\omega +2}(n)=\{n,n,2,2\}$
• $f_{\omega +m}(n)=\{n,n,m,2\}$
• $f_{\omega 2}(n)=\{n,n,n,2\}$
• $f_{\omega 2+1}(n)=\{n,n,1,3\}$
• $f_{\omega 3}(n)=\{n,n,n,3\}$
• $f_{\omega {m}}(n)=\{n,n,n,m\}$
• $f_{\omega {m+k}}(n)=\{n,n,k,m+1\}$
• $f_{\omega ^{2}}(n)=\{n,n,n,n\}$
• $f_{\omega ^{3}}(n)=\{n,n,n,n,n\}$
• $f_{\omega ^{m}}(n)=\{n,n,n,...,n\}$ (m entries)
• $f_{\omega ^{\omega }}(n)=\{n,n,n,...,n\}$ (n entries) $=\{n,n[2]2\}$
• $f_{\omega ^{\omega +1}}(n)=\{n,n[2]1,2\}$
• $f_{\omega ^{\omega +2}}(n)=\{n,n[2]1,1,2\}$
• $f_{\omega ^{\omega 2}}(n)=\{n,n[2]1[2]2\}$
• $f_{\omega ^{\omega 2+1}}(n)=\{n,n[2]1[2]1,2\}$
• $f_{\omega ^{\omega 3}}(n)=\{n,n[2]1[2]1[2]2\}$
• $f_{\omega ^{\omega ^{2}}}(n)=\{n,n[3]2\}$
• $f_{\omega ^{\omega ^{3}}}(n)=\{n,n[4]2\}$
• $f_{\omega ^{\omega ^{\omega }}}(n)=\{n,n[1,2]2\}$
• $f_{\omega ^{\omega ^{\omega ^{2}}}}(n)=\{n,n[1,1,2]2\}$
• $f_{\omega ^{\omega ^{\omega ^{\omega }}}}(n)=\{n,n[1[2]2]2\}$
• $f_{\epsilon _{0}}(n)=\{n,n[1{\backslash }2]2\}$
• $f_{\omega ^{\epsilon _{0}+1}}(n)=\{n,n[1[1{\backslash }2]2{\backslash }2]2\}$
• $f_{\omega ^{\omega ^{\epsilon _{0}+1}}}(n)=\{n,n[1[1[1{\backslash }2]2{\backslash }2]2{\backslash }2]2\}$
• $f_{\epsilon _{1}}(n)=\{n,n[1{\backslash }3]2\}$
• $f_{\epsilon _{2}}(n)=\{n,n[1{\backslash }4]2\}$
• $f_{\epsilon _{\omega }}(n)=\{n,n[1{\backslash }1,2]2\}$
• $f_{\epsilon _{\omega ^{\omega }}}(n)=\{n,n[1{\backslash }1[2]2]2\}$
• $f_{\epsilon _{\epsilon _{0}}}(n)=\{n,n[1{\backslash }1[1{\backslash }2]2]2\}$
• $f_{\epsilon _{\epsilon _{\epsilon _{0}}}}(n)=\{n,n[1{\backslash }1[1{\backslash }1[1{\backslash }2]2]2]2\}$
• $f_{\zeta _{0}}(n)=\{n,n[1{\backslash }1{\backslash }2]2\}$
• $f_{\epsilon _{\zeta _{0}+1}}(n)=\{n,n[1{\backslash }2{\backslash }2]2\}$

• $f_{\epsilon _{\zeta _{0}+\omega }}(n)=\{n,n[1{\backslash }1,2{\backslash }2]2\}$

• $f_{\epsilon _{\zeta _{0}+\{\epsilon _{0}\}}}(n)=\{n,n[1{\backslash }1{[1{\backslash }2]}2{\backslash }2]2\}$
• $f_{\zeta _{1}}(n)=\{n,n[1{\backslash }1{\backslash }3]2\}$
• $f_{\zeta _{\omega }}(n)=\{n,n[1{\backslash }1{\backslash }1,2]2\}$
• $f_{\zeta _{\epsilon _{0}}}(n)=\{n,n[1{\backslash }1{\backslash }1[1{\backslash }2]2]2\}$
• $f_{\zeta _{\zeta _{0}}}(n)=\{n,n[1{\backslash }1{\backslash }1[1{\backslash }1{\backslash }2]2]2\}$
• $f_{\eta _{0}}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2]2\}$
• $f_{\varphi (5,0)}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }1{\backslash }2]2\}$
• $f_{\varphi (6,0)}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }1{\backslash }1{\backslash }2]2\}$
• $f_{\varphi (\omega ,0)}(n)=\{n,n[1[2{\neg }2]2]2\}$
• $f_{\epsilon _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }2[2{\neg }2]2]2\}$
• $f_{\zeta _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }1{\backslash }2[2{\neg }2]2]2\}$
• $f_{\eta _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2[2{\neg }2]2]2\}$
• $f_{\varphi (5,{\varphi (\omega ,0)+1})}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }1{\backslash }2[2{\neg }2]2]2\}$
• $f_{\varphi (\omega ,1)}(n)=\{n,n[1[2{\neg }2]3]2\}$
• $f_{\varphi (\omega ,2)}(n)=\{n,n[1[2{\neg }2]4]2\}$
• $f_{\varphi (\omega ,\omega )}(n)=\{n,n[1[2{\neg }2]1,2]2\}$
• $f_{\varphi (\omega ,\epsilon _{0})}(n)=\{n,n[1[2{\neg }2]1[1{\backslash }2]2]2\}$
• $f_{\varphi (\omega ,\zeta _{0})}(n)=\{n,n[1[2{\neg }2]1[1{\backslash }1{\backslash }2]2]2\}$
• $f_{\varphi (\omega ,\varphi (\omega ,0))}(n)=\{n,n[1[2{\neg }2]1[1[2{\neg }2]2]2]2\}$
• $f_{\varphi (\omega ,\varphi (\omega ,\varphi (\omega ,0)))}(n)=\{n,n[1[2{\neg }2]1[1[2{\neg }2]1[1[2{\neg }2]2]2]2]2\}$
• $f_{\varphi (\omega +1,0)}(n)=\{n,n[1[2{\neg }2]1{\backslash }2]2\}$
• $f_{\varphi (\omega +2,0)}(n)=\{n,n[1[2{\neg }2]1{\backslash }1{\backslash }2]2\}$
• $f_{\varphi (\omega 2,0)}(n)=\{n,n[1[2{\neg }2]1[2{\neg }2]2]2\}$
• $f_{\varphi (\omega ^{2},0)}(n)=\{n,n[1[3{\neg }2]2]2\}$
• $f_{\varphi (\omega ^{3},0)}(n)=\{n,n[1[4{\neg }2]2]2\}$
• $f_{\varphi (\omega ^{\omega },0)}(n)=\{n,n[1[1,2{\neg }2]2]2\}$
• $f_{\varphi (\omega ^{\omega ^{\omega }},0)}(n)=\{n,n[1[1[2]2{\neg }2]2]2\}$
• $f_{\varphi ({\epsilon _{0}},0)}(n)=\{n,n[1[1[1{\backslash }2]2{\neg }2]2]2\}$
• $f_{\Gamma _{0}}(n)=\{n,n[1[1{\backslash }2{\neg }2]2]2\}$
• $f_{\varphi (1,0,0,0)}(n)$
• $f_{\varphi (1,0,0,0,0)}(n)$
• $f_{\vartheta (\Omega ^{\omega })}(n)=\{n,n[1[1{\backslash }1,2{\neg }2]2]2\}$
• $f_{\vartheta (\Omega ^{\Omega })}(n)=\{n,n[1[1{\backslash }1{\backslash }2{\neg }2]2]2\}$

References

• Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
• 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, MR 0704094
• 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 1129778 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".)
• Girard, Jean-Yves (1981), "Π¹₂-logic. I. Dilators", Annals of Mathematical Logic, 21 (2): 75–219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, MR 0656793
• Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
• Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, December 1991 doi:10.1016/0012-365X(91)90346-4.
• Wainer, S.S (1989). "Slow Growing Versus Fast Growing". Journal of Symbolic Logic. 54 (2): 608–614. JSTOR 2274873.