Comprehending ordinals: from $\omega^\omega$ through $\omega^{\omega^2}$ to $\varepsilon_0$

Question

I am currently trying to comprehend ordinal numbers by finding an order on some countable set (like natural numbers or tuples of natural numbers) that is isomorphic to some ordinal.

For an instance, I think that I can "see" $\omega^\omega$, because of the following: consider $(T, <)$, where $T$ are the $n$-tuples of natural numbers of all lengths. The order is defined as: $x < y$ iff $x$ is shorter (has less components) than $y$, or they have the same length but $x$ comes before $y$ lexicographically. This ordered set is isomorphic to $\omega^\omega$, and it is easy to imagine.

I am looking for some similar structure for $\omega^{\omega^2}$, or even $\varepsilon_0$.

Answer 1

I'm sure there are more well-known good examples that are great for your purposes, but here's one from my field:

For $\varepsilon_0$, a nice order on finite sequences of natural numbers is the Primitive Sequence System (abbreviated as PrSS). It sort of encodes iterated Cantor Normal Form, but it also has an interpretation that doesn't involve that.

The order is lexicographical (from left to right, so $(0,1,2,0)$ is larger than $(0,1,1,1,1)$), and the sequences in the ordered set are precisely the sequences that can be obtained from sequences of the form $(0,1,2,\ldots,n)$ by repeatedly applying something called "expansion" (which is basically like taking an element of a fundamental sequence):

Given a sequence $S$, we can expand it by any natural number $m$ to get a smaller sequence $S[m]$. To find $S[m]$, we let $x$ be the last number in $S$. If $x=0$, then $S[m]$ is just $S$ without $x$. Otherwise, we let $y$ be the last number in $S$ smaller than $x$, and let $B$ be the subsequence of $S$ from $y$ to the number right before $x$. Then $S[m]$ is obtained from $S$ by replacing $x$ with $m$ copies of $B$.

For example, if we want to get $(0,1,2)[3]$, the last number $x$ is $2$, the last number in $S$ smaller than $2$ is the $1$, and $B$ is the subsequence from the $1$ to the $1$, which is just $(1)$, so we replace the $2$ with $3$ copies of $(1)$, and we get $(0,1,1,1,1)$. If we want to find $(0,1,1,1,1)[2]$, then the last number is the $1$ at the end, the last number smaller than $1$ is the $0$, so then $B$ is the subsequence from the $0$ to the third $1$, which means $B$ is $(0,1,1,1)$. Replacing the $1$ at the end with $2$ copies of $(0,1,1,1)$ gives us $(0,1,1,1,1)[2] = (0,1,1,1,0,1,1,1,0,1,1,1)$.

It may take a while to get the hang of this, but once the sequences seem readable, here's why it's nice:

1. If you replace each number $n$ with an $\omega$ at "height" $n$ (where the height increases by 1 when you go into an exponent), put $0$ in the exponent of each $\omega$ that has an empty exponent, and put pluses where they're necessary (before each $\omega$ that isn't the first in the exponent of some other $\omega$, and isn't the first in the whole expression), you get precisely the ordinal corresponding to the sequence (i.e. the order type of the set of smaller sequences), which means this is a concise one-line way of encoding iterated Cantor Normal Form.

2. It is the perfect first example of reflection properties appearing in well-orders of sequences. Reflection properties are properties of ordered sets $(X,<)$ with additional structure (relations, possibly operators and constants) including a relation $R$. A reflection property then roughly says that whenever we have a finite set $Y\subseteq X$, and some $y\in Y$ has the relation $R(y,x_1,x_2,\ldots,x_n)$ with some $x_1,x_2,\ldots,x_n$ in $X$ (not necessarily in $Y$), then we can find copies of $Y$ below $y$ that are isomorphic to it except for that one relation $R(y,x_1,x_2,\ldots,x_n)$ which doesn't need to be preserved by the "almost" isomorphism.

In our case, the ordered set $(X,<,R)$ is somewhat abstract, but finite subsets of $X$ represent the sequences from PrSS, and each number in one of those sequences represents an element of $X$, with $<$ being the order in which the corresponding numbers appear in the sequence. The relation $R$ will just take two inputs, and in the interpretation of $Y\subseteq X$ as a sequence $S$, $R(y,x)$ represents that $y$ is the last element of $S$ before $x$ that is smaller than $x$. Then the expansion $S[m]$ is basically just repeatedly applying the reflection property with the $y,x$ described in the definition of expansion and taking the union of the resulting almost-isomorphic set $Y'$ with the original $Y$ to get a new $Y$ to reflect, doing all of this $m$ times and then removing $x$.

This set $(X,<,R)$ also corresponds to $\Sigma_1$-stability, but i won't get into the details of that now. Maybe i'll edit this later to add that.

Answer 2

I will use $\sim$ as an abbreviation for "corresponds to", and $\underline{\alpha}$ as an abbreviation for the set of tuples that corresponds to $\underline{\alpha}$ First, the tuple idea can be made a little more elegant by only considering tuples whose first element is not zero. Extending this, we can write $\{(a_n,n),(a_{n-1},n-1),...,(a_1,1),(a_0,0)\}$ for the tuple $(a_n,a_{n-1},...,a_1,a_0)$, omitting the $a_i$ which are equal to zero. However, since $\{(x,0)\}\sim x$ for $x>0$, and $\varnothing\sim 0$ a natural extension is to write $\{(1,\{(1,\underline{1})\})\} = \{(1,\{(1,\{(1,\varnothing)\})\})\}$ for $\omega^\omega$. This can continue on until $\varepsilon_0$.

