Löb–Wainer 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 , 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 α < ε₀. 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_(n) = f_\alpha^n(n)$
*$f_\alpha(n) = f_(n)$ 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 $\mathcal^n$. (See Points of Interest below.)

Generalizing the above definition even further, a fast iteration hierarchy is obtained by taking ''f''₀ to be any non-decreasing function g: N → N.

For limit ordinals not greater than ε₀, there is a straightforward natural definition of the fundamental sequences (see the Wainer hierarchy below), but beyond ε₀ the definition is much more complicated. However, this is possible well beyond the Feferman–Schütte ordinal, Γ₀, 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.'' 991p. 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''_α (α ≤ ε₀) obtained by defining the fundamental sequences as follows allier 1991Prӧmel, et al., 1991]:

For limit ordinals λ < ε₀, written in Cantor normal form,

* if λ = ω^α₁ + ... + ω^α_k−1 + ω^α_k for α₁ ≥ ... ≥ α_k−1 ≥ α_k, then λ 'n''= ω^α₁ + ... + ω^α_k−1 + ω^α_k 'n''
* if λ = ω^α+1, then λ 'n''= ω^α''n'',
* if λ = ω^α for a limit ordinal α, then λ 'n''= ω^{α 'n''/sup>,}

and

* if λ = ε₀, take λ = 0 and λ 'n'' + 1= ω^{λ 'n''/sup> as in allier 1991 alternatively, take the same sequence except starting with λ = 1 as in rӧ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 α < ε₀ (thus excluding ''f''_ε0 from the hierarchy).

To continue beyond ε₀, 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^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 α < ε₀ is computable and provably total in Peano arithmetic.
* Every computable function that is provably total in Peano arithmetic is dominated by some ''f''_α with α < ε₀ 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 α < ε₀, and hence is not provably total in Peano Arithmetic.
* In the Wainer hierarchy, if α < β < ε₀, 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 α < ε₀. The Hardy hierarchy "catches up" to the Wainer hierarchy at α = ε₀, 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)
* 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''₀(''n'') = ''n'' + 1 = 2 'n'' − 1
* ''f''₁(''n'') = ''f''₀^''n''(''n'') = ''n'' + ''n'' = 2''n'' = 2 'n''
* ''f''₂(''n'') = ''f''₁^''n''(''n'') = 2^''n'' · ''n'' > 2^''n'' = 2 '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 (ω ≤ α ≤ ε₀):

* ''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) > Graham's number (= ''g''₆₄ in the sequence defined by ''g''₀ = 4, ''g''_''k''+1 = 3 'g''_''k'' + 2). This follows by noting ''f''_ω(''n'') > 2 'n'' + 1'n'' > 3 'n'' + 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

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.
*
* PDF

(In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
*
* 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 , Part 2 , Corrections .
* 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 .
*

{{DEFAULTSORT:Fast-Growing Hierarchy
Computability theory
Proof theory
Hierarchy of functions
Large numbers