The canonical well-ordering of α×α (part 2)

31 Jan 2015

In a my previous blog post, I discussed the canonical well-ordering on $\alpha\times\alpha$ and stated theorem 0.5 below to calculate its order-type $\gamma(\alpha)$. Subsequent corollaries provided a bound for $\gamma(\alpha)$, its fixed points and a proof that infinite cardinals were among these fixed points (and so that cardinal addition and multiplication is trivial). In this second part, I’m going to provide the proof of this theorem.

First, we note that for all $n<\omega$, there is only one order-type for $n\times n$, since the notion of cardinal and ordinal is the same for finite sets. So indeed

$$\forall n<\omega,\gamma(n)={|n\times n|}=n^{2}$$

and taking the limit, we get our first infinite fixed point:

$$\gamma(\omega)=\sup_{n<\omega}{\gamma(n)}=\omega$$

For all $\alpha$ the ordering on ${(\alpha+1)}\times{(\alpha+1)}$ is as follows: first the elements of $\alpha\times\alpha$ ordered as $\gamma(\alpha)$, followed by the elements $(\xi,\alpha)$ for $0\leq\xi<\alpha$, followed by the elements $(\alpha,\xi)$ for $0\leq\xi\leq\alpha$. Hence

$$\forall\alpha,{\gamma(\alpha+1)}={\gamma(\alpha)}+\alpha\cdot 2+1$$

From this, we can try to calculate the next values of $\gamma$ after $\omega$:

$${\gamma(\omega+1)}=\omega+{\omega\cdot 2}+1={\omega\cdot 3}+1$$

$${\gamma(\omega+2)}={\omega\cdot 3+1}+\omega+1+\omega+1+1={\omega\cdot 5}+2$$

The important point is $1+\omega=\omega$ ; in general we will use several times the property $\alpha+\omega^{\beta}=\omega^{\beta}$ if $\alpha<\omega^{\beta}$. By a simple recurrence (see proposition 0.1), we can generalize the expression to arbitrary $n$:

$${\gamma(\omega+n)}=\omega\left(2n+1\right)+n$$

and so taking the limit

$${\gamma(\omega\cdot 2)}=\omega^{2}$$

which is a limit ordinal not fixed by $\gamma$. We note another point that will be used later: taking the limit “eliminates” the smallest terms. More generally, we can perform the same calculation, starting from any arbitrary $\alpha\geq\omega$:

Proposition 0.1.

For any limit ordinal $\alpha$ and $1\leq n<\omega$ we have

$$\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n$$

Proof.

For $n=1$ this is the relation for $\gamma(\alpha+1)$ explained above. If the relation is true for $n$ then

$$\gamma(\alpha+n+1)=\gamma(\alpha+n)+{\left(\alpha+n\right)\cdot 2}+1$$

$$\gamma(\alpha+n+1)=\gamma(\alpha)+{\alpha\cdot{2n}}+n+\alpha+n+\alpha+n+1$$

and since $\alpha\geq\omega$ we have $n+\alpha=\alpha$ and so

$$\gamma(\alpha+n+1)=\gamma(\alpha)+{\alpha\cdot{(2n+1)}}+n+1$$

Which shows the result at step $n+1$. ∎

As above, we can take the limit and say ${\gamma(\alpha+\omega)}=\sup_{n<\omega}{\gamma(\alpha+n)}=\gamma(\alpha)+\alpha\cdot\omega$ which is consistent with ${\gamma(\omega\cdot 2)}=\omega+\omega^{2}=\omega^{2}$. However, if we consider the Cantor Normal Form $\alpha=\omega^{\beta_{1}}n_{1}+...+\omega^{\beta_{k}}n_{k}$, then for all $n<\omega$ we have can use the fact that “$\omega^{\beta_{1}}$ will eliminate smaller terms on its left” that is $\alpha\cdot n=\omega^{\beta_{1}}{(n_{1}n)}+\omega^{\beta_{2}}n_{2}+...+\omega^{\beta_{k}}n_{k}$. Then using the fact that “taking the limit eliminates the smallest terms” we get $\alpha\cdot\omega=\sup_{n<\omega}\alpha\cdot n=\omega^{\beta_{1}+1}$. So actually, we have a nicer formula where $\alpha\cdot\omega$ is put in Cantor Normal Form:

