canonical ordering on pairs of ordinals

The lexicographic ordering on On$\mathrm{\times }$On, the class of all pairs of ordinals, is a well-order in the broad sense, in that every subclass of On$\mathrm{\times }$On has a least element, as proposition 2 of the parent entry readily shows. However, with this type of ordering, we get initial segments which are not sets. For example, the initial segment of $(1,0)$ consists of all ordinal pairs of the form $(0,\alpha )$, where $\alpha \in$ On, and is easily seen to be a proper class. So the questions is: is there a way to order On$\mathrm{\times }$On such that every initial segment of On$\mathrm{\times }$On is a set? The answer is yes. The construction of such a well-ordering in the following discussion is what is known as the canonical well-ordering of On$\mathrm{\times }$On.

To begin, let us consider a strictly linearly ordered set . We construct a binary relation $\prec$ on $A\times A$ as follows:

For example, consider the usual ordering on $\mathbb{Z}$. Given $(p,q)\in \mathbb{Z}\times \mathbb{Z}$. Suppose $p\le q$. Then the set of all $(m,n)\in \mathbb{Z}\times \mathbb{Z}$ such that $(m,n)\prec (p,q)$ is the union of the three pairwise disjoint sets .

Proposition 1.

. $\mathrm{\prec }$ is a strict linear ordering on $A\mathrm{\times }A$.

Proof.

It is irreflexive because $(a_1,a_2)$ is never comparable with itself. It is linear because, first of all, given $(a_1,a_2)\ne (b_1,b_2)$, exactly one of the three conditions is true, and hence either $(a_1,a_2)\prec (b_1,b_2)$, or $(b_1,b_2)\prec (a_1,a_2)$. It remains to show that $\prec$ is transitive, suppose $(a_1,a_2)\prec (b_1,b_2)$ and $(b_1,b_2)\prec (c_1,c_2)$.

The two cases

1. and $\max \{b_1,b_2\}\le \max \{c_1,c_2\}$,

2. $\max \{a_1,a_2\}\le \max \{b_1,b_2\}$ and ,

produce . Now, assume $\max \{a_1,a_2\}=\max \{b_1,b_2\}=\max \{c_1,c_2\}$, which result in three more cases

1. and $b_1\le c_1$,

2. $a_1\le b_1$ and ,

3. $a_1=b_1=c_1$, and and ,

the first two produce , and the last $a_1=c_1$ and . In all cases, we get $(a_1,a_2)\prec (c_1,c_2)$.∎

Proposition 2.

If is a well-order on $A$, then so is $\mathrm{\prec }$ on $A\mathrm{\times }A$.

Proof.

Let $R\subseteq A\times A$ be non-empty. Let

$$B:=\{\max \{b_1,b_2\}\mid (b_1,b_2)\in R\}.$$

Then $\mathrm{\varnothing }\ne B\subseteq A$, and therefore has a least element $b$, since is a well-order on $A$. Next, let

$$C:=\{c_1\mid \max \{c_1,c_2\}=b,\text{ where }(c_1,c_2)\in R\}.$$

Then $C\ne \mathrm{\varnothing }$, and has a least element $c$. Finally, let

$$D:=\{d_2\mid \max \{c,d_2\}=b,\text{ where }(c,d_2)\in R\}.$$

Again, $D\ne \mathrm{\varnothing }$, so has a least element $d$. So $(c,d)\in R$. We want to show that $(c,d)$ is the least element of $R$.

Pick any $(x,y)\in R$ distinct from $(c,d)$. Then $\max \{x,y\}\in B$ is at least $b=\max \{c,d\}$. If , then $(c,d)\prec (x,y)$. Otherwise, $b=\max \{x,y\}$, so that $x\in C$ is at least $c$. If , then again we have $(c,d)\prec (x,y)$. But if $c=x$, then $y\in D$, so that $d\le y$. Since $(x,y)\ne (c,d)$, and $x=c$, $y\ne d$. Therefore , and $(c,d)\prec (x,y)$ as a result.∎

The ordering relation above can be generalized to arbitrary classes. Since On is well-ordered by $\in$, the canonical ordering on On$\mathrm{\times }$On is a well-ordering by proposition 2. Moreover,

Proposition 3.

Given the canonical ordering $\mathrm{\prec }$ on On$\mathrm{\times }$On, every initial segment is a set.

Proof.

Given ordinals $\alpha ,\beta \in$On, suppose $\lambda =\max \{\alpha ,\beta \}$. The initial segment of $(\alpha ,\beta )$ is the union of the following collections

1. , which is a subcollection of $\lambda \times \lambda$,

2. , which again is a subcollection $\lambda \times \lambda$, and

3. , which is a subcollection of $\{\alpha \}\times \beta$.

Since $\lambda \times \lambda$ and $\{\alpha \}\times \beta$ are both sets, so is the initial segment of $(\alpha ,\beta )$.∎

Remark. The canonical well-ordering on On$\mathrm{\times }$On can be used to prove a well-known property of alephs: ${\mathrm{\aleph }}_{\alpha }\cdot {\mathrm{\aleph }}_{\alpha }={\mathrm{\aleph }}_{\alpha }$, for any ordinal $\alpha$.