In computability theory, computational complexity theory and proof theory, the Hardy hierarchy, named after G. H. Hardy, is a hierarchy of sets of numerical functions generated from an ordinal-indexed family of functions hα: N → N (where N is the set of natural numbers,) called Hardy functions. It is related to the fast-growing hierarchy and slow-growing hierarchy.
Hardy hierarchy is introduced by Stanley S. Wainer in 1972,[1] [2] but the idea of its definition comes from Hardy's 1904 paper,[3] in which Hardy exhibits a set of reals with cardinality
\aleph1
Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The Hardy functions hα: N → N, for α < μ, is then defined as follows:
H0(n)=n,
H\alpha+1(n)=H\alpha(n+1),
H\alpha(n)=H\alpha[n](n)
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.
The Hardy hierarchy
\{l{H}\alpha\}\alpha<\mu
l{H}\alpha
defines a modified Hardy hierarchy of functions
H\alpha
The Wainer hierarchy 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.