Let $$T_0=\{\varnothing\} \\ T_{n+1} = \{\{(a_0,X_0),(a_1,X_1),...,(a_k,X_k)\}\mid a_0,a_1,...a_k > 0\land\\ X_0,X_1,...,X_k \in T_n\mid X_0\neq X_1\neq...\neq X_k \land k>0\} \\ T = \bigcup_{i\in\omega}T_i$$ Then we can define an order $<$ on $T$ as follows:

1. For all $x$, $x < \varnothing$ is false.
2. For all $y\neq \varnothing$, $\varnothing < y$ is true.
3. If $x, y$ are $\{(a,X),...\}, \{(b,Y),...\}$ with $X\neq Y$ where $X$ and $Y$ are the maximal elements of $(\{v\mid\exists a\text{:}(a,v)\in x\},<)$ and $(\{u\mid \exists a\text{:}(a,u)\in y\},<)$ respectively, then $x<y$ is equivalent to $X < Y$.
4. If $x, y$ are $\{(a,X),...\}, \{(b,X),...\}$ with $a \neq b$ where $X$ is the maximal element of both $(\{v\mid\exists a\text{:}(a,v)\in x\},<)$ and $(\{u\mid \exists a\text{:}(a,u)\in y\},<)$, then $x<y$ is equivalent to $a < b$.
5. Otherwise, $x, y$ must be $\{(a,X),...\}, \{(a,X),...\}$ where $X$ is the maximal element of both of the aforementioned sets. In this case, $x < y$ is equivalent to $x\setminus \{(a,X)\} < y\setminus \{(a,X)\}$.

Then, $(T,<)$ is isomorphic to $\varepsilon_0$.

Answer 3

Although this may be considered un-natural, Gerhardt Gentzen introduced an ordinal notation via isomorphism to iterated Cantor normal form for his ordinal analysis of Peano arithmetic like so:

• $0$ is standard

• If $a_1, a_2, \cdots, a_n$ are standard and $a_n \preceq \cdots \preceq a_2 \preceq a_1$ then $2^{a_1+1} 3^{a_2+1} \cdots p_n^{a_n+1}$ is standard where $p_i$ is the $i$th prime.

• $0 \preceq n$ for all $n$.

• $2^{a_1+1} 3^{a_2+1} \cdots p_n^{a_n+1} \preceq 2^{b_1+1} 3^{b_2+1} \cdots p_m^{b_m+1}$ iff ($a_1 \preceq b_1$ and $a_1 \neq b_1$) or ($a_1 = b_1$ and $2^{a_2+1} \cdots p_{n-1}^{a_n+1} \preceq 2^{b_2+1} \cdots p_{m-1}^{b_m+1}$)

The mapping $o: (\mathbb{N}_{\mathrm{std}}, \preceq) \to (\varepsilon_0, \leq)$, where $\mathbb{N}_{\mathrm{std}}$ is the set of standard terms, defined as $o(0) = 0$ and $o(2^{a_1+1} 3^{a_2+1} \cdots p_n^{a_n+1}) = \omega^{o(a_1)} + \omega^{o(a_2)} + \cdots + \omega^{o(a_n)}$, is an order-isomorphism, and we can verify this like so:

First, we prove $o$ is injective. Assume $o(x) = o(y)$. Either:

• $o(x) = o(y) = 0$. Since $o(x) = 0$ iff $x = 0$, we have $x = y = 0$ and so $x = y$.
• $x = 2^{a_1+1} 3^{a_2+1} \cdots p_n^{a_n+1}$ and $y = 2^{b_1+1} 3^{b_2+1} \cdots p_m^{a_m+1}$. Since $o(x) = o(y)$, We have $\omega^{o(a_1)} + \omega^{o(a_2)} + \cdots + \omega^{o(a_n)} = \omega^{o(b_1)} + \omega^{o(b_2)} + \cdots + \omega^{o(b_m)}$, and these are both written in Cantor normal form, therefore they must be equal.

Now, we prove $o$ is surjective. We proceed by transfinite induction, letting $\alpha < \varepsilon_0$. If $\alpha = 0$, then $o(0) = \alpha$. Else, $\alpha > 0$, and so the CNF theorem guarantees we can write $\alpha = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ where $\alpha > \alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$ and $n > 0$. By the induction hypothesis, there are $a_1, a_2, \cdots, a_n$ so that $o(a_m) = \alpha_m$ for all $1 \leq m \leq n$. Then $o(2^{a_1+1} 3^{a_2+1} \cdots p_n^{a_n+1}) = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n} = \alpha$.

Verifying that $o$ preserves order is also easy.

For example:

• $1$ corresponds to $2$.
• $2$ corresponds to $6$.
• $\omega$ corresponds to $8$.
• $\omega^2$ corresponds to $128$.
• $\omega^\omega$ corresponds to $512$.
• $\omega^{\omega 2}+\omega^{\omega+1}+\omega^3+\omega^2 2+4$ corresponds to $2^{2^{10077697}+1} 3^{2^{24}+1} 5^{2^{30}+1} 7^{129} 11^{129} 13^3 17^3 23^3 29^3$

In conclusion, this is a straightforward way of encoding ordinals below $\varepsilon_0$ into natural numbers via prime factorisation and iterated Cantor normal form.