Hardy hierarchy

From Wikipedia, the free encyclopedia
Jump to: navigation, 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".

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:

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