Slow-growing hierarchy
Encyclopedia
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 (where N is the set of natural numbers, {0, 1, ...}). It contrasts with the fast-growing hierarchy
.
such that a fundamental sequence is assigned to every limit ordinal less than μ. The slow-growing hierarchy of functions gα: N → N, for α < μ, is then defined as follows:
Here α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α.
The article on the Fast-growing hierarchy describes a standardized choice for fundamental sequence for all α < ε0.
. (Girard 1981) and (Cichon and Wainer 1983)
However, Girard (1981) proved that the slow-growing hierarchy eventually catches up with the fast-growing one. Specifically, that there exists an ordinal α and integers a, b such that
where fα are the functions in the fast-growing hierarchy. He further showed that the first α this holds for is the ordinal of the theory ID<ω of arbitrary finite iterations of an inductive definition. (Wainer 1989). However for the Cichon assignment of fundamental sequences the first match up occurs at the level ε0 (Weiermann 1997).
Extensions of the result proved in Wainer 1989 to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated
-comprehension where the slow and fast growing hierarchy match up (Weiermann 1995).
For the novice it is worth mentioning that the slow growing hierarchy depends extremely sensitive on the choice of the underlying fundamental sequences (Weiermann 1997 and Weiermann 1999).
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...
, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions gα: N → N (where N is the set of natural numbers, {0, 1, ...}). It contrasts with the fast-growing hierarchy
Fast-growing hierarchy
In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy is an ordinal-indexed family of rapidly increasing functions fα: N → N...
.
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 is assigned to every limit ordinal less than μ. The slow-growing hierarchy of functions gα: N → N, for α < μ, is then defined as follows:
if α is a limit ordinal.
Here α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α.
The article on the Fast-growing hierarchy describes a standardized choice for fundamental sequence for all α < ε0.
Relation to fast-growing hierarchy
The slow-growing hierarchy grows much more slowly than the fast-growing hierarchy. Even gε0 is only equivalent to f3 and gα only attains the growth of fε0 (the first function that Peano arithmetic cannot prove total in the hierarchy) when α is the Bachmann–Howard ordinalBachmann–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...
. (Girard 1981) and (Cichon and Wainer 1983)
However, Girard (1981) proved that the slow-growing hierarchy eventually catches up with the fast-growing one. Specifically, that there exists an ordinal α and integers a, b such that
- gα(n) < fα(n) < gα(n + 1)
where fα are the functions in the fast-growing hierarchy. He further showed that the first α this holds for is the ordinal of the theory ID<ω of arbitrary finite iterations of an inductive definition. (Wainer 1989). However for the Cichon assignment of fundamental sequences the first match up occurs at the level ε0 (Weiermann 1997).
Extensions of the result proved in Wainer 1989 to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated
-comprehension where the slow and fast growing hierarchy match up (Weiermann 1995).For the novice it is worth mentioning that the slow growing hierarchy depends extremely sensitive on the choice of the underlying fundamental sequences (Weiermann 1997 and Weiermann 1999).