Teorema
183
[23B] Sia \(A⊇ ℕ\) e \(P(n)\) una proposizione logica che possa essere valutata per \(n∈ A\). Supponiamo siano soddisfatte le due seguenti ipotesi:
\(P(n)\) è vera per \(n=0\) e
\(∀ n∈ ℕ, P(n)⇒ P(S(n))\) ;
allora \(P\) è vera per ogni \(n∈ ℕ\).
La prima ipotesi è nota come “base dell’induzione” e la seconda come “passo induttivo”
Proof
Sia \(U=\{ n∈ ℕ:P(n)\} \) sappiamo che \(0∈ U\) e che \(∀ x, x ∈ U⇒ S(x)∈ U\), così \(U\) è S-saturo e \(U\subseteq N\) si conclude \(U=\mathbb {N}\).