Well-Ordering Principle/Proof by Restriction of Real Numbers
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
Let $S$ be a non-empty subset of the set of natural numbers $\N$.
We take as axiomatic that $\N$ is itself a subset of the set of real numbers $\R$.
Thus $S \subseteq \R$.
By definition:
- $\forall n \in \N: n \ge 0$
and so:
- $\forall n \in S: n \ge 0$
Hence $0$ is a lower bound of $S$.
This establishes the fact that $S$ is bounded below.
By the Continuum Property, we have that $S$ admits an infimum.
Hence let $b = \inf S$.
Because $b$ is the infimum of $S$, it follows that $b + 1$ is not a lower bound of $S$.
So, for some $n \in S$:
- $n < b + 1$
Aiming for a contradiction, suppose $n$ is not the smallest element of $S$.
Then there exists $m \in S$ such that:
- $b \le m < n < b + 1$
from which it follows that:
- $0 < n - m < 1$
But there exist no natural numbers $k$ such that $0 < k < 1$.
Hence $n = b$ is the smallest element of $S$.
$\blacksquare$
Sources
- 1977: K.G. Binmore: Mathematical Analysis: A Straightforward Approach ... (previous) ... (next): $\S 3$: Natural Numbers: $\S 3.5$