# Fast-growing hierarchy

In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy, or a Schwichtenberg-Wainer hierarchy) 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:
* $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., α < ω), 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 ${\mathcal {E}}^{n}$. (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 $\Pi _{1}^{1}$-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.)
* 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 ${\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 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 = 2n = 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 nth Ackermann number.
* f$_{ω+1}$(64) = f$_ω$$^{64}$(64) > 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.