Totally Ordered Set is Well-Ordered iff Subsets Contain Infima

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preccurlyeq}$ be a totally ordered set.


Then $\struct {S, \preccurlyeq}$ is a well-ordered set if and only if every non-empty subset of $T \subseteq S$ has an infimum such that $\map \inf T \in T$.


Proof

Sufficient Condition

Let $T \subseteq S$ such that $m := \map \inf T \in T$.

By definition, $m$ is a lower bound of $T$ and so:

$\forall x \in T: m \preccurlyeq x$

That is:

$\neg \exists x \in T: x \prec m$

Thus by definition $x$ is a minimal element of $T$.

Thus by definition $S$ is well-founded and so is a well-ordered set.

$\Box$


Necessary Condition

Let $\struct {S, \preccurlyeq}$ be a well-ordered set.

Let $T \subseteq S$.

Then from Subset of Well-Ordered Set is Well-Ordered, $\struct {T, \preccurlyeq}$ is also a well-ordered set.

Hence, by definition, $\struct {T, \preccurlyeq}$, has a smallest element $m$.

From Smallest Element is Infimum, $m$ is an infimum.

But $m \in T$.

Hence the result.

$\blacksquare$


Sources