# 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[edit]

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:

- 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 *α* ≤ *ε*_{0} is described in the article on the fast-growing hierarchy.

Caicedo (2007) 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[edit]

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[edit]

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