Le raisonnement par récurrence est enseigné comme une technique : on vérifie l’initialisation, on suppose l’hérédité, on conclut. Présenté ainsi, il ressemble à une astuce de rédaction, et l’élève qui demande pourquoi ça marche reçoit rarement autre chose qu’une métaphore de dominos. La réponse honnête est plus courte et plus troublante : ça marche parce qu’on l’a décrété. La récurrence n’est pas un théorème. C’est un axiome.

Ce blog a déjà construit deux étages de l’édifice numérique : l’anneau canonique des couples d’entiers relatifs et les coupures de Dedekind. Il manquait le rez-de-chaussée. Le vocabulaire employé ici est celui de Syntaxe et sémantique.

1. Cinq énoncés

On se donne un ensemble , un élément et une application appelée successeur. On demande à ce triplet de vérifier ce qui suit.

(P1) est un élément de .

(P2) Tout élément de a un successeur dans .

(P3) n’est le successeur d’aucun élément : pour tout , .

(P4) Le successeur est injectif : si , alors .

(P5) Axiome de récurrence. Si une partie de contient et vérifie « entraîne », alors .

Ces énoncés portent le nom de Giuseppe Peano, qui les publie en 1889 dans les Arithmetices principia. Peano lui-même renvoie à Richard Dedekind, dont Was sind und was sollen die Zahlen? avait paru l’année précédente et contenait l’essentiel. L’usage a retenu un seul des deux noms.

Remarquons ce qui ne figure pas dans la liste : ni addition, ni multiplication, ni ordre. Tout cela sera défini ensuite, à partir du seul successeur. Un entier naturel n’est pas une quantité : c’est une position dans une chaîne qui commence quelque part et ne revient jamais en arrière.

2. Ce que chaque axiome interdit

Un axiome se comprend mieux par ce qu’il exclut. Retirons-les un à un.

Sans (P3), pourrait être le successeur de quelqu’un : la chaîne se refermerait sur elle-même. L’ensemble avec satisfait tous les autres axiomes. C’est un cadran d’horloge, pas .

Sans (P4), deux éléments distincts pourraient avoir le même successeur : deux branches se rejoindraient. On aurait un arbre qui fusionne, non une suite.

Sans (P5) — et c’est le cas intéressant — rien n’interdit à l’ensemble de contenir, à côté de la chaîne issue de , une chaîne supplémentaire sans commencement. Posons

le successeur étant dans chacune des deux parties, et celui de . Les axiomes (P1) à (P4) sont satisfaits : n’est le successeur de personne, et le successeur reste injectif, la copie de n’ayant ni début ni fin. Mais (P5) tombe : la partie contient , est stable par successeur, et pourtant .

Voilà ce que l’axiome de récurrence apporte, et lui seul : il affirme qu’il n’y a rien d’autre dans que ce que l’on atteint depuis en avançant pas à pas. Les quatre premiers axiomes décrivent une chaîne ; le cinquième dit qu’il n’y en a qu’une.

3. La récurrence des copies d’élèves

La forme (P5) parle de parties de ; celle que l’on pratique parle de propriétés. Le passage est immédiat : à une propriété on associe la partie , et l’axiome devient

L’initialisation et l’hérédité ne sont donc pas deux étapes d’une méthode : ce sont les deux hypothèses d’un axiome, et la conclusion vient sans travail supplémentaire. Cela explique aussi l’échec de l’oubli de l’initialisation. « » est parfaitement héréditaire, et fausse pour tout : l’hérédité seule ne démarre rien. Une chaîne de dominos correctement espacés ne tombe pas si personne ne pousse le premier.

4. Le théorème jumeau : définir par récurrence

Pour définir l’addition, on écrit

Ce geste est si familier qu’on le croit gratuit. Il ne l’est pas. Démontrer une propriété par récurrence et définir un objet par récurrence sont deux opérations distinctes : la première vérifie qu’une chose est vraie partout, la seconde affirme qu’une fonction existe et qu’elle est unique. C’est le contenu du théorème de récursion, dû à Dedekind, qui se déduit de (P1)–(P5) mais ne s’y réduit pas.

Une fois l’addition en place, ses propriétés se démontrent — par récurrence, naturellement. L’associativité, la commutativité, la simplification : rien de tout cela n’est donné, tout se prouve. Et la commutativité coûte plus cher qu’on ne l’imagine, puisqu’il faut d’abord établir deux lemmes, et , chacun par une récurrence propre. Trois récurrences successives pour établir que l’ordre des termes d’une somme est indifférent.

5. Premier ordre, second ordre : une dernière fissure

Un mot d’abord sur ce qu’on appelle l’ordre d’un énoncé. Il ne s’agit pas d’une relation d’ordre, mais de la nature de ce sur quoi portent les quantificateurs « pour tout » et « il existe ». Au premier ordre, on ne quantifie que sur les éléments : « pour tout entier … ». Au second ordre, on s’autorise à quantifier aussi sur les parties, c’est-à-dire sur les propriétés : « pour toute partie … ». La différence paraît mince à la lecture ; elle est énorme, parce que les parties d’un ensemble infini sont incomparablement plus nombreuses que ses éléments.

L’énoncé (P5) quantifie sur les parties de : c’est un énoncé du second ordre. Sous cette forme, il caractérise complètement — deux modèles des cinq axiomes sont toujours isomorphes, résultat établi par Dedekind.

Or la logique du premier ordre, celle dans laquelle on formalise d’ordinaire l’arithmétique, ne sait pas quantifier sur les parties. Elle ne peut donc pas écrire (P5) tel quel. Elle le remplace par un schéma d’axiomes : au lieu d’un énoncé unique valable pour toute partie, une infinité d’énoncés, un pour chaque propriété que le langage sait écrire. On récupère ainsi la récurrence pour toutes les propriétés exprimables, et pour elles seules.

Cela ne suffit pas, et le compte est facile à faire. Une formule est une suite finie de signes pris dans un alphabet fini : les propriétés exprimables sont donc dénombrables. Les parties de , elles, ne le sont pas. Le schéma laisse ainsi échapper presque toutes les parties, et la caractérisation tombe : il existe des modèles de l’arithmétique du premier ordre qui ne sont pas isomorphes à . On les dit non standard ; ils contiennent des « entiers » plus grands que , que , que , et que tous les entiers ordinaires à la fois. Le modèle de la deuxième section en donne déjà l’allure.

Ces modèles non standard ne sont pas des curiosités : ce sont eux qui rendent les théorèmes d’incomplétude de Gödel intuitifs. Aucune théorie du premier ordre ne peut décrire et lui seul.

L’élève de terminale n’a pas à connaître ce dernier point. Mais celui qui lui enseigne la récurrence gagne à savoir qu’il ne transmet pas un truc de rédaction : il transmet le seul énoncé qui distingue les entiers naturels de tout ce qui leur ressemble.

---

La construction des ensembles de nombres, depuis les axiomes de Peano jusqu’au corps des réels, est exposée au chapitre 3 du Discours formel sur les mathématiques pour le secondaire.