Skip to main content

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

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{.}\)

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.