## You are here

Homecanonical ordering on pairs of ordinals

## Primary tabs

# 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)$. ∎

## Mathematics Subject Classification

03E10*no label found*06A05

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## segment

Is the second factor in prop. 3/3 itself not beta?

## Re: segment

That's right. Thanks for the simplification.