How to compare ordinal numbers?

Question

There is a theorem which says given any two ordinals $\alpha$ and $\beta$, exactly one of the following holds: $\alpha\in\beta$, or $\beta\in\alpha$, or $\alpha=\beta$.

But is there an algorithm to compare any two ordinals?

For example, how do I compare $(\omega\times 2)\omega^\omega$ and $\omega^\omega\times 2$?

Answer 1

If you are talking specifically about notation using addition, multiplication, exponentiation and symbols like $\omega$ and finite ordinals/numbers .... then I think there is no doubt that there should be an algorithm. It would be interesting to see full details of such an algorithm though (because I haven't seen it).

I think there is a recent book which discusses the Cantor's system in a fairly remarkable/full detail (in what seems to be beginner friendly manner). I only know of this particular exposition, which goes in that much detail for $\epsilon_0$ (though I haven't studied it myself in detail).

I don't re-call the exact name now but I would link the name of book in a day or two maybe. But maybe someone else can link to some other good references also in meanwhile because I would be interested in that too.

For your specific example: $$(\omega.2).\omega^\omega=\omega^\omega$$

$$\omega^\omega.2=\omega^\omega+\omega^\omega>\omega^\omega=(\omega.2).\omega^\omega$$

The first equality can be seen pretty much in a similar manner in the other question you asked. Hence we have: $$\omega^\omega.2>(\omega.2).\omega^\omega$$

Edit:

There is a catch in a problem like this I think. Because we are allowing different "strings" of finite symbols to denote the same ordinal ($2.\omega$ is same as $\omega$ and so on), I "think" that a problem like this may be made undecidable (even for recursive ordinals) .... that is in a more general sense. Maybe someone else can elaborate this particular point better and in more detail.

Answer 2

Making SSequence's presumption that the problem is about comparing two expressions built from $\omega$ and finite ordinals using addition, multiplication, exponentiation, and parentheses, there is indeed an algorithm. I will divide the problem into two parts: rewriting an expression in iterated Cantor Normal Form, and comparing two expressions written in iterated Cantor Normal Form.

The Cantor Normal Form theorem states that any ordinal $\alpha > 0$ can be uniquely expressed as a sum $\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ with $\alpha_1 \ge \alpha_2 \ge \cdots \ge \alpha_n$; this is known as the "Cantor Normal Form" of the ordinal. It follows that any ordinal less than $\varepsilon_0$ (the limit of $\omega, \omega^\omega, \omega^{\omega^\omega},\cdots$) can be uniquely written in "iterated Cantor Normal Form", where $\alpha$ is written in iterated in Cantor Normal Form if either:

• $\alpha = 0$ and $\alpha$ is written as $0$.
• $\alpha > 0$, $\alpha$ is written in Cantor Normal Form $\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$, and the $\alpha_i$ are all written in iterated Cantor Normal Form.

