Well-Ordered Sets and Induction
The purpose of this post is to provide a more sophisticated perspective on the principle of (strong) mathematical induction: Let \(P(n)\) be a statement about the natural number \(n\) such that \(P(1)\) holds, and such that \(P(1)\land P(2) \land ... \land P(n) \implies P(n+1)\). Then \(P(n)\) holds for all natural numbers \(n\). I want to begin by introducing the notion of a well-ordered set and then using this notion to give an equivalent statement of the principle of induction. Definition (Well-Ordered set): An ordered set \(A\) is called well-ordered if every non-empty subset of \(A\) has a smallest element. The principle of mathematical induction is equivalent to the statement that the natural numbers are well-ordered. Why is this so? Well, to see this we consider the set \(S\) of natural numbers for which the proposition \(P(n)\) doesn't hold. If it is not empty, then let \(k\) be the smallest element. Since \(P(1)\) holds we know that \(k \neq 1\). But if \(P(k)