Well-Ordering Principle

From ProofWiki
Jump to: navigation, search

Theorem

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

This is called the well-ordering principle.


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


Proof

Consider the natural numbers $\N$ defined as the naturally ordered semigroup $\struct {S, \circ, \preceq}$.

From its definition, $\struct {S, \circ, \preceq}$ is well-ordered by $\preceq$.

The result follows.


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

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

$\blacksquare$


Also known as

This is otherwise known as the well-ordering property (of $\N$).

Some sources give it as the least-integer principle.


Note that some authors cite this as the well-ordering theorem.

However, this allows it to be confused even more easily with the Well-Ordering Theorem, which states that any set can have an ordering under which that set is a well-ordered set.


Also see

Some authors extend the scope of this theorem to include:


Sources