In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy is an ordinal-indexed family of rapidly increasing functions fα: N → N. A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε0. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.
Here fαn = fα) denotes the nth iterate of fα applied to n, and α denotes the nthelement of the fundamental sequence assigned to the limit ordinal α. The initial part of this hierarchy, comprising the functions fα with finite index, 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. Generalizing the above definition even further, a fast iteration hierarchy is obtained by taking f0 to be any increasing function g: N → N. For limit ordinals not greater than ε0, there is a straightforward natural definition of the fundamental sequences, but beyond ε0 the definition is much more complicated. However, this is possible well beyond the Feferman–Schütte ordinal, Γ0, up to at least the Bachmann–Howard ordinal. Using Buchholz psi functions one can extend this definition easily to the ordinal of transfinitely iterated -comprehension. A fully specified extension beyond the recursive ordinals is thought to be unlikely; e.g., Prӧmel et al. 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 : For limit ordinals λ < ε0, written in Cantor normal form,
if λ = ωα1 +... + ωαk−1 + ωαk for α1 ≥... ≥ αk−1 ≥ αk, then λ = ωα1 +... + ωαk−1 + ωαk,
if λ = ωα+1, then λ = ωαn,
if λ = ωα for a limit ordinal α, then λ = ωα,
and
if λ = ε0, take λ = 0 and λ = ωλ as in ; alternatively, take the same sequence except starting with λ = 1 as in .
For n > 0, the alternative version has one additional ω in the resulting exponential tower, i.e. λ = ωω...ω with n omegas. Some authors use slightly different definitions, and some define this hierarchy only for α < ε0. 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:
In the Wainer hierarchy, fα is dominated by fβ if α < β. > g The same property holds in any fast-growing hierarchy with fundamental sequences satisfying the so-called Bachmann property.
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.
Every computable function that's provably total in Peano arithmetic is dominated by some fα with α < ε0 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 as fε0 in the Wainer hierarchy, dominating every fα for which α < ε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.
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 ≤ hε0 ≤ fε0 for all n ≥ 1.
and Cichon & Wainer 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 further showed that the slow-growing hierarchy gα attains the same growth rate as fα when α is the ordinal of the theory ID<ω of arbitrary finite iterations of an inductive definition.
Functions in fast-growing hierarchies
The functions at finite levels of any fast-growing hierarchy coincide with those of the Grzegorczyk hierarchy:
f0 = n + 1 = 2 n − 1
f1 = f0n = n + n = 2n = 2 n
f2 = f1n = 2n · n > 2n = 2 n for n ≥ 2
fk+1 = fkn > nn ≥ 2 n for n ≥ 2, k < ω.
Beyond the finite levels are the functions of the Wainer hierarchy :
fω = fn > 2 n > 2 − 3 = A for n ≥ 4, where A is the Ackermann function.
fω+1 = fωn ≥ fnn for all n > 0, where nn is the nth Ackermann number.
fω+1 > fω64 > Graham's number. This follows by noting fω > 2 n > 3 3 + 2, and hence fω > gk+1 + 2.
fε0 is the first function in the Wainer hierarchy that dominates the Goodstein function.
Approximate growth rates in comparison to other googological notations