$$\forall\alpha\geq\omega,{\gamma(\alpha+\omega)}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+1}$$

This can be generalized by the following proposition:

Proposition 0.2.

For any $\alpha\geq\omega$ and $\beta\geq 1$ such that $\log_{\omega}(\alpha)+1\geq\beta$ we have

$${\gamma(\alpha+\omega^{\beta})}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta}$$

Proof.

We prove by induction on $\beta$ that for all such $\alpha$ the expression is true. We just verified $\beta=1$ and the limit case is obvious by continuity of $\gamma$ and of the sum/exponentiation in the second variable. For the successor step, if $\log_{\omega}(\alpha)+1\geq\beta+1$ then a fortiori $\forall 1\leq n<\omega,\log_{\omega}(\alpha+\omega^{\beta}\cdot n)+1\geq\beta+1\geq\beta$. We can then use the induction hypothesis to prove by induction on $1\leq n<\omega$ that ${\gamma(\alpha+{\omega^{\beta}\cdot n})}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta}\cdot n$. For $n=1$, this is just the induction hypothesis of $\beta$ (for the same $\alpha$!). For the successor step, we need to use the induction hypothesis of $\beta$ (for $\alpha+\omega^{\beta}\cdot n$) which is ${\gamma(\alpha+{\omega^{\beta}\cdot{(n+1)}})}={\gamma(\alpha+{\omega^{\beta}\cdot n})}+\omega^{\log_{\omega}(\alpha)+\beta}$. Finally, ${\gamma(\alpha+{\omega^{\beta+1}})}={\sup_{1\leq n<\omega}{\gamma(\alpha+{\omega^{\beta}\cdot n})}}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta+1}$, as wanted. ∎

For all $\alpha\geq 1$, $\log_{\omega}(\omega^{\alpha})+1=\alpha+1$ so the previous paragraph also gives ${\gamma(\omega^{\alpha+1})}=\gamma\left(\omega^{\alpha}+\omega^{\alpha+1}\right)={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2+1}$. Then, we find

$$\gamma(\omega^{2})=\omega+\omega^{3}=\omega^{3}$$

$$\gamma(\omega^{3})=\omega^{3}+\omega^{5}=\omega^{5}$$

And more generally by induction on $n<\omega$, we can show that

$$\gamma(\omega^{n+1})=\omega^{2n+1}$$

Then we deduce another fixed point

$$\gamma(\omega^{\omega})={\sup_{1\leq n<\omega}\gamma\left({\omega^{n}}\right)}=\omega^{\omega}$$

The following proposition tries to generalize the expression of ${\gamma(\omega^{\alpha+1})}$.

Proposition 0.3.

For any $\alpha,\beta\geq 1$ such that $\log_{\omega}(\alpha)>\log_{\omega}(\beta)$ we have

$${\gamma(\omega^{\alpha+\beta})}={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2+\beta}$$

Proof.

This is done by induction on $\beta<\alpha$ for a fixed $\alpha$. We already verified the case $\beta=1$ in the previous paragraph and the limit case is obvious by continuity of $\gamma$ and of the sum/exponentiation in the second variable. For the successor step, we have ${\gamma(\omega^{\alpha+\beta+1})}={\gamma(\omega^{\alpha+\beta})}+\omega^{{(\alpha+\beta)}\cdot 2+1}$ and by induction hypothesis, ${\gamma(\omega^{\alpha+\beta})}={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2+\beta}$. Since $\log_{\omega}(\alpha)>\log_{\omega}(\beta+1)=\log_{\omega}(\beta)$ we have ${(\alpha+\beta)}\cdot 2+1=\alpha+\beta+\alpha+\beta+1=\alpha\cdot 2+\beta+1>\alpha\cdot 2+\beta$ and so $\omega^{\alpha\cdot 2+\beta}+\omega^{\alpha\cdot 2+\beta+1}=\omega^{\alpha\cdot 2+\beta+1}$. Finally, ${\gamma(\omega^{\alpha+\beta+1})}={\gamma(\omega^{\alpha+\beta})}+\omega^{\alpha\cdot 2+\beta+1}$ as wanted. ∎

