Well-Ordering Principle

From ProofWiki

Jump to: navigation, search

Theorem

Every non-empty subset of $\N$ has a minimal (or smallest, or first) element.

This is called the well-ordering property of $\N$, or the well-ordering principle.

Some sources give this as the least-integer principle.

The well-ordering principle also holds for $\N_{\ne 0}$.

From the definition of the naturally ordered semigroup, $\left({S, \circ, \preceq}\right)$ is well-ordered by $\preceq$.

So as $\left({\N, +, \le}\right) \cong \left({S, \circ, \preceq}\right)$ the result follows.

As $\N_{\ne 0} = \N \setminus \left\{{0}\right\}$, by Set Difference Subset $\N_{\ne 0} \subseteq \N$.

As $\N$ is well-ordered, by definition, every subset of $\N$ has a minimal element.

$\blacksquare$

Some authors extend the scope of this theorem to include:

This theorem should not be confused with the Well-Ordering Theorem, which states that any set can have an ordering under which that set is a well-ordered set.