Well-Ordering is Total Ordering

From ProofWiki

Jump to: navigation, search

Theorem

Let $\left({S, \preceq}\right)$ be a well-ordered set.

Then:

By definition of well-ordered, every subset of $S$, including $S$ itself, has a minimal element under $\preceq$.

So that covers the assertion that $\left({S, \preceq}\right)$ has a minimal element.

Now consider $X = \left\{{a, b}\right\}$ where $a, b \in S$.

Because $S$ is well-ordered under $\preceq$, $X$ has a minimal element.

So either $\inf X = a$ or $\inf X = b$.

But by definition, $\inf X \le a$ or $\inf X \le b$.

So either $a \le b$ or $b \le a$.

That is, $a$ and $b$ are comparable.

We have shown that any arbitrarily selected elements $a$ and $b$ of $S$ are comparable.

So there are no non-comparable pairs in $\left({S, \preceq}\right)$.

Hence the ordering $\preceq$ is total.

$\blacksquare$