L’ensemble des entiers naturels est noté $\N.$ Il est formé par tous les entiers positifs, $0$ y compris.

L’existence de l’ensemble $\N$ provient des axiomes de fondation, qui ne seront pas explicités ici.

L’ensemble $\N$ possède deux propriétés fondamentales qui sont équivalentes.

La première s’appelle le bon ordre. Elle stipule que toute partie non vide de $\N$ admet un plus petit élément.

La seconde s’appelle le principe de récurrence. Pour tout entier naturel $n\comma$ notez $\mathscr{P}(n)$ une propriété dont la valeur de vérité peut être vraie ou fausse. Supposez que $\mathscr{P}(0)$ soit vraie et que l’implication suivante soit vérifiée :

Alors, pour tout entier $n$ de $\N\comma$ la propriété $\mathscr{P}(n)$ est vraie.

Vous allez démontrer l’équivalence de ces deux énoncés.

Montrez que le bon ordre implique le principe de récurrence

Supposez que l’ensemble $\N$ possède la propriété suivante : toute partie non vide de $\N$ non vide admet un plus petit élément.

Pour tout entier naturel $n\comma$ vous notez $\mathscr{P}(n)$ une propriété, vérifiant les conditions suivantes :

Vous voulez montrer que la propriété $\mathscr{P}(n)$ est vraie pour tout entier naturel $n.$ Vous allez considérer l’ensemble noté $A$ des entiers naturels $n$ tels que la propriété $\mathscr{P}(n)$ soit fausse.

Si l’ensemble $A$ n’est pas vide, alors $A$ admet un plus petit élément noté $a$ vu que $A$ est une partie de $\N.$ Notez que comma $\mathscr{P}(0)$ est vraie, vous avez $a\notin A.$ Par conséquent, $a\neq 0$ donc $a\geq 1$ et $a-1 \in \N.$ Comme $a-1$ est strictement inférieur à $a\comma$ qui est le plus petit élément de $A\comma$ vous avez $a-1\notin A.$ Donc $\mathscr{P}(a-1)$ est vraie. Du coup, $\mathscr{P}(a-1+1)$ est vraie et $\mathscr{P}(a)$ est vraie donc $a\notin A\comma$ ce qui est une contradiction.

Il en résulte que la partie $A$ est vide, donc pour tout entier naturel $n\comma$ la propriété $P(n)$ est vraie.

Le principe de récurrence implique que le bon ordre

Vous allez utiliser le principe de récurrence pour montrer que si une partie de $\N$ n’admet pas de plus petit élément, alors elle est vide.

Supposez que l’ensemble $\N$ vérifie le principe de récurrence. Soit $A$ une partie de $\N$ qui n’admet pas de plus petit élément.

Pour tout entier naturel $n\comma$ vous notez $\mathscr{P}(n)$ la propriété stipulant que, pour tout entier naturel $k$ inférieur ou égal à $n\comma$ vous avez $k\notin A.$

Initialisation. Si $0$ appartient à $A$, alors $0$ est le plus petit élément de $A\comma$ ce qui est impossible. Donc $0\notin A$ et par conséquent la propriété $\mathscr{P}(0)$ est vérifiée.

Hérédité. Soit $n$ un entier naturel. Supposez que la propriété $\mathscr{P}(n)$ soit vérifiée.

Notez que tous les entiers naturels $k$ compris entre $0$ et $n$ n’appartiennent pas à $A.$ Si $n+1$ appartenait à la partie $A\comma$ alors $n+1$ serait le plus petit élément de $A\comma$ ce qui est impossible. Donc $n+1\notin A.$

Via le principe de récurrence, vous venez de montrer que $\forall n\in\N, \mathscr{P}(n)$ est vraie. Vous en déduisez que $\forall n\in\N, n\notin A.$ Comme $A$ est une partie de $\N$, il s’ensuit que $A$ est vide.

Par contraposée de ce qui vient d’être établi, vous déduisez que si $A$ est une partie non vide de $\N\comma$ elle admet un plus petit élément.