Hardy hierarchy

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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


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


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