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

30 Jan 2015

It is well-known that the cartesian product of two infinite sets of cardinality $\aleph_{\alpha}$ is also of cardinality $\aleph_{\alpha}$. Equivalently, the set $\omega_{\alpha}\times\omega_{\alpha}$ can be well-ordered in order-type $\omega_{\alpha}$. However, the standard ordering on $\omega_{\alpha}\times\omega_{\alpha}$ does not work, since it is always of order type $\omega_{\alpha}^{2}$. Instead, we introduce for each ordinal $\alpha$ the canonical well-ordering of $\alpha\times\alpha$ as follows: ${(\xi_{1},\xi_{2})}\lhd{(\eta_{1},\eta_{2})}$ if either ${\max{(\xi_{1},\xi_{2})}}<{\max{(\eta_{1},\eta_{2})}}$ or ${\max{(\xi_{1},\xi_{2})}}={\max{(\eta_{1},\eta_{2})}}$ but $(\xi_{1},\xi_{2})$ precedes $(\eta_{1},\eta_{2})$ lexicographically. If we note $\gamma(\alpha)$ the ordinal isomorphic to that well-ordering ordering, then we can prove that $\gamma(\omega_{\alpha})=\omega_{\alpha}$ as wanted (see Corollary 0.4).

Jech’s Set Theory book contains several properties of $\gamma$. For example, $\gamma$ is increasing : for any ordinal $\alpha$, $\alpha\times\alpha$ is a (proper) initial segment of ${(\alpha+1)}\times{(\alpha+1)}$ and of $\lambda\times\lambda$ for any limit ordinal $\lambda>\alpha$. As a consequence, $\forall\alpha,\alpha\leq\gamma(\alpha)$ which can also trivially be seen by the increasing function $\xi\mapsto(\xi,0)$ from $\alpha$ to $\alpha\times\alpha$. Also, $\forall\alpha,\gamma(\alpha)<\gamma(\lambda)$ implies $\sup_{\alpha<\lambda}{\gamma(\alpha)}\leq\gamma(\lambda)$. This can not be a strict equality, or otherwise the element ${(\xi,\eta)}\in\lambda\times\lambda$ corresponding to $\sup_{\alpha<\lambda}{\gamma(\alpha)}$ via the isomorphism between $\lambda\times\lambda$ and $\gamma(\lambda)$ would be an element larger than all $(\alpha,\alpha)$ for $\alpha<\lambda$. Hence $\gamma$ is continuous and by exercise 2.7 of the same book, $\gamma$ has arbitrary large fixed points. Exercise 3.5 shows that $\gamma(\alpha)\leq\omega^{\alpha}$ and so $\gamma$ does not increase cardinality (see Corollary 0.2 for a much better upper bound). Hence starting at any infinite cardinal $\kappa$ the construction of exercise 2.7 provides infinitely many fixed points of $\gamma$ having cardinality $\kappa$. Hence the infinite fixed points of $\gamma$ are not just cardinals and we can wonder what they are exactly…

I recently tried to solve Exercise I.11.7 of Kunen’s Set Theory book which suggests a nice characterization of infinite fixed points of $\gamma$: they are the ordinals of the form $\omega^{\omega^{\alpha}}$. However, I could not find a simple proof of this statement so instead I tried to determine the explicit expression of $\gamma(\alpha)$, from which the result becomes obvious (see Corollary 0.3). My final calculation is summarized in Theorem 0.1, which provides a relatively nice expression of $\gamma(\alpha)$. Recall that any $\alpha\geq 1$ can be written uniquely as $\alpha=\omega^{\beta}q+\rho$ where $\beta$ is (following Kunen’s terminology) the “logarithm in base $\omega$ of $\alpha$” (that we will denote $\log_{\omega}{\alpha}$ for $\alpha\geq\omega$) and $q,\rho$ are the quotient and remainder of the Euclidean division of $\alpha$ by $\omega^{\beta}$. Alternatively, this can be seen from Cantor’s Normal Form: $\beta$ and $q$ are the exponent and coefficient of the largest term while $\rho$ is the sum of terms of smaller exponents.

Theorem 0.1.

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.

In a future blog post ;-) ∎

From this theorem, we deduce several corollaries:

Corollary 0.2.

For any ordinal $\alpha$, we have

$$\alpha\leq{\gamma(\alpha)}\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\left({\alpha-r}\right)}+{\alpha\cdot{2r}}}\leq\alpha\left(\alpha+r\right)$$

where $r=\alpha\mod\omega$ is the remainder in the Euclidean division of $\alpha$ by $\omega$ (i.e. the constant term in the Cantor Normal Form).

Proof.

The “Limit Ordinals” case is $r=0$ i.e. $\alpha\leq{\gamma(\alpha)}\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\alpha}}$, which is readily seen by the previous theorem. Then we deduce for the “Infinite Successor Ordinals” case: ${\gamma(\alpha+n)}=\gamma(\alpha)+{\alpha\cdot{2n}}+n\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\alpha}}+{\left(\alpha+n\right)\cdot{2n}}$ where ${\log_{\omega}(\alpha+n)}={\log_{\omega}(\alpha)}$ and $n=\left(\alpha+n\mod\omega\right)$. Since $\omega^{\log_{\omega}(\alpha)}\leq\alpha$ we can write ${{\omega^{\log_{\omega}(\alpha)}\cdot\left({\alpha-r}\right)}+{\alpha\cdot{2r}}}\leq{\alpha\cdot\left(\alpha-r+2r\right)}={\alpha\cdot{(\alpha+r)}}$. ∎

