Seconda forma del principio di induzione

Teorema

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

1. $P(0)$ sia vera (BASE DELL'INDUZIONE)
2. $\mathrm{\forall }n>0,(P(k)\text{ è vera }\mathrm{\forall }k<n)⟹P(n)\text{ è vera}$ (PASSO INDUTTIVO)

Allora $P(n)$ è vera $\mathrm{\forall }n\in \mathbb{N}$.

Dimostrazione

Sia $A:=\{n\in \mathbb{N}|P(n)\text{ è falsa}\}$, dimostriamo che $A=\varnothing$.
Supponiamo per assurdo che $A\ne \varnothing$. Grazie al teorema di buon ordinamento di $\mathbb{N}$, $A$ ammette minimo $m$. Osserviamo che $m\in A⟹\text{ P(m) è falsa}$.
Da (1) segue che $m\ne 0$.
Inoltre, se $0<k<m,k\notin A$, in quanto abbiamo che $m=minA$, ma allora dalla (2) segue che $P(m)$ è vera, che è impossibile. Segue che $A=\varnothing$, ovvero $P(n)\text{ è vera}\mathrm{\forall }n\in \mathbb{N}$.