Well-Ordering Principle

Theorem 1:  Well-Ordering Princple

Every non-empty set of non-negative integers contains a least element

Proof:

(1)  Assume that there exists a non-empty set $S$ of positive integers that does not contain a least element.

(2)  Let $P(n)$ be true if $n$ is an element of $S$

(3)  $P(0)$ is false.  If true, then $0$ would be the least element for $S$

(4)  Assume that for all $i \le n, P(i)$ is false. 

(5)  It follows that $P(n+1)$ is false.  If not, then $n+1$ would be the least element for $S$.

(6)  But, then by the Principle of Mathematical Induction, there is no positive integer in $S$

(7)  This contradicts our assumption in (1) that $S$ is non-empty.  Therefore, we can reject our assumption in step (1).

Note:  This is an example of a proof by contradiction.