For any $1\leq n<\omega$ and $\alpha\geq 1$, if $1\leq\beta<\omega^{\alpha}$ then $\log_{\omega}(\beta)<\alpha=\log_{\omega}(\omega^{\alpha}\cdot n)$. Hence proposition 0.3 gives ${\gamma(\omega^{{\omega^{\alpha}\cdot n}+\beta})}={\gamma(\omega^{{\omega^{\alpha}\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{2n}}+\beta}$ Then by continuity of $\gamma$ and of the sum/exponentiation in the second variable, we can consider the limit $\beta\rightarrow\omega^{\alpha}$ to get ${\gamma(\omega^{{\omega^{\alpha}\cdot(n+1)}})}={\gamma(\omega^{{\omega^{\alpha}\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{(2n+1)}}}$. So continuing our calculation we have

$${\gamma(\omega^{\omega\cdot 2})}=\omega^{\omega}+\omega^{\omega\cdot 3}=\omega^{\omega\cdot 3}$$

$${\gamma(\omega^{\omega\cdot 3})}=\omega^{\omega\cdot 3}+\omega^{\omega\cdot 5}=\omega^{\omega\cdot 5}$$

and taking the limit we find another fixed point

$${\gamma(\omega^{\omega^{2}})}=\omega^{\omega^{2}}$$

then again

$${\gamma(\omega^{\omega^{2}\cdot 2})}=\omega^{\omega^{2}}+\omega^{\omega^{2}\cdot 3}=\omega^{\omega^{2}\cdot 3}$$

$${\gamma(\omega^{\omega^{2}\cdot 3})}=\omega^{\omega^{2}\cdot 3}+\omega^{\omega^{2}\cdot 5}=\omega^{\omega^{2}\cdot 5}$$

and taking the limit we find another fixed point

$${\gamma(\omega^{\omega^{3}})}=\omega^{\omega^{3}}$$

More generally, we have the following proposition:

Proposition 0.4.

For any ordinal $\alpha$ and $1\leq n<\omega$ we have

$${\gamma(\omega^{{\omega^{\alpha}\cdot n}})}=\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}$$

Proof.

From the relation ${\gamma(\omega^{{\omega^{\alpha}\cdot(n+1)}})}={\gamma(\omega^{{\omega^{\alpha}\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{(2n+1)}}}$, we deduce by induction on $n$ that

$$\forall n\geq 2,{\gamma(\omega^{{\omega^{\alpha}\cdot n}})}={\gamma(\omega^{{\omega^{\alpha}}})}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}$$

Taking the limit $n\rightarrow\omega$,we obtain

$${\gamma(\omega^{{\omega^{\alpha+1}}})}={\gamma(\omega^{{\omega^{\alpha}}})}+\omega^{{\omega^{\alpha+1}}}$$

We can then show by induction that all the $\omega^{\omega^{\alpha}}$ are actually fixed points, using the previous relation at successor step, the continuity of $\gamma$ at limit step and the fact that $\gamma(\omega)=\omega$. This means

$${\gamma(\omega^{{\omega^{\alpha}}})}=\omega^{{\omega^{\alpha}}}=\omega^{{\omega^{\alpha}\cdot{(2\times 1-1)}}}$$

Then for $n\geq 2$, we get

$${\gamma(\omega^{{\omega^{\alpha}\cdot n}})}={\gamma(\omega^{{\omega^{\alpha}}})}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}={\omega^{{\omega^{\alpha}}}}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}=\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}$$

∎

Equipped with these four propositions, we have a way to recursively calculate $\gamma$. We are ready to prove the main theorem:

Theorem 0.5.

For all ordinal $\alpha$, we denote $\gamma(\alpha)$ the order-type of the canonical ordering of $\alpha\times\alpha$. Then $\gamma$ can be calculated as follows:

1. 1.

   Finite Ordinals: For any $n<\omega$ we have

   $$\gamma(n)=n^{2}$$

2. 2.

   Limit Ordinals: For any limit ordinal $\alpha$,

   1. (a)

      If $\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}$ does not divide $\log_{\omega}(\alpha)$ then

      $$\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\alpha$$

   2. (b)

      Otherwise, we write $\alpha={\omega^{\log_{\omega}(\alpha)}n}+\rho$ for some $n\geq 1$. If $n\geq 2$ then

      $$\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left({\omega^{\log_{\omega}(\alpha)}\cdot{(n-1)}}+\rho\right)$$

      (like the first case but we “decrement $n$ in the second factor”)

   3. (c)

      Otherwise, $\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho$ and we write $\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}m$ for some $m\geq 1$. We have

      $$\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left(\omega^{\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left(m-1\right)}+\rho\right)$$

      (like the first case but we “decrement $m$ in the second factor”)