(Note: The term "iterated Cantor Normal Form" is as far as I know just something I made up, most people just conflate it with the term "Cantor Normal Form". I don't like doing that since they are two different things.)

So for example:

$\omega^{\omega^{\omega^{\omega^0 + \omega^0} + \omega^0}+ \omega^0 + \omega^0} + \omega^{\omega^0 + \omega^0} + \omega^0$ is an ordinal written in iterated Cantor Normal Form.

$\omega^{\omega^0 + \omega^{\omega^0}}$ is not an expression in iterated Cantor Normal Form, since $\omega^0 + \omega^{\omega^0}$ does not have weakly decreasing exponents.

$\omega^{\omega^0}\cdot 2$ is not iterated Cantor Normal Form, since $\cdot$ and $2$ are not among our base symbols.

However, I will be using a more intuitive version of iterated Cantor Normal Form for our rules: I will be using $1$ as a shorthand for $\omega^0$, since all the $\omega^0$'s get cumbersome. Also, I will consider the expression $\omega$ as iterated Cantor Normal Form, even though it is $\omega^{\omega^0}$ in the formal version when not used as a base in an exponentiation. It is easy to convert this intuitive version to the formal version: just replace $1$ with $\omega^0$, and either replace $\omega$ with $\omega^{\omega^0}$ if it is not being used as a base, or leave it be if it is.

So first, we need an algorithm for rewriting an expression in iterated Cantor Normal Form. First, we don't want any symbols for ordinals other than $\omega$, $0$, or our shorthand $1$ for $\omega^0$, so rewrite any finite ordinal $n > 1$ as $(1+1+\cdots+1)$. Our non-operation symbols $0,1,\omega$ are all written in our intuitive iCNF (iterated Cantor Normal Form), so we just need resolve our operations one at at time (following the parentheses of course) turning two ordinal written in iCNF into one. So we just need rules for each of the three operations.

I will be writing the rules using equations, but we will be using these equations as rules for simplifying our expressions. So for example, the first rule is that $\alpha + 0 = \alpha$; this means that if we are trying to add two expressions in iCNF, and the right term is just $0$, then the resulting expression is the expression $\alpha$.

Some of these rules are inductive, for example the third multiplication rule has $\alpha \cdot \beta = \omega^{[\alpha_1 + \beta_1]}$, but this does not mean that the latter is in iCNF; the brackets indicate that we need to use the addition rule on $\alpha_1 + \beta_1$. The algorithm will still eventually terminate, because the operands for the new operations will have at least one reduced, while the other does not increase, so the well-orderedness of the ordinals will imply eventual termination.

Addition

1. $\alpha + 0 = \alpha$.
2. If $\alpha = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ and $\beta = \omega^{\beta_1} + \omega^{\beta_2} + \cdots + \omega^{\beta_m}$, and $\alpha_1 < \beta_1$, then $\alpha + \beta = \omega^{\beta_1} + \omega^{\beta_2} + \cdots + \omega^{\beta_m}$.
3. If $\alpha = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ and $\beta = \omega^{\beta_1} + \omega^{\beta_2} + \cdots + \omega^{\beta_m}$, and $i$ is the largest integer such that $\alpha_i \ge \beta_1$, then $\alpha + \beta = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_i} + \omega^{\beta_1} + \omega^{\beta_2} + \cdots + \omega^{\beta_m}$.

Multiplication

1. $\alpha \cdot 0 = 0$.
2. $\alpha \cdot 1 = \alpha$.
3. If $\alpha = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ and $\beta = \omega^{\beta_1}$ with $\beta_1 > 0$, then $\alpha \cdot \beta = \omega^{[\alpha_1 + \beta_1]}$
4. If $\beta = \omega^{\beta_1} + \cdots + \omega^{\beta_m}$, then $\alpha \cdot \beta = [ [\alpha \cdot \omega^{\beta_1}] + \cdots + [\alpha \cdot \omega^{\beta_m}] ]$.

Exponentiation

1. $\alpha^0 = 1$.
2. $\alpha^1 = \alpha$.
3. If $\alpha = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ and $\beta = \omega^{\beta_1}$ with $\beta_1 > 0$, then $\alpha^\beta = \omega^{[\alpha_1 \cdot \omega^{\beta_1}]}$.
4. If $\beta = \omega^{\beta_1} + \cdots + \omega^{\beta_m}$, then $\alpha^\beta = [ [\alpha^{\omega^{\beta_1}}] \cdot [\alpha^{\omega^{\beta_2}}] \cdot \ \cdots \ \cdot [\alpha^{\omega^{\beta_m}}]]$.

So that converts any expression to intuitive iCNF, which can easily be converted to formal iCNF. After rewriting two expressions in formal iCNF, comparing them is easy:

1. If both of them are $0$, they are equal.
2. If one is $0$ and the other is not, $0$ is smaller.
3. If $\alpha = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$ and $\beta = \omega^{\beta_1} + \cdots + \omega^{\beta_m}$, compare $\alpha_i$ versus $\beta_i$ starting from $i=1$. Once we reach an $i$ such that $\alpha_i \ne \beta_i$, whichever one is greater will be part of the greater ordinal. If we run out of one set of the exponents and the other continues, then the one that continues is greater. If $n=m$ and $\alpha_i = \beta_i$ for all $i$, the two ordinals are equal.

It is possible to do this for more general expressions, reaching up to larger ordinals, it just gets more and more complicated the higher you go. But, once you reach the Church-Kleene ordinal $\omega_1^{\text{CK}}$, it is not possible to even have a recursive notation for the full set of ordinals, so it is not possible to have an algorithm to compare two ordinals from that set (written in some nonrecursive notation).