Classifying numbers with ordinals

Introduction

Robert Munafo classified natural numbers with classes. This method is useful for classifying large numbers of tetration level, but it is not useful for classifying numbers such as Graham's number.

Therefore in googology we classify functions which define large numbers. For example, in Grzegorczyk hierarchy, an infinite set of functions \(E_i\) for some natural number \(i\) is introduced, and the n-th hierarchy \(\mathcal{E}^n\) which containes certain classes of functions are defined. The set has hierarchy structure such that

\[ \mathcal{E}^0 \subseteq \mathcal{E}^1 \subseteq \mathcal{E}^2 \subseteq \cdots\]

By extending this definition to ordinal, fast-growing hierarchy (FGH) is defined. FGH defined in googology wiki is

• \(f_0(n) = n + 1\)
• \(f_{\alpha+1}(n) = f^n_\alpha(n)\), where \(f^n\) denotes function iteration
• \(f_\alpha(n) = f_{\alpha[n]}(n)\) if and only if \(\alpha\) is a limit ordinal 

where \(\alpha[n]\) is the n-th ordinal of fundamental sequence for limit ordinal \(\alpha\). This definition defines a function \(f_\alpha\) to an ordinal \(\alpha\). Actually FGH is also called extended Grzegorczyk hierarchy, which defines a set of functions in the hierarchy of \(\alpha\), \(\mathcal{E}^\alpha\). The definition of FGH in the googology wiki is considered as extracting an example of functions which belong to the set of function in the hierarchy.

As the function can be strictly classified with the extended Grzegorczyk hierarchy, the Graham's number can be expressed as "a large number defined with a Graham function which belongs to the \(\omega+1\) level of hierarchy". This expression is a bit lengthy, and I want to express that a certain number belongs to a certain hierarchy, such as "Graham's number is in the \(\omega+1\) level of hierarchy". In this article, I propose a method to classify the numbers with hierarchy using FGH.

Goal

For an ordinal \(\alpha\), I want to define a set of natural numbers \(\mathcal{E}^{\alpha}\) so that

\[ \alpha < \beta \Rightarrow \mathcal{E}^\alpha < \mathcal{E}^\beta \]

However, it is impossible. Therefore I set the goal as

A number \(n\) belongs to the class of an ordinal \(\alpha = C(n)\), and \( C(m) < C(n) \Rightarrow m < n \)

Definition

(1) Set of ordinals for hierarchy

Assume that we have unique definition of fundamental sequence \(\beta[n]\) for all the limit ordinals not exceeding \(\gamma\). We then have a unique definition of \(f_{\alpha}\) (see definition of FGH above) for all \(\alpha \le \gamma\). To make the hierarchy system "strong enough", the fundamental sequence should be defined so that every ordinal \(\alpha \le \gamma\) can be expressed as \(\alpha = \gamma[n_1][n_2] \cdots [n_k]\).

For example, we can use the Wainer hierarchy for \(\gamma = \varepsilon_0\).

Define set \(A\) as follows.

1. \(\gamma \in A\)
2. if \(\beta \in A\) and \(\beta\) is a limit ordinal, \(\beta[0],\ldots,\beta[99] \in A\)
3. if \(\beta+1 \in A\), \(\beta \in A\)
4. 1, 2 and 3 define all the elements of \(A\).

Here, as we use only finite part of fundamental sequence in #2, \(A\) is a finite set. (Mikadukim proved it in the comment to my Japanese blog post. Actually I think it is obvious.)

(2) Limit function

Limit function \(L(\alpha)\) with the domain of \(\alpha \in A\) is defined with the FGH defined in (1) as

\[L(\alpha) = f_{\alpha}^6(100) \]

for \(\alpha, \beta \in A\), \(\alpha < \beta \Rightarrow L(\alpha) < L(\beta)\) (see Appendix)

(3) Classifying function

Classifying function \(C(n)\) with the domain of natural number \(n \le L(\gamma)\) is defined as

\(C(n) = \alpha\)

for the smallest \(\alpha\) such that \(n \le L(\alpha)\)

\(n\) is a class \(C(n)\) number.

Appendix

Selection of the function defining the limit function

\[L(\alpha) = f_{\alpha}^6(100) \]

