LPT The Connection between Mathematical Induction and the Principle of Well Ordering

Subsection A.2 The Connection between Mathematical Induction and the Principle of Well Ordering

Lemma A.2.5.

The Principle of Mathematical Induction implies that $1$ is the least positive natural number.

Proof.

Let $S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}$ Then $1 \in S\text{.}$ Assume that $n \in S\text{.}$ Since $0 \lt 1\text{,}$ it must be the case that $n = n + 0 \lt n + 1\text{.}$ Therefore, $1 \leq n \lt n + 1\text{.}$ Consequently, if $n \in S\text{,}$ then $n + 1$ must also be in $S\text{,}$ and by the Principle of Mathematical Induction, and $S = \mathbb N\text{.}$

🔗

Theorem A.2.6.

The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of $\mathbb N$ contains a least element.

🔗

Proof.

We must show that if $S$ is a nonempty subset of the natural numbers, then $S$ contains a least element. If $S$ contains 1, then the theorem is true by Lemma A.2.5. Assume that if $S$ contains an integer $k$ such that $1 \leq k \leq n\text{,}$ then $S$ contains a least element. We will show that if a set $S$ contains an integer less than or equal to $n + 1\text{,}$ then $S$ has a least element. If $S$ does not contain an integer less than $n+1\text{,}$ then $n+1$ is the smallest integer in $S\text{.}$ Otherwise, since $S$ is nonempty, $S$ must contain an integer less than or equal to $n\text{.}$ In this case, by induction, $S$ contains a least element.