Hardy hierarchy
Encyclopedia
In 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 (where N is the set of natural numbers, {0, 1, ...}). It is related to the fast-growing hierarchy
and slow-growing hierarchy
. The hierarchy was first described in Hardy's 1904 paper, "A theorem concerning the infinite cardinal numbers".
such that a fundamental sequence is assigned to every limit ordinal less than μ. The Hardy hierarchy of functions hα: N → N, for α < μ, is then defined as follows:
Here α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α. A standardized choice of fundamental sequence for all α ≤ ε0 is described in the article on the fast-growing hierarchy.
Caicedo (2007) defines a modified Hardy hierarchy of functions
by using the standard fundamental sequences, but with α[n+1] (instead of α[n]) in the third line of the above definition.
of functions fα and the Hardy hierarchy of functions hα are related by fα = hωα for all α < ε0. Thus, for any α < ε0, hα grows much more slowly than does fα. However, 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)
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 Hardy hierarchy, named after G. H. Hardy
G. H. Hardy
Godfrey Harold “G. H.” Hardy FRS was a prominent English mathematician, known for his achievements in number theory and mathematical analysis....
, is an ordinal-indexed family of functions hα: N → N (where N is the set of natural numbers, {0, 1, ...}). It is related to 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...
and 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...
. The hierarchy was first described in Hardy's 1904 paper, "A theorem concerning the infinite cardinal numbers".
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 Hardy hierarchy of functions hα: 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 α. A standardized choice of fundamental sequence for all α ≤ ε0 is described in the article on the fast-growing hierarchy.
Caicedo (2007) defines a modified Hardy hierarchy of functions
by using the standard fundamental sequences, but with α[n+1] (instead of α[n]) in the third line of the above definition.Relation to fast-growing hierarchy
The Wainer hierarchyFast-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...
of functions fα and the Hardy hierarchy of functions hα are related by fα = hωα for all α < ε0. Thus, for any α < ε0, hα grows much more slowly than does fα. However, 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)