Misplaced Pages

Hardy hierarchy

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In computability theory, computational complexity theory and proof theory, the Hardy hierarchy, named after G. H. Hardy, is a hierarchy of sets of numerical functions generated from an ordinal-indexed family of functions hα: N → N (where N is the set of natural numbers, {0, 1, ...}) called Hardy functions. It is related to the fast-growing hierarchy and slow-growing hierarchy.

Hardy hierarchy is introduced by Stanley S. Wainer in 1972, but the idea of its definition comes from Hardy's 1904 paper, in which Hardy exhibits a set of reals with cardinality ℵ 1 {\displaystyle \aleph _{1}} .

Definition

Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The Hardy functions hα: N → N, for α < μ, is then defined as follows:

  • H 0 ( n ) = n , {\displaystyle H_{0}(n)=n,}
  • H α + 1 ( n ) = H α ( n + 1 ) , {\displaystyle H_{\alpha +1}(n)=H_{\alpha }(n+1),}
  • H α ( n ) = H α [ n ] ( n ) {\displaystyle H_{\alpha }(n)=H_{\alpha }(n)} if α is a limit ordinal.

Here α denotes the n 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.

The Hardy hierarchy { H α } α < μ {\displaystyle \{{\mathcal {H}}_{\alpha }\}_{\alpha <\mu }} is a family of numerical functions. For each ordinal α, a set H α {\displaystyle {\mathcal {H}}_{\alpha }} is defined as the smallest class of functions containing Hα, zero, successor and projection functions, and closed under limited primitive recursion and limited substitution (similar to Grzegorczyk hierarchy).

Caicedo (2007) defines a modified Hardy hierarchy of functions H α {\displaystyle H_{\alpha }} by using the standard fundamental sequences, but with α (instead of α) 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)

Notes

  1. Fairtlough, Matt; Wainer, Stanley S. (1998). "Chapter III - Hierarchies of Provably Recursive Functions". Handbook of Proof Theory. Vol. 137. Elsevier. pp. 149–207. doi:10.1016/S0049-237X(98)80018-9. ISBN 9780444898401.
  2. ^ Wainer, S. S. (1972). "Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy". The Journal of Symbolic Logic. 37 (2): 281–292. doi:10.2307/2272973. ISSN 0022-4812. JSTOR 2272973. S2CID 34993575.
  3. Hardy, G.H. (1904). "A THEOREM CONCERNING THE INFINITE CANONICAL NUMBERS". Quarterly Journal of Mathematics. 35: 87–94.

References

Categories: