Hardy hierarchy

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,[1][2] but the idea of its definition comes from Hardy's 1904 paper,[2][3] in which Hardy exhibits a set of reals with cardinality $\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,$
$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 α. A standardized choice of fundamental sequence for all α ≤ ε₀ is described in the article on the fast-growing hierarchy.

The Hardy hierarchy $\{{\mathcal {H}}_{\alpha }\}_{\alpha <\mu }$ is a family of numerical functions. For each ordinal $α$ , a set ${\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[2] (similar to Grzegorczyk 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

The Wainer hierarchy of functions f_α and the Hardy hierarchy of functions h_α are related by f_α = h_ω^α for all α < ε₀. Thus, for any α < ε₀, h_α grows much more slowly than does f_α. However, the Hardy hierarchy "catches up" to the Wainer hierarchy at α = ε₀, such that f_ε₀ and h_ε₀ have the same growth rate, in the sense that f_ε₀(n-1) ≤ h_ε₀(n) ≤ f_ε₀(n+1) for all n ≥ 1. (Gallier 1991)

Notes

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.
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.
Hardy, G.H. (1904). "A THEOREM CONCERNING THE INFINITE CANONICAL NUMBERS". Quarterly Journal of Mathematics. 35: 87–94.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

[:0-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.