Fast-growing hierarchy

Let μ be a large countable ordinal such that to every limit ordinal α α: N → N, for α 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(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., α 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 f0 to be any non-decreasing function g: N → N. For limit ordinals not greater than ε0, there is a straightforward natural definition of the fundamental sequences (see the Wainer hierarchy below), but beyond ε0 the definition is 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 to the ordinal of transfinitely iterated \Pi^1_1-comprehension (see Analytical hierarchy). A fully specified extension beyond the computable ordinals is thought to be unlikely; e.g., Prӧmel and others 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α (α ≤ ε0) 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 λ[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]; alternatively, take the same sequence except starting with λ[0] = 1. For n > 0, the alternative version has one additional ω in the resulting exponential tower, i.e. λ[n] = ωω⋰ω with n appearances of ω. 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 the fundamental sequences for the Veblen hierarchy can be used. ==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 α 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 α ω, 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 fn-1k evaluated at the maximum argument. • In the Wainer hierarchy, every fα with α 0 is computable and provably total in Peano arithmetic. • Every computable function that is 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 (i.e. each is dominated by some fixed iterate of the other) 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. • 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. • 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. Furthermore, 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. ==Functions in fast-growing hierarchies==

The functions at finite levels (α 0(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) = ''f'k'n(n) > (2[k + 1])n n ≥ 2[k + 2]n for n ≥ 2, k'' 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. ==Notes==