Get Fast-growing Hierarchy essential facts below. View Videos or join the Fast-growing Hierarchy discussion. Add Fast-growing Hierarchy to your PopFlock.com topic list for future reference or share this resource on social media.
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 increasing 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 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 (see Analytical hierarchy).
A fully specified extension beyond the recursive ordinals is thought to be unlikely; e.g., Pr?mel et al. (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? (? ?0) obtained by defining the fundamental sequences as follows [Gallier 1991][Pr?mel, et al., 1991]:
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],
if ? = ?0, take ? = 0 and ?[n + 1] = ??[n] as in [Gallier 1991]; alternatively, take the same sequence except starting with ? = 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).
In the Wainer hierarchy, f? is dominated by f? if ? < ?. (For any two functions f, g: N -> N, f is said to dominateg 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 ? < ?0 is computable and provably total in Peano arithmetic.
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 (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 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  n - 1
f1(n) = f0n(n) = n + n = 2n = 2  n
f2(n) = f1n(n) = 2n · n > 2n = 2  n for n >= 2
fk+1(n) = fkn(n) > (2 [k + 1])nn >= 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 nthAckermann number.
f?+1(64) > f?64(6) > 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.
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.