Principio di induzione

Sia $\{P(n){\}}_{n\in \mathbb{N}}$ una famiglia di proposizioni, ovvero affermazioni, indicizzata su $\mathbb{N}$. Supponiamo

1. $P(0)$ è vera. (BASE DELL'INDUZIONE)
2. $\mathrm{\forall }n\in \mathbb{N},\mathrm{♣}P(n)⟹⧫P(succ(n))$ è vera.
   $\mathrm{♣}:$IPOTESI INDUTTIVA
   $⧫:$PASSO INDUTTIVO
   Allora $P(n)$ è vera $\mathrm{\forall }n\in \mathbb{N}$.

Dimostrazione

Osserviamo:

1. $\iff 0\in A$
   Sia $n\in A$. Vale: $n\in A\iff P(n)$ è vera $⟹P(succ(n))$ è vera $\iff succ(n)\in A$
   Grazie all'assioma 2.8 (di induzione), $A=\mathbb{N}\iff P(n)$ è vera $\mathrm{\forall }n\in \mathbb{N}$