Hardy Hierarchy
Get Hardy Hierarchy essential facts below. View Videos or join the Hardy Hierarchy discussion. Add Hardy Hierarchy to your PopFlock.com topic list for future reference or share this resource on social media.
Hardy Hierarchy

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 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 ${\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)

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