Proofs of Universal Statements: Mathematical Induction · Well Ordering Principle
Lesson 1
The method of mathematical induction is equivalent to the following important property of positive integers: any non-empty subset has a minimal element. It is known as the well-ordering principle. Note that this property holds for positive integers, but does not hold for many other sets: for example, the sets \(\{-1, -2, -3, \dotsc\}\) (negative integers) and \((2, 3)\) (real numbers \(x\) such that \(2<x<3\)) do not contain minimal elements.
We will show that this property can be proven by induction. Consider a non-empty set \(S \subseteq \mathbb{Z}_{>0}\) and assume that it has no minimal element. Clearly, \(1 \not \in S\) (otherwise, it would be the minimal element). Now consider the predicate \[A(n)=[[n] \cap S = \varnothing].\] The statement \(A(1)\) is true, so the base case holds. We will prove the step \(n \to n+1\): if \(A(n)\) holds but \(A(n+1)\) does not, then \(n+1\) is the minimal element of \(S\). Thus, for all \(n \in \mathbb{Z}_{>0}\), \(n \not \in S\), meaning the set \(S\) is actually empty. Now we will show how the principle of mathematical induction follows from this property. Consider the predicate \(A \colon \mathbb{Z}_{>0}\to \{0,1\}\), for which it is known that \(A(1)\) is true and \(A(n) \Rightarrow A(n+1)\) for all \(n \in \mathbb{Z}_{>0}\). Suppose there exists an \(n \in \mathbb{Z}_{>0}\) for which \(A(n)\) is false. Then the set \(S=\{n \in \mathbb{Z}_{>0}\colon \neg A(n)\}\) is non-empty. By the property, it has a minimal element \(m\), meaning \(A(m)\) is false. Since \(A(1)\) is true, \(m>1\). Thus, \(m-1 \in \mathbb{Z}_{>0}\) and \(A(m-1)\) is false: if \(A(m-1)\) were true, then \(A(m)\) would also have to be true. But this contradicts the minimality of \(m\). Therefore, the set \(S\) is actually empty, which means that \(A(n)\) holds for all \(n\).For the curious 🤓