is arbitral. We can use any function which uniquely classifies numbers. It is similar to the idea of Robert Munafo's class - the selection of \(10^6\) is arbitral and we can use \(10^7\) if we want. I wanted to define the upper limit of numbers that can be "approximated with \(f_\alpha\) function easily". We can easily use the function 6 times and get \(f^6_\alpha\), and that is why I selected this function.

The reason that we use only the finite subset of \(\gamma\) as the \(A\) is that if we use all the ordinals below \(\gamma\) as the domain of the limit function, \(\alpha < \beta \Rightarrow L(\alpha) < L(\beta)\) is not true and we can not classify numbers. For example, let \(\alpha = L(\omega)\) and we get \(\alpha < \omega\) and \(L(\alpha) > L(\omega)\).

Proof that for \(\alpha, \beta \in A\), \(\alpha < \beta \Rightarrow L(\alpha) < L(\beta)\)

As \(A\) is a finite set, we can index the element of \(A\) as

\(\alpha_0 < \alpha_1 < ... < \alpha_N\)

What we should prove is \(L(\alpha_n) < L(\alpha_{n+1})\).

If \(\alpha_{n+1}\) is a successor

\(f_{\alpha_{n+1}}(n) = f_{\alpha_{n}+1}(n) = f_{\alpha_{n}}^n(n) > f_{\alpha_{n}}(n)\)

Therefore \(L(\alpha_n) < L(\alpha_{n+1})\)

If \(\alpha_{n+1}\) is a limit ordinal, \(\alpha_{n}=\alpha_{n+1}[99]\), \(f_{\alpha_{n+1}}(m)=f_{\alpha_{n+1}[m]}(m)\)

Therefore \(L(\alpha_n) = f_{\alpha_{n+1}[99]}^6(100) < f_{\alpha_{n+1}}^6(100) = L(\alpha_{n+1})\)

Acknowledgement

Mikadukim told me how to define \(A\). Hyp cos suggested the restriction to the sequence of fundamental sequence. p進大好きbot suggested the condition of \(\beta+1 \in A \rightarrow \beta \in A\).

Examples

\(\gamma = \epsilon_0\) and we use Wainer hierarchy

• C(100) = 0
• C(1000) = 1
• C(Googolquadriplex) = 2
• C(Tritri) = 3
• C(Tritet) = 4
• C(Moser's number) = \(\omega\)
• C(Graham's number) = \(\omega + 1\)
• C(Fish number 1) = \(\omega^2 + 1\)
• C(Fish number 2) = \(\omega^3\)
• C(Okojo-stoat number) = \(\omega^\omega\)
• C(Fish number 3) = \(\omega^{\omega+1} 63+1\)
• C(Gongulus) = \(\omega^{\omega^{\omega}}\) (\(\omega^{\omega^{100}}\) is not an element of \(A\))

Limit function

• L(0) = f₀⁶(100) = 106
• L(1) = f₁⁶(100) = 6400
• L(2) = f₂⁶(100) ≈ 10^10^10^10^10^10^31.5816 ≈ 10↑↑7.1759
• L(3) = f₃⁶(100) ≈ 10↑↑↑7
• L(4) = f₄⁶(100) ≈ 10↑↑↑↑7
• L(99) = f₉₉⁶(100) = 10↑⁹⁹7
• L(ω) = f_ω⁶(100) = 3→3→7→2 = A(1,1,7)
• L(ω+1) = f_ω+1⁶(100) = 3→3→7→3 = A(1,2,6)
• L(ω+2) = f_ω+1⁶(100) = 3→3→7→4 = A(1,3,6)
• L(ω+3) = f_ω+3⁶(100) = 3→3→7→5 = A(1,4,6)
• L(ω+99) = f_ω+99⁶(100) = 3→3→7→101 = A(1,100,6)
• L(ω2) = 3→3→3→7→2 = A(2,1,6)
• L(ω2+1) = 3→3→3→7→3 = A(2,2,6)
• L(ω2+2) = 3→3→3→7→4 = A(2,3,6)
• L(ω3) = 3→3→3→3→7→2 = A(3,1,6)
• L(ω4) = 3→3→3→3→3→7→2 = A(4,1,6)
• L(ω5) = 3→3→3→3→3→3→7→2 = A(5,1,6)
• L(ω²) = A(1,0,1,6)