Soit P une proposition dans N {\displaystyle \mathbb {N} } . On a :
P ( 0 ) ∀ n ∈ N P ( n ) ⇒ P ( n + ) ] ⇒ ∀ n ∈ N {\displaystyle {\begin{matrix}P(0)&&\\\forall {n}\in \mathbb {N} \ P(n)&\Rightarrow &P(n^{+})\end{matrix}}{\Bigg ]}\Rightarrow \forall {n}\in \mathbb {N} } on a P ( n ) {\displaystyle P(n)}
Soit P une proposition et un ensemble P = { n ∈ N / P ( n ) } {\displaystyle {\mathcal {P}}=\lbrace n\in \mathbb {N} /P(n)\rbrace }
On a : P ( 0 ) ⇒ 0 ∈ P {\displaystyle P(0)\Rightarrow 0\in {\mathcal {P}}}
et ∀ n ∈ P ⇒ P ( n ) ⇒ P ( n + ) ⇒ n + ∈ P {\displaystyle \forall n\in {\mathcal {P}}\Rightarrow P(n)\Rightarrow P(n^{+})\Rightarrow n^{+}\in {\mathcal {P}}} On peut dire que P {\displaystyle {\mathcal {P}}} vérifie l'axiome de récurrence et que P = N {\displaystyle {\mathcal {P}}=\mathbb {N} } .
On a donc démontré que :
∀ n ∈ N , P ( n ) {\displaystyle \forall {n}\in \mathbb {N} ,P(n)} est vrai
Ce théorème est le théorème de récurrence
. On a :
![{\displaystyle {\begin{matrix}P(0)&&\\\forall {n}\in \mathbb {N} \ P(n)&\Rightarrow &P(n^{+})\end{matrix}}{\Bigg ]}\Rightarrow \forall {n}\in \mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd521975470e9a3c0985a3de9d0840d668bf6f30)
on a 
On peut dire que 
vérifie l'axiome de récurrence et que 
.
est vrai
