# Lexicographic Order forms Well-Ordering on Ordered Pairs of Ordinals

This article needs to be linked to other articles.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{MissingLinks}}` from the code. |

This page has been identified as a candidate for refactoring of basic complexity.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

## Theorem

The lexicographic order $\preccurlyeq_l$ is a strict well-ordering on $\paren {\On \times \On}$.

## Proof 1

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

$\blacksquare$

## Proof 2

### Total Ordering

Suppose $\tuple {x, y} \preccurlyeq_l \tuple {x, y}$.

Then:

- $x < x \lor \paren {x = x \land y < y}$.

Both are contradictory, so $\preccurlyeq_l$ is irreflexive.

$\Box$

Let:

- $\tuple {\alpha, \beta} \preccurlyeq_l \tuple {\gamma, \delta}$

and:

- $\tuple {\gamma, \delta} \preccurlyeq_l \tuple {\epsilon, \zeta}$

There are two cases:

Let $\alpha < \gamma$.

Then:

- $\alpha < \epsilon$

so:

- $\tuple {\alpha, \beta} \preccurlyeq_l \tuple {\epsilon, \zeta}$

Let $\alpha = \gamma$.

Then:

- $\alpha < \epsilon \lor \paren {\alpha = \epsilon \land \delta < \zeta}$

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

Therefore:

- $\paren {\alpha = \epsilon \land \beta < \zeta}$

Therefore:

- $\tuple {\alpha, \beta} \preccurlyeq_l \tuple {\epsilon, \zeta}$

In either case, $\preccurlyeq_l$ is transitive.

So $\preccurlyeq_l$ is a strict ordering.

$\Box$

### Strict Total Ordering

Let:

- $\neg \tuple {\alpha, \beta} \preccurlyeq_l \tuple {\gamma, \delta}$

and:

- $\neg \tuple {\gamma, \delta} \preccurlyeq_l \tuple {\alpha, \beta}$

Then:

- $\neg \alpha < \gamma$

and:

- $\neg \gamma < \alpha$

so:

- $\alpha = \gamma$

Similarly:

- $\neg \beta < \delta$

and:

- $\neg \delta < \beta$

so:

- $\beta = \delta$

- $\tuple {\alpha, \beta} = \tuple {\gamma, \delta}$

Therefore $\preccurlyeq_l$ is a strict total ordering.

$\Box$

### Well-Ordering

Let $A$ be a nonempty subset $A$ of $\paren {\On \times \On}$

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 $\tuple {x, y}$ to its first member $x$.

- $1^{st} = \set {\tuple {\tuple {x, y} z}: z = x}$

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

Take $\Img A$, the image of $A$ under $1^{st}$.

- $\Img A \subseteq \On$

so by Subset of Ordinals has Minimal Element, $\Img A$ has a minimal element.

Let this minimal element be $\alpha$.

Let $B = \set {y \in \On : \tuple {\alpha, y} \in A}$.

$\alpha$ is a minimal element of $\Img A$.

So:

- $\tuple {\alpha, y} \in \Img A$

for some $y \in \On$.

Therefore $B$ is non-empty.

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:

- $\tuple {\alpha, \beta} \in A$

Suppose there is some element $\tuple {\gamma, \delta}$ of $A$ such that:

- $\tuple {\gamma, \delta} \preccurlyeq_l \tuple {\alpha, \beta}$

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 $\tuple {\alpha, \delta} \in A$.

This contradicts the fact that $\beta$ is the minimal element satisfying $\tuple {\alpha, \beta} \in A$.

From this contradiction it follows that $\tuple {\alpha, \beta}$ is the $\preccurlyeq_l$-minimal element of $A$.

$\blacksquare$

## Sources

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 7.54 \ (1)$