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".

Definition

Let ? be a large countable 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:

• ${\displaystyle h_{0}(n)=n,}$
• ${\displaystyle h_{\alpha +1}(n)=h_{\alpha }(n+1),}$
• ${\displaystyle h_{\alpha }(n)=h_{\alpha [n]}(n)}$ if ? is a limit ordinal.

Here ?[n] denotes the n^th element of the fundamental sequence assigned to the limit ordinal ?. A standardized choice of fundamental sequence for all ? ?₀ is described in the article on the fast-growing hierarchy.

Caicedo (2007) defines a modified Hardy hierarchy of functions ${\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 ? < ?₀. Thus, for any ? < ?₀, h_? grows much more slowly than does f_?. However, the Hardy hierarchy "catches up" to the Wainer hierarchy at ? = ?₀, 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)

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 ?₀? 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.