Théorème 1Les entiers naturels

Principe de récurrence

Énoncé

Soit $P(n)$ une propriété des entiers. Si $P(0)$ est vraie, et si $P(n)$ entraîne $P(S(n))$ pour tout $n \in \omega$ , alors $P(n)$ est vraie pour tout $n \in \omega$ .

Démonstration

La partie $A = \{n \in \omega : P(n)\}$ , qui existe par séparation, contient $0$ et est stable par $S$ : elle est inductive. Par minimalité de $\omega$ , on a $\omega \subset A$ , donc $A = \omega$ .

□

Remarque

Ce principe, posé comme un axiome au lycée, est ici un théorème : il traduit le fait que $\omega$ est le plus petit ensemble inductif.

Repose sur

Le plus petit ensemble inductif

Sert à

Les entiers sont des ensembles transitifs Les axiomes de Peano sont des théorèmes L'appartenance est un bon ordre sur ω Théorème de définition par récurrence