Why does Mathematical Induction work ?

Mathematical induction is a proof technique used to prove that a statement, $P(n)$ holds for every natural number $\mathbb{N} = \{1, 2, \dots\}$. The structure of a proof by induction is the following:

1. Base step. Prove that $P(n)$ is true for $n=1$ (i.e., P(1) is true).
2. Induction step. Assume that $P(n)$ holds for an arbitrary natural number $n$ (The induction hypothesis). Then show that this implies that $P(n+1)$ holds.

This would mean that $P(n)$ is true for all $n \in \mathbb{N}$. But why ? It turns out that this is due to the mere existence of the set of natural numbers as the following results from (Schröder, 2007) show.

Theorem: There is a subset $\mathbb{N} \subseteq \mathbb{R}$, called the natural numbers, so that

1. $1 \in \mathbb{N}$
2. For each $n \in \mathbb{N}$ the number $n+1$ is also in $\mathbb{N}$
3. If $S \subseteq \mathbb{N}$ is such that $1 \in S$ and for each $n \in S$ we also have $n + 1 \in S$, then $S = \mathbb{N}$.

Proof: This theorem suggests the existence of a set with two properties (1. and 2.) which defines the set of natural numbers. Point 3. says that any subset of this set with the same properties is infact the set of natural numbers.

Let’s define a successor set, $A$, as a subset of $\mathbb{R}$ such that $1 \in A$ and $a \in A \implies a+1 \in A$. $\mathbb{R}$ itself is a successor set, so there is at least one successor set. Let $ℕ$ be the intersection of all successor sets. That is $ℕ$ contains all elements of $ℝ$ that are in all successor sets. Therefore $ℕ$ itself is a successor set, because $1 \in \mathbb{N}$ since it is in every successor set. And if $n \in ℕ$, $n$ is in every successor set implying that $n + 1$ is in every successor set, thus $n + 1 \in ℕ$. ($ℕ$ is a subset of $ℝ$ with properties 1. and 2.)

To show point 3., suppose $S ⊆ ℕ$ with $1 \in S$ and $n \in S \implies n+1 \in S$. Then $S$ is a successor set. Since $\mathbb{N}$ is the intersection of all successor sets, it means that $ℕ ⊆ S$. Therefore $S = ℕ$. $$\tag*{$\blacksquare$}$$

Theorem (Principle of Induction): Let $P(n)$ be a statement about the natural number $n$. If $P(1)$ is true and if for all $n \in \mathbb{N}$ the truth of $P(n)$ implies the truth of $P(n+1)$, then $P(n)$ holds for all natural numbers.

Proof: Let $S ≔ \{n \in \mathbb{N} \ : \ P(n) \text{ is true} \}$ (S is the set of all natural numbers for which the statement is true). The theorem says that if $1 \in S$ and an arbitrary $n \in S$ implies $n + 1 \in S$, then $S = \mathbb{N}$. That is $P(n)$ is true for all $n \in S = \mathbb{N}$.

Therefore assume $1 \in S$ and $n \in S \implies n+1 \in S$. Note that $S ⊆ \mathbb{N}$. By the previous theorem, $S = \mathbb{N}$. Thus $P(n)$ is true for all $n \in \mathbb{N}$. $$\tag*{$\blacksquare$}$$

References