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:

• $h_{0}(n)=n,\,$
• $h_{\alpha +1}(n)=h_{\alpha }(n+1),\,$
• $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 α.

Fast-growing hierarchy#Definition describes a standardized choice of fundamental sequence for all α ≤ ε₀.

Relation to fast-growing hierarchy

Although the Hardy hierarchy appears to grow more slowly than the fast-growing hierarchy, Gallier (1991) claims that it is not difficult to see that ƒ_α(n) = h_ω^α(n) and thus that ƒ_ε0(n) = h_ε0(n).

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", Ann. Pure Appl. Logic, 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR1129778 PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)