Lexicographic Order forms Well-Ordering on Ordered Pairs of Ordinals

From ProofWiki
Jump to navigation Jump to search

Theorem

The Lexicographic Order $\operatorname{Le}$ is a strict well-ordering on $\left({\operatorname{On} \times \operatorname{On}}\right)$.


Proof 1

This is an instance of Finite Lexicographic Order on Well-Ordered Sets is Well-Ordering.

$\blacksquare$


Proof 2

Total Ordering

Suppose $\left({x, y}\right) \operatorname{Le} \left({x, y}\right)$.

Then:

$x < x \lor \left({x = x \land y < y}\right)$.

Both are contradictory, so $\operatorname{Le}$ is irreflexive.

$\Box$


Let:

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

and:

$\left({\gamma, \delta}\right) \operatorname{Le} \left({\epsilon, \zeta}\right)$


There are two cases:

Let $\alpha < \gamma$.

Then:

$\alpha < \epsilon$

so:

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


Let $\alpha = \gamma$.

Then:

$\alpha < \epsilon \lor \left({\alpha = \epsilon \land \delta < \zeta}\right)$

But also, if $\alpha = \gamma$, then $\beta < \delta$.

Therefore:

$\left({\alpha = \epsilon \land \beta < \zeta}\right)$

Therefore:

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

In either case, $\operatorname{Le}$ is transitive.

So $\operatorname{Le}$ is a strict ordering.

$\Box$


Strict Total Ordering

Let:

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

and:

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

Then:

$\neg \alpha < \gamma$

and:

$\neg \gamma < \alpha$

so:

$\alpha = \gamma$

Similarly:

$\neg \beta < \delta$

and:

$\neg \delta < \beta$

so:

$\beta = \delta$

By Equality of Ordered Pairs:

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

Therefore $\operatorname{Le}$ is a strict total ordering.

$\Box$

Well-Ordering

Let $A$ be a nonempty subset $A$ of $\left({\operatorname{On} \times \operatorname{On}}\right)$

Let $A$ be any class.

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

Let the mapping $1^{st}$ send each ordered pair $\left({x, y}\right)$ to its first member $x$.

$\displaystyle 1^{st} = \left\{ {\left({\left({x, y}\right) z}\right): z = x}\right\}$

Then $1^{st}: A \to \operatorname{On}$ is a mapping.

Take $\operatorname{Im}\left({A}\right)$, the image of $A$ under $1^{st}$.

$\operatorname{Im}\left({A}\right) \subseteq \operatorname{On}$

so by Subset of Ordinals has Minimal Element, $\operatorname{Im}\left(A\right)$ has a minimal element.

Let this minimal element be $\alpha$.

Let $B = \left\{ {y \in \operatorname{On} : \left({\alpha, y}\right) \in A}\right\}$.

$\alpha$ is a minimal element of $\operatorname{Im}\left({A}\right)$.

So:

$\left({\alpha, y}\right) \in \operatorname{Im} \left({A}\right)$

for some $y \in \operatorname{On}$.

Therefore $B$ is nonempty.

Furthermore, $B$ is some subset of the ordinals.


By Subset of Ordinals has Minimal Element it follows that $B$ has a minimal element.

Let this minimal element be $\beta$.

Therefore:

$\left({\alpha, \beta}\right) \in A$

Suppose there is some element $\left({\gamma, \delta}\right)$ of $A$ such that:

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

Then:

$\gamma \le \alpha$

But for all ordered pairs in $A$, $\alpha$ is a minimal first element.

Therefore $\gamma = \alpha$

But this implies that $\delta < \beta$ and $\left({\alpha, \delta}\right) \in A$.

This contradicts the fact that $\beta$ is the minimal element satisfying $\left({\alpha, \beta}\right) \in A$.

From this contradiction it follows that $\left({\alpha, \beta}\right)$ is the $\operatorname{Le}$-minimal element of $A$.

$\blacksquare$


Sources