Hardy hierarchy
Introduction 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.Hardy hierarchy is 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 .
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 ''α'' th 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'''  is a family of numerical functions. For each ordinal , a set  is defined as the smallest class of functions containing , zero, successor and projection functions, and closed under limited primitive recursion and limited substitution (similar to Grzegorczyk hierarchy). 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 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.
Notes
References **. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions". )* .