Equivalence of Definitions of Well-Ordering/Definition 1 implies Definition 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preceq}$ be an ordered set such that:

$\forall T \subseteq S: \exists a \in T: \forall x \in T: a \preceq x$

That is, such that $\preceq$ is a well-ordering by definition 1.


Then $\preceq$ is a total ordering.


Proof

Consider $X = \set {a, b}$ where $a, b \in S$.

We have by hypothesis that $X$ has a smallest element.

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

If $\min X = a$, then $a \preceq b$.

If $\min X = b$, then $b \preceq a$.

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

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

As this applies to all $a, b \in S$, the ordering $\preceq$ is total.

$\blacksquare$


Sources