\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Natural Numbers
Needed by:
Peano Axioms
Sheet PDF
Graph PDF

Natural Induction


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


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. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view