Fast-growing hierarchy

In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk 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 α < ε₀. 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 a fundamental sequence (a strictly increasing sequence of ordinals whose supremum is a limit ordinal) is assigned to every limit ordinal less than μ. 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) = 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 {E}}^{n}$ . (See Points of Interest below.)

Generalizing the above definition even further, a fast iteration hierarchy is obtained by taking f₀ to be any increasing 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. [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_α (α ≤ ε₀) obtained by defining the fundamental sequences as follows [Gallier 1991][Prӧ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],

and

if λ = ε₀, 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 α < ε₀ (thus excluding f_ε₀ 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 {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 α < ε₀ is computable and provably total in Peano Arithmetic.
Every computable function that's provably total in Peano Arithmetic is dominated by some f_α with α < ε₀ in the Wainer hierarchy. Hence f_ε₀ 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_ε₀ 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_Γ₀ 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_ε₀ and h_ε₀ have the same growth rate, in the sense that f_ε₀(n-1) ≤ h_ε₀(n) ≤ f_ε₀(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_ε₀ 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 [1] n − 1
f₁(n) = f₀ⁿ(n) = n + n = 2n = 2 [2] n
f₂(n) = f₁ⁿ(n) = 2ⁿ · n > 2ⁿ = 2 [3] n for n ≥ 2
f_k+1(n) = f_kⁿ(n) > (2 [k + 1])ⁿ 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) ≥ 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_ω⁶⁴(6) > Graham's number (= g₆₄ in the sequence defined by g₀ = 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_ε₀(n) is the first function in the Wainer hierarchy that dominates the Goodstein function.

References

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, MR 704094
Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory", Ann. Pure Appl. Logic, 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR 1129778 PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
Girard, Jean-Yves (1981), "Π¹₂-logic. I. Dilators", Annals of Mathematical Logic, 21 (2): 75–219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, MR 656793
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, Dec. 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.

This article is issued from Wikipedia - version of the 10/8/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.