Fast-growing hierarchy
In
Definition
Let μ be a
- if α is a limit ordinal.
Here fαn(n) = fα(fα(...(fα(n))...)) denotes the nth iterate of fα applied to n, and α[n] denotes the nth 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 fn, whereas the latter is an indexed family of sets of functions . (See Points of Interest below.)
Generalizing the above definition even further, a fast iteration hierarchy is obtained by taking f0 to be any non-decreasing function g: N → N.
For limit ordinals not greater than
A fully specified extension beyond the
The Wainer hierarchy
The Wainer hierarchy is the particular fast-growing hierarchy of functions fα (α ≤
For limit ordinals λ <
- if λ = ωα1 + ... + ωαk−1 + ωαk for α1 ≥ ... ≥ αk−1 ≥ αk, then λ[n] = ωα1 + ... + ωαk−1 + ωαk[n],
- if λ = ωα+1, then λ[n] = ωαn,
- if λ = ωα for a limit ordinal α, then λ[n] = ωα[n],
and
- if λ = ε0, 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 α < ε0 (thus excluding fε0 from the hierarchy).
To continue beyond ε0, 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.)[clarification needed]
- 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 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 fn-1k evaluated at the maximum argument.
- In the Wainer hierarchy, every fα with α < Peano arithmetic.
- Every computable function that is provably total in Peano arithmetic is dominated by some fα with α < ε0in the Wainer hierarchy. Hence fε0 in the Wainer hierarchy is not provably total in Peano arithmetic.
- The ε0, and hence is not provably total in Peano Arithmetic.
- In the Wainer hierarchy, if α < β < ε0, 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 α < ε0. The Hardy hierarchy "catches up" to the Wainer hierarchy at α = ε0, 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)
- f0(n) = n + 1 = 2[1]n − 1
- f1(n) = f0n(n) = n + n = 2n = 2[2]n
- f2(n) = f1n(n) = 2n · n > 2n = 2[3]n for n ≥ 2
- fk+1(n) = fkn(n) > (2[k + 1])n n ≥ 2[k + 2]n for n ≥ 2, k < ω.
Beyond the finite levels are the functions of the Wainer hierarchy (ω ≤ α ≤ ε0):
- fω(n) = fn(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(n) ≥ fn[n + 2]n(n) for all n > 0, where n[n + 2]n is the nth Ackermann number.
- fω+1(64) = fω64(64) > Graham's number (= g64 in the sequence defined by g0 = 4, gk+1 = 3[gk + 2]3). This follows by noting fω(n) > 2[n + 1]n > 3[n]3 + 2, and hence fω(gk + 2) > gk+1 + 2.
- fε0(n) is the first function in the Wainer hierarchy that dominates the Goodstein function.
References
- S2CID 10454755.
Sources
- 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, S2CID 1390729
- . (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
- 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 .
- 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 .
- Wainer, S.S (1989). "Slow Growing Versus Fast Growing". S2CID 19848720.