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 [math]\displaystyle{ \aleph_1 }[/math].
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:
- [math]\displaystyle{ h_0(n) = n, }[/math]
- [math]\displaystyle{ h_{\alpha+1}(n) = h_\alpha(n + 1), }[/math]
- [math]\displaystyle{ h_\alpha(n) = h_{\alpha[n]}(n) }[/math] 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.
The Hardy hierarchy [math]\displaystyle{ \{\mathcal{H}_\alpha\}_{\alpha\lt \mu} }[/math] is a family of numerical functions. For each ordinal α, a set [math]\displaystyle{ \mathcal{H}_\alpha }[/math] 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 [math]\displaystyle{ H_\alpha }[/math] 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 α < ε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
- ↑ Fairtlough, Matt; Wainer, Stanley S. (1998). "Chapter III - Hierarchies of Provably Recursive Functions". Handbook of Proof Theory. 137. Elsevier. pp. 149–207. doi:10.1016/S0049-237X(98)80018-9. ISBN 9780444898401.
- ↑ 2.0 2.1 2.2 Wainer, S. S. (1972). "Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy" (in en). The Journal of Symbolic Logic 37 (2): 281–292. doi:10.2307/2272973. ISSN 0022-4812. https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/ordinal-recursion-and-a-refinement-of-the-extended-grzegorczyk-hierarchy/C47A374233B902E669249E46945163F1.
- ↑ 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 Γ0? A survey of some results in proof theory", Ann. Pure Appl. Logic 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, https://www.cis.upenn.edu/~jean/kruskal.pdf. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
- Caicedo, A. (2007), "Goodstein's function", Revista Colombiana de Matemáticas 41 (2): 381–391, http://andrescaicedo.files.wordpress.com/2008/04/goodstein.pdf.
 |  |
