11,689
pages

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.