# canonical ordering on pairs of ordinals

The lexicographic ordering on On$\times$On, the class of all pairs of ordinals, is a well-order in the broad sense, in that every subclass of On$\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$\times$On such that every initial segment of On$\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$\times$On.

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

 $(a_{1},a_{2})\prec(b_{1},b_{2})\quad\mbox{iff}\quad\left\{\begin{array}[]{ll}% \max\{a_{1},a_{2}\}<\max\{b_{1},b_{2}\},\mbox{ or }\\ \max\{a_{1},a_{2}\}=\max\{b_{1},b_{2}\},\mbox{ and }a_{1}

For example, consider the usual ordering on $\mathbb{Z}$. Given $(p,q)\in\mathbb{Z}\times\mathbb{Z}$. Suppose $p\leq 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 $\{(m,n)\mid\max\{m,n\}.

###### Proposition 1.

. $\prec$ is a strict linear ordering on $A\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})\neq(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. 1.

$\max\{a_{1},a_{2}\}<\max\{b_{1},b_{2}\}$ and $\max\{b_{1},b_{2}\}\leq\max\{c_{1},c_{2}\}$,

2. 2.

$\max\{a_{1},a_{2}\}\leq\max\{b_{1},b_{2}\}$ and $\max\{b_{1},b_{2}\}<\max\{c_{1},c_{2}\}$,

produce $\max\{a_{1},a_{2}\}<\max\{c_{1},c_{2}\}$. Now, assume $\max\{a_{1},a_{2}\}=\max\{b_{1},b_{2}\}=\max\{c_{1},c_{2}\}$, which result in three more cases

1. 1.

$a_{1} and $b_{1}\leq c_{1}$,

2. 2.

$a_{1}\leq b_{1}$ and $b_{1},

3. 3.

$a_{1}=b_{1}=c_{1}$, and $a_{2} and $b_{2},

the first two produce $a_{1}, and the last $a_{1}=c_{1}$ and $a_{2}. 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 $\prec$ on $A\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 $\varnothing\neq 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,\mbox{ where }(c_{1},c_{2})\in R\}.$

Then $C\neq\varnothing$, and has a least element $c$. Finally, let

 $D:=\{d_{2}\mid\max\{c,d_{2}\}=b,\mbox{ where }(c,d_{2})\in R\}.$

Again, $D\neq\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 $b<\max\{x,y\}$, then $(c,d)\prec(x,y)$. Otherwise, $b=\max\{x,y\}$, so that $x\in C$ is at least $c$. If $c, then again we have $(c,d)\prec(x,y)$. But if $c=x$, then $y\in D$, so that $d\leq y$. Since $(x,y)\neq(c,d)$, and $x=c$, $y\neq d$. Therefore $d, 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$\times$On is a well-ordering by proposition 2. Moreover,

###### Proposition 3.

Given the canonical ordering $\prec$ on On$\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. 1.

$\{(\gamma,\delta)\mid\max\{\gamma,\delta\}<\lambda\}$, which is a subcollection of $\lambda\times\lambda$,

2. 2.

$\{(\gamma,\delta)\mid\max\{\gamma,\delta\}=\lambda,\mbox{ and }\gamma<\alpha\}$, which again is a subcollection $\lambda\times\lambda$, and

3. 3.

$\{(\alpha,\delta)\mid\max\{\alpha,\delta\}=\lambda,\mbox{ and }\delta<\beta\}$, 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$\times$On can be used to prove a well-known property of alephs: $\aleph_{\alpha}\cdot\aleph_{\alpha}=\aleph_{\alpha}$, for any ordinal $\alpha$.

Title canonical ordering on pairs of ordinals CanonicalOrderingOnPairsOfOrdinals 2013-03-22 18:50:02 2013-03-22 18:50:02 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 03E10 msc 06A05 canonical well-ordering IdempotencyOfInfiniteCardinals canonical ordering