Googology Wiki
Advertisement
Googology Wiki

The Hardy hierarchy is a certain hierarchy mapping ordinals \(\alpha\) to 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, who first described it in his 1904 paper "A theorem concerning the infinite cardinal numbers". It is less known than its speedier cousin, the fast-growing hierarchy. 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 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\). 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 \(\epsilon\) 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 Hierarchy and other googological notations.

\(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)\)

\(H_{\omega+m}(n) = 2(n+m)\)

\(H_{\omega 2}(n) = 4n\)

\(H_{(\omega 2)+m}(n) = 4(n+m)\)

\(H_{\omega 3}(n) = 8n\)

\(H_{(\omega 3)+m}(n) = 8(n+m)\)

\(H_{\omega m}(n) = (2^m)n\)

\(H_{\omega m+x}(n) = 2^m(n+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\}\)

We can note that the Hardy Hierarchy relates to the Fast-growing hierarchy by the following way: \(H_{\omega^\alpha}(n) = f_\alpha(n)\), where \(\alpha < \varepsilon_0\).

Sources

  1. Cantor's Attic, Hardy hierarchy (accessed 2020-11-20)

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 · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert'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