Pourquoi « le plus petit » est indispensable

1. Trois candidats, et il y en a une infinité :

$$P=\{0,2,4,6,\dots \},D=\{\dots ,-4,-2,0,2,4,\dots \},\mathbb{Z}.$$

Chacun contient $0$ et est clos par $n\mapsto n+2$. Aucune règle ne les distingue.

2. L'ensemble inductif est $P$, le plus petit des trois — et de tous les autres. On le voit de deux manières, qui sont les deux faces de la définition :

• Par en haut : $P$ est l'intersection de tous les ensembles contenant $0$ et clos par la règle. Cette intersection est elle-même close (si $n$ est dans tous, $n+2$ aussi), donc c'est le plus petit ;
• Par en bas : $P$ est l'ensemble des éléments atteignables en un nombre fini d'applications des règles à partir de $0$. Ce sont les $0,2,4,\dots$, et rien d'autre : $-2$ n'est le résultat d'aucune suite finie de règles.

Les deux descriptions coïncident, et c'est ce théorème — admis ici — qui rend la définition utilisable.

3. Sans « le plus petit », la preuve par induction devient fausse, et le contre-exemple est immédiat. Prenons $P(n)$ : « $n\ge 0$ ». Les deux obligations de l'induction structurelle sont remplies :

• l'assertion : $P(0)$ est vraie ;
• la règle : si $n\ge 0$ alors $n+2\ge 0$.

Le principe conclurait que tout élément de l'ensemble est positif. Or $D$ satisfait les deux règles et contient $-2$, qui n'est pas positif. La conclusion serait fausse alors que les deux hypothèses sont vraies : c'est le principe lui-même qui s'effondre.

Ce que « le plus petit » achète, en une phrase. Il garantit que tout élément a été construit en un nombre fini d'applications de règles. C'est cette finitude qui rend l'ordre induit bien fondé, et c'est de ce caractère bien fondé que la démonstration du principe d'induction tire son élément minimal. Retirer « le plus petit », c'est retirer la finitude, donc l'ordre bien fondé, donc le principe. Les quatre notions ne sont qu'une seule, vue sous quatre angles.