Fast-growing Hierarchy

Get Fast-growing Hierarchy essential facts below. View Videos or join the Fast-growing Hierarchy discussion. Add Fast-growing Hierarchy to your PopFlock.com topic list for future reference or share this resource on social media.
## Definition

## The Wainer hierarchy

## Points of interest

## Functions in fast-growing hierarchies

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

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 ? < ?_{0}. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.

Let ? be a large countable ordinal such 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:

- 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 . (See Points of Interest below.)

Generalizing the above definition even further, a **fast iteration hierarchy** is obtained by taking *f*_{0} 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 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** 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.

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 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'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 (
*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)

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}(6) > 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.

- 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 0704094 - 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, MR 1129778^{[permanent dead link]}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, MR 0656793 - 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. JSTOR 2274873.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists