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, {0, 1, ...}) called Hardy functions. It is related to the fast-growing hierarchy and slow-growing hierarchy. The Hardy hierarchy was introduced by Stanley S. Wainer in 1972, but the idea of its definition comes from Hardy's 1904 paper, in which Hardy exhibits a set of reals with cardinality ℵ 1 {\displaystyle \aleph _{1}} .
Definition 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:
H 0 ( n ) = n , {\displaystyle H_{0}(n)=n,}
H α + 1 ( n ) = H α ( n + 1 ) , {\displaystyle H_{\alpha +1}(n)=H_{\alpha }(n+1),}
H α ( n ) = H α [ n ] ( n ) {\displaystyle H_{\alpha }(n)=H_{\alpha [n]}(n)} 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. The Hardy hierarchy { H α } α < μ {\displaystyle \{{\mathcal {H}}_{\alpha }\}_{\alpha <\mu }} is a family of numerical functions. For each ordinal α, a set H α {\displaystyle {\mathcal {H}}_{\alpha }} is defined as the smallest class of functions containing Hα, zero, successor and projection functions, and closed under limited primitive recursion and limited substitution (similar to Grzegorczyk hierarchy). Caicedo (2007) defines a modified Hardy hierarchy of functions H α {\displaystyle H_{\alpha }} 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 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. (Gallier 1991)
Notes
References Hardy, G.H. (1904), "A theorem concerning the infinite cardinal numbers", Quarterly Journal of Mathematics, 35: 87–94 Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory" (PDF), Ann. Pure Appl. Logic, 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR 1129778. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".) Caicedo, A. (2007), "Goodstein's function" (PDF), Revista Colombiana de Matemáticas, 41 (2): 381–391.