Skip to main content

Section 6.4 Foundations of the Principle of Math Induction

Subsection 6.4.1 Proof of Math Induction

Mathematical induction can be taken as an axiom, a fundamental fact which is assumed to be true. However, it is a result of a more fundamental property of the natural numbers, which is the well-ordering principle. The well-ordering principle makes math induction concrete.

First, we have to consider math induction in a more precise way. Let \(S\) be the set of all natural numbers such that \(P(n)\) is true. Then, the principle of math induction can be stated as follows.

Let \(S\) be a set of natural numbers, such that \(S\) contains 1, and \(S\) has the property that if \(k \in S\text{,}\) then \((k+1) \in S\text{.}\) By contradiction, assume that \(S\) is not the set of natural numbers. Then, there exists a natural number not in \(S\text{.}\) Let \(A = \mathbb{N} \setminus S\text{,}\) the set of natural numbers not in \(S\text{.}\) This set \(A\) is non-empty, so by the well-ordering property, it contains a smallest element \(S\text{,}\) i.e. a smallest natural number that is not in \(S\text{.}\)

Since \(1 \in S\text{,}\) \(k \neq 1\text{,}\) and so \(k > 1\text{.}\) Then, since \(k - 1 \lt k\text{,}\) and \(S\) is the smallest natural number not in \(S\text{,}\) then \((k - 1) \in S\text{.}\) However, this implies that \((k - 1) + 1 = k \in S\text{,}\) contradicting the fact that \(k \notin S\text{.}\)

Subsection 6.4.2 General Principle of Math Induction