Natural Induction

Why

We want to show something holds for every natural number.¹

Definition

The most important property of the set of natural numbers is that it is the unique smallest successor set. In other words, if $S$ is a successor set contained in $\omega $ (see Natural Numbers), then $S = \omega $. This is useful for proving that a particular property holds for the set of natural numbers.

To do so we follow standard routine. First, we define the set $S$ to be the set of natural numbers for which the property holds. This step uses the principle of selection (see Set Selection) and ensures that $S \subset \omega $. Next we show that this set $S$ is indeed a successor set. The first part of this step is to show that $0 \in S$. The second part is to show that $n \in S \implies \ssuc{n} \in S$. These two together mean that $S$ is a successor set, and since $S \subset \omega $ by definition, that $S = \omega $. In other words, the set of natural numbers for which the property holds is the entire set of natural numbers. We call this the principle of mathematical induction.

1. Future editions will modify this superficial why. ↩︎