Canonical Order Well-Orders Ordered Pairs of Ordinals

From ProofWiki
Jump to navigation Jump to search

Theorem

The canonical order, $R_0$ strictly well-orders the ordered pairs of ordinal numbers.


Proof

Strict Ordering

Let $\left({x, y}\right) R_0 \left({x, y}\right)$.

Then:

$\max \left({x, y}\right) < \max\left({x, y}\right) \lor \left({x, y}\right) \operatorname{Le} \left({x, y}\right)$.



Both lead to contradictions, so:

$\neg \left({x, y}\right) R_0 \left({x, y}\right)$

and $R_0$ is irreflexive.

$\Box$


Let:

$(1): \quad \left({\alpha, \beta}\right) R_0 \left({\gamma, \delta}\right)$

and:

$(2): \quad \left({\gamma, \delta}\right) R_0 \left({\epsilon, \zeta}\right)$


There are two cases:

$\max \left({\alpha, \beta}\right) < \max \left({\gamma, \delta}\right)$

or:

$\max \left({\alpha, \beta}\right) = \max \left({\gamma, \delta}\right)$


\(\displaystyle \max \left({\alpha, \beta}\right) < \max \left({\gamma, \delta}\right)\) \(\implies\) \(\displaystyle \max \left({\alpha, \beta}\right) < \max \left({\epsilon, \zeta}\right)\) from $(2): \quad \max \left({\gamma, \delta}\right) \le \max \left({\epsilon, \zeta}\right)$
\(\displaystyle \) \(\implies\) \(\displaystyle \left({\alpha, \beta}\right) R_0 \left({\epsilon, \zeta}\right)\) Definition of Canonical Order



\(\displaystyle \max \left({\alpha, \beta}\right) = \max \left({\gamma, \delta}\right)\) \(\implies\) \(\displaystyle \left({\alpha, \beta}\right) \operatorname{Le} \left({\gamma, \delta}\right)\)
\(\displaystyle \) \(\implies\) \(\displaystyle \max \left({\alpha, \beta}\right) < \max \left({\epsilon, \zeta}\right) \lor \left({\alpha, \beta}\right) \operatorname{Le} \left({\epsilon, \zeta}\right)\) Transitivity of $\operatorname{Le}$
\(\displaystyle \) \(\implies\) \(\displaystyle \left({\alpha, \beta}\right) R_0 \left({\epsilon, \zeta}\right)\) Definition of Canonical Order


In either case:

$\left({\alpha, \beta}\right) R_0 \left({\epsilon, \zeta}\right)$

and $R_0$ is transitive.

$\Box$


Strict Total Ordering

Suppose:

$\neg \left({\alpha, \beta}\right) R_0 \left({\gamma, \delta}\right)$

and:

$\neg \left({\gamma, \delta}\right) R_0 \left({\alpha, \beta}\right)$

Then:

$\max \left({\alpha, \beta}\right) \le \max \left({\gamma, \delta}\right)$

and:

$\max \left({\gamma, \delta}\right) \le \max \left({\alpha, \beta}\right)$

So:

$\max \left({\alpha, \beta}\right) = \max \left({\gamma, \delta}\right)$.

Therefore:

$\neg \left({\alpha, \beta}\right) \operatorname{Le} \left({\gamma, \delta}\right)$

and:

$\neg \left({\gamma, \delta}\right) \operatorname{Le} \left({\alpha, \beta}\right)$

From Lexicographic Order forms Well-Ordering on Ordered Pairs of Ordinals:

$\left({\alpha, \beta}\right) = \left({\gamma, \delta}\right)$

$\Box$


Well-Ordering

Take any nonempty subset $A$ of $\left({\operatorname{On} \times \operatorname{On}}\right)$.

We shall allow $A$ to be any class.

This isn't strictly necessary, but it will not alter the proof.

The $\max$ mapping sends each element in $A$ to an element of $\operatorname{On}$.

Therefor the image of $\max$ has a minimal element, $N$.

Take $B$ to be the class of all ordered pairs $\left({x, y}\right)$, such that $\max \left({x, y}\right) = N$.

Let the $\operatorname{Le}$-minimal element of $B$ be denoted $C$.

Then:

$\max \left({C}\right) = N$

and $C$ is seen to be $\operatorname{Le}$-minimal.

Therefore $C$ is the $R_0$-minimal element of $A$.

$\blacksquare$


Sources