Fast-growing hierarchy
Encyclopedia
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 α < ε0. Such hierarchies provide a natural way to classify computable function
s according to rate-of-growth and computational complexity
.
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:
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 ordinal
s 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".
For limit ordinals λ < ε0, written in Cantor normal form,
and
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.
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)
Beyond the finite levels are the functions of the Wainer hierarchy (ω ≤ α ≤ ε0):
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and proof theory
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy
Grzegorczyk hierarchy
The Grzegorczyk hierarchy , named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory . Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level...
) 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 function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
s according to rate-of-growth and computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
.
Definition
Let μ be a large countable ordinalLarge countable ordinal
In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable 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:
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
Grzegorczyk hierarchy
The Grzegorczyk hierarchy , named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory . Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level...
; 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
Feferman–Schütte ordinal
In mathematics, the Feferman–Schütte ordinal Γ0 is a large countable ordinal.It is the proof theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion.It is named after Solomon Feferman and Kurt Schütte....
, up to at least the Bachmann–Howard ordinal
Bachmann–Howard ordinal
In mathematics, the Bachmann–Howard ordinal is a large countable ordinal.It is the proof theoretic ordinal of several mathematical theories, such as Kripke–Platek set theory and the system CZF of constructive set theory.It is named after William Alvin Howard and Heinz Bachmann.-Definition:The...
. Using Buchholz psi functions one can extend this definition easily to the ordinal of transfinitely iterated
-comprehension (see Analytical hierarchyAnalytical hierarchy
In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.-The analytical hierarchy of formulas:...
).
A fully specified extension beyond the recursive ordinal
Recursive ordinal
In mathematics, specifically set theory, an ordinal \alpha is said to be recursive if there is a recursive binary relation R that well-orders a subset of the natural numbers and the order type of that ordering is \alpha....
s 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 functionComputable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
.
- 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 functionPrimitive recursive functionThe primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
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 functionAckermann functionIn computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
.
- For n ≥ 3, the set
in the Grzegorczyk hierarchyGrzegorczyk hierarchyThe Grzegorczyk hierarchy , named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory . Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level...
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 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Γ0Feferman–Schütte ordinalIn mathematics, the Feferman–Schütte ordinal Γ0 is a large countable ordinal.It is the proof theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion.It is named after Solomon Feferman and Kurt Schütte....
in a fast-growing hierarchy described by Gallier (1991).
- The Wainer hierarchy of functions fα and the Hardy hierarchyHardy hierarchyIn computability theory, computational complexity theory and proof theory, the Hardy hierarchy, named after G. H. Hardy, is an ordinal-indexed family of functions hα: N → N . It is related to the fast-growing hierarchy and slow-growing 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)
and Cichon & Wainer (1983) showed that the slow-growing hierarchy
Slow-growing hierarchy
In computability theory, computational complexity theory and proof theory, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions gα: N → N...
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:- f0(n) = n + 1
- f1(n) = f0n(n) = n + n = 2n
- f2(n) = f1n(n) = 2nn > (2 ↑) n for n ≥ 2 (using Knuth up-arrow notation)
- fk+1(n) = fkn(n) > (2 ↑k-1)n n ≥ 2 ↑k 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 − 2 (n + 3) − 3 = A(n, n) for n ≥ 4, where A is the Ackermann functionAckermann functionIn computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
(of which fω is a unary version). - fω+1(n) = fωn(n) ≥ fn↑nn(n) for all n > 0, where n↑nn is the nth Ackermann number.
- fω+1(64) > fω64(6) > Graham's number (= g64 in the sequence defined by g0 = 4, gk+1 = 3 ↑gk 3). This follows by noting fω(n) > 2 ↑n - 1 n > 3 ↑n - 2 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.