# Fast-growing hierarchy

__: Ordinal-indexed family of rapidly increasing functions: ℕ→ℕ__

**Short description**In computability theory, computational complexity theory and proof theory, a **fast-growing hierarchy** (also called an **extended Grzegorczyk hierarchy**, or a **Schwichtenberg-Wainer hierarchy**)^{[1]} 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 α < ε_{0}. 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 to every limit ordinal α < μ there is assigned a fundamental sequence (a strictly increasing sequence of ordinals whose supremum is α). A **fast-growing hierarchy** of functions *f*_{α}: **N** → **N**, for α < μ, is then defined as follows:

- [math]\displaystyle{ f_0(n) = n + 1, }[/math]
- [math]\displaystyle{ f_{\alpha+1}(n) = f_\alpha^n(n), }[/math]
- [math]\displaystyle{ f_\alpha(n) = f_{\alpha[n]}(n) }[/math] if α is a limit ordinal.

Here *f*_{α}^{n}(*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 [math]\displaystyle{ \mathcal{E}^n }[/math]. (See Points of Interest below.)

Generalizing the above definition even further, a **fast iteration hierarchy** is obtained by taking *f*_{0} 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 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 [math]\displaystyle{ \Pi^1_1 }[/math]-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*_{α} (α ≤ ε_{0}) obtained by defining the fundamental sequences as follows [Gallier 1991][Prӧmel, et al., 1991]:

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]}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 [math]\displaystyle{ \mathcal{E}^n }[/math] 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 α < ε_{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 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)

*f*_{0}(*n*) =*n*+ 1 = 2[1]*n*− 1*f*_{1}(*n*) =*f*_{0}^{n}(*n*) =*n*+*n*= 2*n*= 2[2]*n**f*_{2}(*n*) =*f*_{1}^{n}(*n*) = 2^{n}·*n*> 2^{n}= 2[3]*n*for*n*≥ 2*f*_{k+1}(*n*) =*f*_{k}^{n}(*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*) =*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}(*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*_{ω}^{64}(5) > Graham's number (=*g*_{64}in the sequence defined by*g*_{0}= 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.

## References

- ↑ L. D. Beklemishev, "Proof-theoretic analysis by iterated reflection" (1999). Archive of Mathematical Logic, vol. 42

## 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, doi:10.2307/2273557, ISSN 0022-4812 - Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ
_{0}? A survey of some results in proof theory",*Ann. Pure Appl. Logic***53**(3): 199–260, doi:10.1016/0168-0072(91)90022-E PDF: [1]. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".) - Girard, Jean-Yves (1981), "Π
^{1}_{2}-logic. I. Dilators",*Annals of Mathematical Logic***21**(2): 75–219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843 - 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. doi:10.2307/2274873.

Original source: https://en.wikipedia.org/wiki/Fast-growing hierarchy.
Read more |