3. 3.

   Infinite Successor Ordinals: For any limit ordinal $\alpha$ and $1\leq n<\omega$ we have

   $$\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n$$

   where $\gamma(\alpha)$ is determined as in the previous point.

Proof.

The “Finite Ordinals” has been discussed at the beginning and the “Infinite Successor Ordinals” is proposition 0.1. Now let’s consider the Cantor Normal Form $\omega^{\beta_{1}}n+...+\omega^{\beta_{k}}n_{k}$ of a limit ordinal $\alpha\geq\omega$ (so $\beta_{k}\geq 1$ and $\beta_{1}=\log_{\omega}(\alpha)$). First, from proposition 0.2 we can make successively extract the $n_{k}$ terms $\omega^{\beta_{k}}$ (by left-multiplying them by $\omega^{\beta_{1}}$), then the $n_{k-1}$ terms $\omega^{\beta_{k-1}}$, … then the $n_{2}$ terms $\omega^{\beta_{2}}$ and finally $n-1$ terms $\omega^{\beta_{1}}$. We obtain:

$${\gamma(\alpha)}={\gamma(\omega^{\beta_{1}})}+{\omega^{\beta_{1}}\left(\omega^{\beta_{1}}{(n-1)}+\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}\right)}$$

We now write $\beta_{1}=\omega^{\delta}m+\sigma$ where $\delta=\log_{\omega}{\beta_{1}}$ and $m,\sigma$ are the quotient and remainder of the Euclidean division of $\beta_{1}$ by $\omega^{\delta}$. We can then use proposition 0.3 to extract $\sigma$:

$$\sigma=0\implies{\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}$$

$$\sigma\neq 0\implies{\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}+\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}$$

Finally, using proposition 0.4 we obtain

$${\gamma(\omega^{\omega^{\delta}m})}=\omega^{{\omega^{\delta}\cdot{(2m-1)}}}$$

$\sigma\neq 0$ means that $\omega^{\delta}=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}$ does not divide $\beta_{1}={\log_{\omega}(\alpha)}$. In that case, $\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}>\omega^{{\omega^{\delta}\cdot{(2m-1)}}}$ and so ${\gamma(\omega^{\beta_{1}})}=\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}$. We note that $\beta_{1}\cdot 2=\omega^{\delta}m+\sigma+\omega^{\delta}m+\sigma=\omega^{\delta}{(2m)}+\sigma$ since the remainder $\sigma$ is less than $\omega^{\delta}$. So actually ${\gamma(\omega^{\beta_{1}})}=\omega^{\beta_{1}}\omega^{\beta_{1}}$. Coming back to the expression of $\gamma(\alpha)$, this term can be grouped with $\omega^{\beta_{1}}{(n-1)}$ to recover the Cantor Normal Form of $\alpha$ and we finally get $\gamma(\alpha)=\omega^{\beta_{1}}\alpha$.

Otherwise, $\sigma=0$, $\beta_{1}=\omega^{\delta}m$ and

$${\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}=\omega^{{\omega^{\delta}\cdot{(2m-1)}}}={\omega^{\beta_{1}}{\omega^{\omega^{\delta}\cdot{(m-1)}}}}$$

But then $\beta_{1}=\omega^{\delta}m>{\omega^{\delta}{(m-1)}}$ and so $\omega^{\beta_{1}}\omega^{\beta_{1}}>\omega^{\beta_{1}}\omega^{{\omega^{\delta}\cdot{(m-1)}}}$. Hence if $n\geq 2$, the term ${\gamma(\omega^{\beta_{1}})}$ is eliminated in the expression of $\gamma(\alpha)$ and it remains

$${\gamma(\alpha)}={\omega^{\beta_{1}}\left(\omega^{\beta_{1}}{(n-1)}+\rho\right)}$$

where $\rho=\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}$. If instead $n=1$, then the term $\omega^{\beta_{1}}{(n-1)}$ is zero and it remains

$${\gamma(\alpha)}={\omega^{\beta_{1}}\left(\omega^{{\omega^{\delta}\cdot{(m-1)}}}+\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}\right)}$$

∎