# Principle of Well-Ordering: Every nonempty subset of the natural numbers is well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

**Lemma**: The Principle of Mathematical Induction implies that 1 is the least positive natural number.

**Proof**: Let S = {n ∊ N : n ≥1}. Then 1 ∊ S. Now assume that n ∊ S; that is, n ≥1. Since n+1≥1, n+1 ∊ S; hence, by induction, every natural number is greater than or equal to 1.

**Theorem**: The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of N contains a least element.

**Proof**: We must show that if S is a nonempty subset of the natural numbers, then S contains a smallest element. If S contains 1, then the theorem is true by above Lemma. Assume that if S contains an integer k such that 1 ≤ k ≤ n, then S contains a smallest element. We will show that if a set S contains an integer less than or equal to n + 1, then S has a smallest element. If S does not contain an integer less than n + 1, then n + 1 is the smallest integer in S. Otherwise, since S is nonempty, S must contain an integer less than or equal to n. In this case, by induction, S contains a smallest integer.