# Well-Ordering Principle/Proof using Naturally Ordered Semigroup

Jump to navigation
Jump to search

## Theorem

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

That is, the relational structure $\struct {\N, \le}$ on the set of natural numbers $\N$ under the usual ordering $\le$ forms a well-ordered set.

This is called the **well-ordering principle**.

## 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$