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.
The Hardy hierarchy was introduced by Stanley S. Wainer in 1972,{{Cite book |last1=Fairtlough |first1=Matt |title=Handbook of Proof Theory |last2=Wainer |first2=Stanley S. |publisher=Elsevier |year=1998 |isbn=9780444898401 |volume=137 |pages=149–207 |chapter=Chapter III - Hierarchies of Provably Recursive Functions |doi=10.1016/S0049-237X(98)80018-9}}{{Cite journal |last=Wainer |first=S. S. |year=1972 |title=Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy |url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/ordinal-recursion-and-a-refinement-of-the-extended-grzegorczyk-hierarchy/C47A374233B902E669249E46945163F1 |journal=The Journal of Symbolic Logic |language=en |volume=37 |issue=2 |pages=281–292 |doi=10.2307/2272973 |jstor=2272973 |s2cid=34993575 |issn=0022-4812}} but the idea of its definition comes from Hardy's 1904 paper,{{Cite journal |last=Hardy |first=G.H. |author-link=G. H. Hardy |year=1904 |title=A THEOREM CONCERNING THE INFINITE CANONICAL NUMBERS |journal=Quarterly Journal of Mathematics |volume=35 |pages=87–94}} in which Hardy exhibits a set of reals with cardinality .
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:
- 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 is a family of numerical functions. For each ordinal {{Math|α}}, a set is defined as the smallest class of functions containing {{Math|Hα}}, zero, successor and projection functions, and closed under limited primitive recursion and limited substitution (similar to Grzegorczyk hierarchy).
{{Harvp|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
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. {{harv|Gallier|1991}}
Notes
{{Reflist}}
References
- {{citation|last= Hardy |first= G.H. |authorlink= G. H. Hardy|title= A theorem concerning the infinite cardinal numbers |journal= Quarterly Journal of Mathematics |volume= 35 |year= 1904 |pages= 87–94}}
- {{citation|mr=1129778|last= Gallier|first= Jean H.|authorlink= Jean Gallier |title= What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory|journal= Ann. Pure Appl. Logic|volume= 53 |year=1991|issue= 3|pages= 199–260|url=https://www.cis.upenn.edu/~jean/kruskal.pdf|doi=10.1016/0168-0072(91)90022-E|doi-access=free}}. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
- {{Citation |last=Caicedo |first=A. |title=Goodstein's function |url=http://andrescaicedo.files.wordpress.com/2008/04/goodstein.pdf |journal=Revista Colombiana de Matemáticas |volume=41 |issue=2 |year=2007 |pages=381–391 }}.