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.

  • $\begingroup$ 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)? $\endgroup$ – Noah Schweber Sep 20 '19 at 20:58
  • $\begingroup$ The multiplication operator $\cdot$ is included in the alphabet. You can't have multiplication in this context without exponentiation, can you? $\endgroup$ – AplanisTophet Sep 21 '19 at 0:52
  • $\begingroup$ 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. $\endgroup$ – Noah Schweber Sep 21 '19 at 1:53
  • $\begingroup$ 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? $\endgroup$ – AplanisTophet Sep 21 '19 at 2:47
  • $\begingroup$ 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?) $\endgroup$ – 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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.