Proofs of Universal Statements: Mathematical Induction · Well Ordering Principle

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Let's provide some examples of using the well-ordering principle (also known as the method of the smallest counterexample). Let us prove that any integer amount \(m \ge 8\) can be changed using coins of denomination \(3\) and \(5\). Let \(m \ge 8\) be the smallest amount that cannot be changed. Clearly, \(m \ge 11\), since 8, 9, and 10 can be changed. But then \(m'=m-3\) also cannot be exchanged (if it could, then we could also change \(m\)), which leads us to a contradiction with the minimality of \(m\).

Similarly, one can prove the formula for the arithmetic series: show that if it does not hold for some \(m\), then it also does not hold for \(m-1\).

The irrationality of the number \(\sqrt 2\) can be proven in a similar way: let \(\sqrt 2=\frac{n}{q}\) and \(n \in \mathbb{Z}_{>0}\) be minimal; but then (as we showed above) \(n\) and \(q\) are even, but then \(n\) is not minimal. More formally, we can say that we are proving the statement \(A(n)\) for all \(n \in \mathbb{Z}_{>0}\): \(\sqrt 2\) is not equal to \(n/q\) for any \(q \in \mathbb{Z}\setminus\{0\}\).

For the curious 🤓

A similar proof proceeds as follows. Suppose that \(\sqrt 2=\frac{n}{q}\) for some \(n,q \in \mathbb{Z}_{>0}\). This means that the set \(S=\{q \in \mathbb{Z}_{>0}\colon q\sqrt 2 \in \mathbb{Z}_{>0}\}\) is non-empty. Let \(m\) be its minimal element, meaning \(m\sqrt{2}\) is an integer. Then the number \(m(\sqrt 2 -1)\) is also an integer: \(m(\sqrt 2-1)=m\sqrt{2}-m\). Moreover, \(m(\sqrt 2 - 1) \in S\): \(m(\sqrt 2-1)\sqrt 2=2m-\sqrt 2m\). But \(m(\sqrt 2-1)<m\), which contradicts the minimality of \(m\).