Hence the order type of the canonical ordering $\lhd$ of $\alpha\times\alpha$ (i.e. $\gamma(\alpha)\leq\alpha{(\alpha+\omega)}$) is never significantly bigger than the one of the standard lexical ordering (i.e. $\alpha^{2}$), and even never larger for limit ordinals. Moreover, for many ordinals $\alpha$ the canonical ordering is of order type $\alpha$:

Corollary 0.3.

The fixed points of $\gamma$ are $0,1$ and $\omega^{\omega^{\alpha}}$ for all ordinals $\alpha$.

Proof.

For the “Finite Ordinals” case, we have $\gamma(n)=n^{2}=n$ iff $n=0$ or $n=1$. For the “Infinite Successor Ordinals” case, we have $\alpha\cdot{2n}>\alpha$ if $n\geq 1$ so $\gamma(\alpha+n)>\alpha+n$. Now we look at the three subcases of the “Limit Ordinals” case. For the first one, we have $\log_{\omega}(\alpha)\geq 1$ and so $\omega^{\log_{\omega}(\alpha)}\alpha\geq\omega\alpha>\alpha$. For the second one, we note that ${\log_{\omega}(\alpha)}2>\log_{\omega}(\alpha)$ and so $\omega^{{\log_{\omega}(\alpha)}2}>\alpha$ (compare the Cantor Normal Form). Since $n-1\geq 1$ by assumption, we have $\gamma(\alpha)>\alpha$. Similarly in the third case, if we expand the parenthesis the first term is $\omega$ raised to the power ${\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left(2m-1\right)}$ which is stricly greater than $\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}m$ if $m\geq 2$. Now if $m=1$, we obtain $\gamma(\alpha)={\omega^{\log_{\omega}(\alpha)}+{\omega^{\log_{\omega}(\alpha)}\rho}}$ and $\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho$. Hence $\gamma(\alpha)>\alpha$ if $\rho>0$ and $\gamma(\alpha)=\alpha$ if $\rho=0$. Finally for $\alpha\geq\omega$, $\gamma(\alpha)=\alpha$ iff $\alpha=\omega^{\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}}$ iff $\alpha=\omega^{\omega^{\beta}}$ for some ordinal $\beta$. ∎

Finally, now that we know that infinite fixed points of $\gamma$ are of the form $\alpha=\omega^{\omega^{\beta}}$ we only need to verify that infinite cardinals $\kappa$ are of this form to prove that ${|\kappa\times\kappa|}=\kappa$. This provides an alternative (less straightforward) proof of Theorem 3.5 from Jech’s Set Theory book.

Corollary 0.4.

Any infinite cardinal $\kappa$ is a fixed point of $\gamma$. Hence for any infinite cardinal $\kappa_{1},\kappa_{2}$ we have

$$\kappa_{1}+\kappa_{2}=\kappa_{1}\kappa_{2}={\max(\kappa_{1},\kappa_{2})}$$

Proof.

For any cardinal infinite cardinal $\mu$ that is a fixed point of $\gamma$, the canonical well-ordering provides a bijection between $\mu$ and $\mu\times\mu$ i.e. $\mu^{2}=\mu$. Hence if $\mu_{1}\leq\mu_{2}$ are two fixed points, we have

$$\mu_{2}\leq{\mu_{1}+\mu_{2}}\leq{\mu_{1}\mu_{2}}\leq\mu_{2}^{2}=\mu_{2}$$

Suppose that there is a cardinal $\kappa$ which is not a fixed point of $\gamma$ and consider the smallest one. Then any infinite cardinal below $\kappa$ is a fixed point of $\gamma$ and the previous equality is still true below $\kappa$.

Suppose $\kappa>\omega^{\log_{\omega}{\kappa}}$ and write $\kappa=\omega^{\log_{\omega}{\kappa}}+\rho$ where $\rho<\kappa$ corresponds to the remaining terms in Cantor Normal Form. Then $\aleph_{0}\leq\mu_{1}=\left|\omega^{\log_{\omega}{\kappa}}\right|<\kappa$, $\mu_{2}={|\rho|}<\kappa$ and $\mu_{1}+\mu_{2}=\kappa$. But the two first relations imply $\mu_{1}+\mu_{2}=\max(\mu_{1},\mu_{2})<\kappa$ which contradicts the third one. Hence $\kappa=\omega^{\log_{\omega}{\kappa}}$.

Now suppose $\log_{\omega}{\kappa}>\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}$ and write $\log_{\omega}{\kappa}=\omega^{\log_{\omega}{\kappa}}+\rho$ where $\rho<\log_{\omega}{\kappa}$ corresponds to the remaining terms in Cantor Normal Form. Then we have

$$\kappa=\omega^{\log_{\omega}{\kappa}}=\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}\omega^{\rho}$$

where $\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}<\omega^{\log_{\omega}{\kappa}}=\kappa$ and $\omega^{\rho}<\omega^{\log_{\omega}{\kappa}}=\kappa$ since $\alpha\mapsto\omega^{\alpha}$ is strictly increasing. Then $\aleph_{0}\leq\mu_{1}=\left|\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}\right|<\kappa$, $\mu_{2}={|\omega^{\rho}|}<\kappa$ and $\mu_{1}\mu_{2}=\kappa$. But again, the two first relations imply $\mu_{1}\mu_{2}=\max(\mu_{1},\mu_{2})<\kappa$ which contradicts the third one.

Finally, $\kappa=\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}$ and so is a fixed point of $\gamma$, a contradiction. Hence all the infinite cardinals are fixed point of $\gamma$ and so the property stated at the beginning is true for arbitrary infinite cardinals $\mu_{1},\mu_{2}$. ∎