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}<b_{1},\mbox{ or }\\ \max\{a_{1},a_{2}\}=\max\{b_{1},b_{2}\},\mbox{ and }a_{1}=b_{1},\mbox{ and }a_% {2}<b_{2}.\end{array}\right.

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\}<q\}\cup\{(m,q)\mid m<p\}\cup\{(p,n)\mid n<q\}$ .

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.

$\max\{a_{1},a_{2}\}<\max\{b_{1},b_{2}\}$ and $\max\{b_{1},b_{2}\}\leq\max\{c_{1},c_{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.

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

$a_{1}\leq b_{1}$ and $b_{1}<c_{1}$ ,
3.

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

the first two produce $a_{1}<c_{1}$ , and the last $a_{1}=c_{1}$ and $a_{2}<c_{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<x$ , 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<y$ , 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.

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

$\{(\gamma,\delta)\mid\max\{\gamma,\delta\}=\lambda,\mbox{ and }\gamma<\alpha\}$ , which again is a subcollection $\lambda\times\lambda$ , and
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
Canonical name	CanonicalOrderingOnPairsOfOrdinals
Date of creation	2013-03-22 18:50:02
Last modified on	2013-03-22 18:50:02
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03E10
Classification	msc 06A05
Synonym	canonical well-ordering
Related topic	IdempotencyOfInfiniteCardinals
Defines	canonical ordering