Theorem
183
[23B] Let \(A⊇ ℕ\) and \(P(n)\) be a logical proposition that can be evaluated for \(n∈ A\). Suppose the following two assumptions are satisfied:
\(P(n)\) is true for \(n=0\) and
\(∀ n∈ ℕ, P(n)⇒ P(S(n))\) ;
then \(P\) is true for every \(n∈ ℕ\).
The first hypothesis is known as ”the basis of induction” and the second as ”inductive step”
Proof
Let \(U=\{ n∈ ℕ:P(n)\} \), we know that \(0∈ U\) and that \(∀ x, x ∈ U⇒ S(x)∈ U\), so \(U\) is S-saturated and \(U\subseteq N\) we conclude that \(U=\mathbb {N}\).