Googology Wiki
Advertisement
Googology Wiki

The Hardy hierarchy is a certain hierarchy mapping ordinals \(\alpha\) to set of functions \(\mathcal{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 more useful in analyzing sequence systems such as Bashicu matrix system and Y sequence.

The Hardy functions are defined as follows[1]:

  • \(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 ordinal \(\alpha\).


Warning

Main article: 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\) such that \(\gamma\) which satisfies \(\alpha + \beta = \gamma + \beta\) and \(\gamma < \alpha\) does not exist, \(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.

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 1972[2]. 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"[3]. 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

  1. Cantor's Attic, Hardy hierarchy (accessed 2020-11-20)
  2. Wainer, 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
  3. Hardy, G. H.: A THEOREM CONCERING THE INFINITE CARDINAL NUMBERS. Quarterly Journal of Mathematics, Vol 35 (1904). pp. 87–94.

See also

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Advertisement