Hardy hierarchy

The Hardy hierarchy is a certain hierarchy mapping ordinals \(\alpha\) to a set of functions \(H_\alpha\) generated from Hardy functions \(H_\alpha: \mathbb{N} \rightarrow \mathbb{N}\). For large ordinals \(\alpha\), \(H_\alpha\) grows extremely fast. The Hardy hierarchy is named after G. H. Hardy. However, it can on occasion be more useful than the fast-growing hierarchy; for example, it can more easily be related to the numbers resulting from Goodstein sequences, and it is better in analyzing sequence systems such as Bashicu matrix system and Y sequence than the Fast-growing hierarchy.
== Warning ==
A system of fundamental sequences for limit ordinals below a given supremum is not unique, and the Hardy hierarchy heavily depends on the choice of such a system. In particular, the Hardy hierarchy is ill-defined unless a specific choice of a system of fundamental sequences is explicitly fixed in the context. One hierarchy, the Wainer hierarchy, is explained at the article for the fast-growing hierarchy.
For the fundamental hierarchy of the Wainer hierarchy, following property is satisfied.
* For all \(\alpha,\beta < \varepsilon_0\), if there is no \(\gamma < \alpha\) which satisfies \(\alpha + \beta = \gamma + \beta\), then \(H_{\alpha+\beta}(n) = H_{\alpha}(H_{\beta}(n))\)
* For all \(\alpha < \varepsilon_0\), \(H_{\omega^\alpha}(n) = f_\alpha(n)\) where \(f_{\alpha}\) is fast-growing hierarchy.
This is a property of Wainer Hierarchy, but sometimes it is misinterpreted as properties for other fundamental sequences. For example, the statement that "When \(\alpha\) is an \(\varepsilon\) number, \(\alpha = \omega^{\alpha}\) and therefore \(H_{\alpha}(n) = H_{\omega^{\alpha}}(n) = f_{\alpha}(n)\)" is a typical mistake.
== Definition ==
The Hardy functions are defined as followsCantor's Attic, Hardy hierarchy (accessed 2020-11-20):
* \(H_0(n) = n\)
* \(H_{\alpha+1}(n) = H_\alpha(n+1)\)
* \(H_\alpha(n) = H_{\alpha[n]}(n)\) if \(\alpha\) is a limit ordinal
Here, \(\alpha[n]\) denotes the \(n\)th term of a fixed fundamental sequence assigned to the ordinal \(\alpha\).
== Functions ==
Below is the list of comparisons between the Hardy functions with respect to unspecified fundamental sequences and other googological notations. Note that Hardy hierarchy is ill-defined when we do not fix fundamental sequences, and vary when we change them as we explained in #Warning. Therefore this computation does not necesarily hold for a specific choice of fundamental sequences.
\(H_0(n) = n\)
\(H_1(n) = n+1\)
\(H_2(n) = n+2\)
\(H_m(n) = n+m\)
\(H_\omega(n) = 2n\)
\(H_{\omega+1}(n) = 2(n+1) = 2n+2\)
\(H_{\omega+2}(n) = 2(n+2) = 2n+4\)
\(H_{\omega+m}(n) = 2(n+m) = 2n + 2m\)
\(H_{\omega 2}(n) = 4n\)
\(H_{(\omega 2)+m}(n) = 4(n+m) = 4n + 4m\)
\(H_{\omega 3}(n) = 8n\)
\(H_{(\omega 3)+m}(n) = 8(n+m) = 8n + 8m\)
\(H_{\omega m}(n) = (2^m)n\)
\(H_{\omega m+x}(n) = 2^m(n+x) = (2^m)n + (2^m)x\)
\(H_{\omega^2}(n) = 2^n*n\)
\(H_{\omega^2+1}(n) = 2^{n+1}*(n+1)\)
\(H_{\omega^2+2}(n) = 2^{n+2}*(n+2)\)
\(H_{\omega^2+\omega}(n) = 2^{2n}*(2n)\)
\(H_{\omega^2+\omega 2}(n) = 2^{4n}*(4n)\)
\(H_{(\omega^2) 2}(n) = 2^{2^n*n}*(2^n*n)\)
\(H_{(\omega^2) 3}(n) = 2^{2^{2^n*n}*(2^n*n)}*(2^{2^n*n}*(2^n*n))\)
\(H_{(\omega^2) m}(n) = 2^{H_{(\omega^2) m-1}(n)}*(H_{(\omega^2) m-1}(n))\)
\(H_{\omega^3}(n) \approx n \uparrow\uparrow n\)
\(H_{(\omega^3) 2}(n) \approx n \uparrow\uparrow (n \uparrow\uparrow n)\)
\(H_{\omega^4}(n) \approx n \uparrow\uparrow\uparrow n\)
\(H_{\omega^5}(n) \approx n \uparrow\uparrow\uparrow\uparrow n\)
\(H_{\omega^m}(n) \approx \{n,n,m-1\}\)
\(H_{\omega^\omega}(n) \approx \{n,n,n-1\}\)
\(H_{\omega^\omega+1}(n) \approx \{n,n,n\}\)
\(H_{\omega^\omega+2}(n) \approx \{n,n,n+1\}\)
\(H_{\omega^\omega+\omega}(n) \approx \{n,n,2n\}\)
\(H_{\omega^\omega+\omega^2}(n) \approx \{n,n,2^n*n\}\)
\(H_{(\omega^\omega) 2}(n) \approx \{n,n,\{n,n,n\}\}\)
\(H_{(\omega^\omega) 3}(n) \approx \{n,n,\{n,n,\{n,n,n\}\}\}\)
\(H_{\omega^{\omega+1}}(n)\) or \(H_{(\omega^\omega) \omega}(n) \approx \{n,n,1,2\}\)
\(H_{\omega^{\omega+2}}(n) \approx \{n,n,2,2\}\)
\(H_{\omega^{\omega+m}}(n) \approx \{n,n,m,2\}\)
\(H_{\omega^{\omega 2}}(n) \approx \{n,n,n,2\}\)
\(H_{\omega^{\omega 2+1}}(n) \approx \{n,n,1,3\}\)
\(H_{\omega^{\omega 2+2}}(n) \approx \{n,n,2,3\}\)
\(H_{\omega^{\omega m+2}}(n) \approx \{n,n,m,3\}\)
\(H_{\omega^{\omega m}}(n) \approx \{n,n,n,m\}\)
\(H_{\omega^{\omega m+x}}(n) \approx \{n,n,x,m+1\}\)
\(H_{\omega^{\omega^2}}(n) \approx \{n,n,n,n\}\)
\(H_{\omega^{\omega^3}}(n) \approx \{n,n,n,n,n\}\)
\(H_{\omega^{\omega^{m-2}}}(n) \approx \{n,m (1) 2\} = m \& n\)
\(H_{\omega^{\omega^m}}(n) \approx \{n,m+2 (1) 2\}\)
\(H_{\omega^{\omega^\omega}}(n) \approx \{n,n+2 (1) 2\}\)
== Historical Note ==
Hardy hierarchy and Hardy functions is first introduced and defined by Stanley S. Wainer in 1972Wainer, S. S.: Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy. The Journal of Symbolic Logic, Vol. 37, Issue 2, June 1972, pp. 281–292. doi:10.2307/2272973. The hierarchy he originally defined was only \(\varepsilon_0\) strata (this is similar to Wainer hierarchy). Wainer described the hierarchy \(\{\mathcal{H}_\beta\}_{\beta<\varepsilon_0}\) as a convenient refinement of Wainer hierarchy.
The hierarchy was named after Godfery H. Hardy, because the idea of definition of functions \(h_\alpha\) comes from his 1904 paper "A THEOREM CONCERING THE INFINITE CARDINAL NUMBERS"Hardy, G. H.: A THEOREM CONCERING THE INFINITE CARDINAL NUMBERS. Quarterly Journal of Mathematics, Vol 35 (1904). pp. 87–94.. In the 1904 paper, Hardy exhibited a set of reals with cardinality \(\aleph_1\), and he showed constructible sequences of numbers parametrized by ordinals until \(\aleph_1\) by using the origin idea.
Note that even though sequences are consructible, but it is needed fundamental sequences of all countable ordinals.
==Sources==
== See also ==
ja:ハーディー階層
ru:Иерархия Харди
Category:Hierarchies
Category:Googology
Category:Functions
Category:Transfinite ordinals
Category:Notations
Category:Eponymous functions