Axiom 3.2.2.1. Well-Ordering Property.
Every nonempty set of nonnegative integers has a least element.
Subsection 3.2.2 Well-ordering Property
The validity of mathematical induction and strong induction follows from a fundamental result about the integers known as the well-ordering property . Note that while we list the well-ordering property below as a theorem, it is in fact an axiom (self-evident truth) that we assume in the precise construction of the set of integers.
Why does the well-ordering property imply that induction is valid ?
Proof of Theorem 3.1.2.1.
For simplicity, just think about the most basic form, as described before Theorem Theorem 3.1.2.1. We proceed by contradiction.
Suppose the principle of mathematical induction is false. Then the set \(S\) of positive integers for which \(P(n)\) is false is nonempty.
By the well-ordering property, \(S\) must have a least element. Let \(m\) be the least element in \(S\text{.}\) Then \(P(m)\) is false.
Because \(P(1)\) is true by the basis step, we have \(m\ne 1\text{.}\) Because \(m\) is positive and not \(1\text{,}\) we must have that \(m\) is at least \(2\text{.}\) Then \(m-1\) is a positive integer less than \(m\text{,}\) and \(P(m - 1)\) is true. By the inductive step, we know that \(P(m-1)\) is true implies \(P(m)\) is true. But \(P(m)\) is true contradicts the proposition that \(P(m)\) is true which we followed from the existence of the non-empty set \(S\text{.}\) Thus such a set \(S\) cannot exists which implies that induction is valid.
The proof the more general case as well as strong-induction is similar.
Remark 3.2.2.2.
This well-ordering property is not true for subsets of the real numbers, so we cannot use these induction techniques to prove things like \(P(x)\) is true for all real positive numbers \(x\text{.}\)
https://xkcd.com/982). Proof of Zermelo’s well-ordering theorem given the Axiom of Choice: 1: Take \(S\) to be any set. 2: When I reach step three, if \(S\) hasn’t managed to find a well-ordering relation for itself, I’ll feed it into this wood chipper. 3: Hey, look, \(S\) is well-ordered.
