# Question on An Explicit Enumeration of Ordinals

Question:

What is the first countable ordinal that doesn't appear in the sequence $$T$$ defined below and is that ordinal equal to $$\{ t_i : t_i \in T\}$$?

Introduction: Making a Sequence $$T$$ based on “The Rule of Three”

The primary means of generating a $$T$$ sequence is through the use of a function $$f$$. In general, function $$f$$ is going to be a function that takes as input a three-member sequence of ordinal numbers (an ordered triplet) and returns the set of all ordinals that are a continuation of any recognizable pattern or limit formed by the triplet. The term ‘recognizable pattern or limit’ is defined for this purpose as one meeting a sequence of rules (see “Rules” below).

Rules: Where $$a, b, c, \dots$$ are ordinals $$\text{Rule 1 : }a, a-1, a-2, \dots \implies \{ a-3 \} \text{, where } a \geq 3$$ $$\text{Rule 2 : }0, 1, a, \dots \implies \{a+1\}$$ $$\text{Rule 3 : }0, 2, a, \dots \implies \{a+2\}$$ $$\text{Rule 4 : }a, a+1, a+2, \dots \implies \{ a+3, a + \omega \}$$ $$\text{Rule 5 : }a \cdot b, a \cdot (b+1), a \cdot (b+2), \dots \implies \{ a \cdot (b+3), a \cdot (b + \omega) \}$$ $$\text{Rule 6 : }a^{b}, a^{b+1}, a^{b+2}, \dots \implies \{a^{b+3}, a^{b + \omega}\}$$ $$\text{Rule 7 : }a^{b \cdot c}, a^{b \cdot (c+1)}, a^{b \cdot (c+2)}, \dots \implies \{a^{b \cdot (c+3)}, a^{b \cdot (c + \omega)}\}$$ $$\text{Rule 8 : }a, s(a), s(s(a)), \dots \implies \{ s(s(s(a))), a^{b^{b^{b^{\vdots}}}}\} \text{, where } s(a) = a^b$$

Define function $$f$$:

$$f((a,b,c)) = \bigcup \{ x : a, b, c, \dots \implies x \}, \text{ where } a, b, \text{ and } c \text{ are ordinals and } x \text{ is a set defined by the above rules}$$

Define function $$g$$:

For any set of ordinals, $$A$$, let $$g(A)$$ be the set of all ordered triplets that can be made from the elements of $$A$$: $$g(A) = \{ (a,b,c) : a,b,c \in A \}$$

Define $$X_{Ord}$$: $$X_{Ord} = X \setminus \{ x \in X : x \text{ is not an ordinal} \} \text{ for any set } X$$

Define the sequence $$T$$:

Define a sequence $$T = t_1, t_2, t_3, \dots$$ via iterations where:

Step 1) $$t_1 = 1, t_2 = 2,$$ and $$t_3 = 3$$.

Step 2) Each $$t_n$$, where $$n \geq 4$$, is defined by the previous elements of the sequence. Starting with $$n = 4$$:

a) Let $$A = \{ t_i \in T : i < n \}$$. E.g., $$A = \{1, 2, 3 \}$$ on the first iteration.

b) Let $$B = \{ f((a,b,c))_{Ord} : (a,b,c) \in g(A) \}$$. Using the previous elements of the sequence $$A$$, this step creates a set $$B$$ of all the new sets of ordinals implied by letting function $$f$$ range over $$g(A)$$. The use of the $$X_{Ord}$$ function in the definition of $$B$$ may be unnecessary for this particular $$T$$ sequence.

c) Let $$C = ( \bigcup B ) \setminus A$$ and let $$c_1, c_2, c_3, \dots$$ be an enumeration of $$C$$ that is also well ordered if $$|C| \in \mathbb{N}$$. This step shaves off any redundant elements of $$\bigcup B$$ before potentially well ordering them so that we can add them to $$T$$.

d) If $$|C| \in \mathbb{N}$$, then set $$t_n = c_1, t_{n+1} = c_2, t_{n+2} = c_3, \dots, t_{n+j-1} = c_j$$.

e) If $$|C| = |\mathbb{N}|$$ (not applicable for this particular $$T$$ sequence), then let $$T’ = t’_1, t’_2, t’_3, \dots$$, be a subsequence of the remaining undefined elements of $$T$$ and set $$t’_n = c_1, t’_{n+2} = c_2, t’_{n+4} = c_3, \dots$$.

Step 3) Proceed to the next undefined index $$j$$ in $$T$$, set $$n = j$$, and repeat step 2.

Assuming my calculations are correct (it gets tricky!!!), the first few elements of $$T$$ would be: $$T = 1,2,3,0,4,\omega,5,6, \omega + 1, \omega +2,7,8,\omega + 3,\omega + 4,\omega \cdot 2,9,10,\omega+5,\omega+6, \omega \cdot 2 + 1, \omega \cdot 2 + 2, \dots$$

The first iteration would generate $$0$$ based on Rule 1 and $$(3,2,1)$$. It would also generate $$4$$ and $$\omega$$ based on $$(1,2,3)$$ Rule 4. These are then added to $$T$$ to complete the first iteration.

• What does it mean for an ordinal to be "comprised from" an alphabet (especially since you use exponentiation later on, which isn't in that alphabet)? – Noah Schweber Sep 20 '19 at 20:58
• The multiplication operator $\cdot$ is included in the alphabet. You can't have multiplication in this context without exponentiation, can you? – AplanisTophet Sep 21 '19 at 0:52
• For finite powers, sure - but something like "$\omega^\omega$"? Regardless, (a) you need to explain what you mean by that and (b) actually you don't seem to need it at all, you can just talk about operations on ordinals themselves. – Noah Schweber Sep 21 '19 at 1:53
• The ordinal $\omega^{\omega}$ easily appears in the sequence due $(\omega, \omega^2, \omega^3)$ and Rule 6. So does $\epsilon_0 = \omega^{\epsilon_0}$, and many more countable ordinals. So, is $\{t_i : t_i \in T \}$ an ordinal? If so, is it less than the Church-Kleene ordinal? – AplanisTophet Sep 21 '19 at 2:47
• I know $\omega^\omega$ appears there - I'm asking how it's "comprised from" your $\Sigma$, and what that means in the first place. (Really, though, there's no reason to talk about $\Sigma$ at all - why include it? What role does it serve?) – Noah Schweber Sep 21 '19 at 2:51

A ninth rule would extend the $$T$$ sequence and also exposes the first ordinal not in $$T$$ based on the above eight rules:
$$\text{Rule 9 : }a, s(a), s(s(a)), \dots \implies \{ s(s(s(a))), \dots(s(s(s(a)))) \}, \text{ where } s(a) = a^{a^{a^{\vdots}}}$$
The $$T$$ sequence with only eight rules would allow for the following subsequence unbounded in $$\dots(s(s(s(\omega))))$$: $$\omega, s(\omega), s(s(\omega)), s(s(s(\omega))), \dots$$
The ninth rule is the next logical extension of the sequence based on the fixed point of a normal function after only eight rules where: $$\phi : \omega_1 \rightarrow \omega_1, \text{ and } \phi(\dots(s(s(s(\omega))))) = \dots(s(s(s(\omega))))$$
That is why $$\dots(s(s(s(\omega))))$$ is the first ordinal not in $$T$$ (sorry for the lack of a better description).