axiome de Peano

On part de zéro, puis on avance d'un entier à la fois : le successeur de 0 est 1, celui de 1 est 2, et ainsi de suite. Les axiomes de Peano fixent les règles de cette construction. Zéro ne vient après aucun entier, deux entiers différents n'ont pas le même successeur, et une propriété vraie au départ puis transmise à chaque étape est vraie pour tous les entiers naturels.

Les axiomes de Peano décrivent une structure formée d'un ensemble d'entiers naturels, noté ℕ, d'un élément distingué appelé zéro, noté z, et d'une fonction successeur, notée s, qui associe à chaque entier naturel son suivant. Ils ne donnent pas une liste déjà écrite des entiers : ils imposent les relations qui organisent cette liste.

Trois exigences interviennent. Zéro n'est le successeur d'aucun entier. La fonction successeur est injective : si deux successeurs sont égaux, leurs antécédents le sont aussi. Enfin, toute partie M de ℕ qui contient z et qui contient s(x) chaque fois qu'elle contient x est nécessairement ℕ tout entier. Cette dernière exigence est le principe de récurrence.

Ces conditions empêchent un retour vers zéro, la fusion de deux chaînes de successeurs et la présence d'éléments naturels inaccessibles depuis zéro. Avec une quantification portant sur toutes les parties de ℕ, elles déterminent la structure des entiers naturels à un isomorphisme près : les noms des éléments peuvent changer, mais pas leur organisation par le successeur.

Soit M une partie de l'ensemble ℕ des entiers naturels. Si M contient l'élément zéro z et si, pour tout entier x appartenant à M, son successeur s(x) appartient encore à M, alors M contient tous les entiers naturels :Pour prouver une propriété par récurrence, M est précisément l'ensemble des entiers pour lesquels cette propriété est vraie.

Les axiomes s'appliquent à une structure composée d'un ensemble ℕ, d'un élément z dans cet ensemble et d'une fonction s de ℕ vers ℕ. Il faut vérifier ensemble trois conditions : z n'est dans l'image de s ; la fonction s est injective ; toute partie contenant z et stable par s est égale à ℕ. La conclusion porte alors sur la structure entière, à un renommage de ses éléments près.

Une chaîne finie ne convient pas. Par exemple, sur {0, 1, 2, 3}, prolonger le successeur impose soit un retour vers un élément déjà atteint, soit un nouvel élément hors de l'ensemble. Un retour vers 0 viole la première condition ; un retour vers 1, 2 ou 3 finit par violer l'injectivité. Il faut alors employer une structure infinie, et non traiter cette chaîne finie comme un modèle des entiers naturels.

On veut établir que l'ajout de zéro à gauche ne change aucun entier naturel. L'addition est définie à partir du successeur par deux règles : zéro plus zéro vaut zéro, et zéro plus le successeur d'un entier n vaut le successeur du résultat de zéro plus n. La propriété P(n) signifie « 0 + n = n ».

1. Au départ, pour n égal à 0, la règle donne exactement 0 + 0 = 0. La propriété P(0) est donc vraie.

2. Supposons P(n) vraie pour un entier naturel n, donc 0 + n = n. La règle de définition de l'addition donne alors :La propriété est ainsi transmise de n à son successeur s(n).

3. L'ensemble M des entiers qui vérifient P contient 0 et reste stable par le successeur. Le principe de récurrence impose donc M = ℕ. Ainsi, 0 + n = n pour tout entier naturel n.

Le contrôle se refait sur les premiers termes : 0 + 1 = 1, puis 0 + 2 = 2 et 0 + 3 = 3. Cette chaîne rend visibles le cas initial et la transmission ; la conclusion générale vient de l'axiome de récurrence, pas de ces seuls essais.

Pour démontrer une affirmation sur tous les entiers naturels, on vérifie un cas initial, puis le passage d'un entier à son successeur. Si l'affirmation ne se transmet pas sous cette forme, une preuve directe ou un autre découpage est préférable.

Pour définir une suite d'objets, on fixe le premier objet puis la règle qui produit le suivant. Cette définition récursive construit les valeurs ; la récurrence, elle, prouve ensuite une propriété commune à toutes ces valeurs.

Pour tester une structure proposée comme modèle des entiers naturels, on cherche un prédécesseur de zéro, deux éléments ayant le même successeur ou une partie stable qui ne couvre pas tout l'ensemble. Un seul de ces défauts suffit à rejeter le modèle.

Axiome et théorème. Un axiome est admis comme point de départ dans une théorie ; un théorème est déduit des axiomes. Dans la présentation de Peano, la récurrence fait partie des postulats, même si elle sert ensuite à démontrer des théorèmes.

Récurrence et définition récursive. Une récurrence établit qu'une propriété vaut pour chaque entier ; une définition récursive fixe un objet initial et la manière de produire le suivant. « P(n) est vraie pour tout n » relève d'une preuve, tandis que « u_n+1 est obtenu à partir de u_n » définit une suite.

Égalité et isomorphisme. Deux modèles peuvent employer des éléments portant des noms différents. Ils sont isomorphes lorsqu'une correspondance bijective conserve zéro et le successeur ; ils ont alors la même structure sans être littéralement le même ensemble.

La formulation logique compte. L'axiome sur toutes les parties de ℕ est une formulation du second ordre et rend la structure catégorique, donc unique à isomorphisme près. Dans une théorie du premier ordre, la récurrence devient un schéma portant sur les propriétés exprimables ; il existe alors aussi des modèles non standards. Il ne faut donc pas transférer automatiquement la conclusion d'un cadre logique à l'autre.

Quelques vérifications ne suffisent pas. Constater une propriété pour 0, 1, 2 et 3 ne prouve rien pour tous les entiers. Le symptôme est l'absence d'un passage démontré de n à s(n). Il faut établir ce passage pour un entier naturel arbitraire, puis invoquer la récurrence.

Le choix du premier naturel est une convention de notation. La structure présentée possède un élément initial z, appelé zéro. Si une source numérote à partir de 1, il faut traduire ses indices au lieu de supprimer l'élément initial exigé par ces axiomes.

Entiers naturels. Situer l'ensemble que les axiomes organisent et retrouver ses usages élémentaires en arithmétique.

Isomorphisme (théorème d'). Préciser en quel sens deux réalisations différentes peuvent porter exactement la même structure mathématique.

arithmétique. Replacer les entiers naturels, leurs opérations et leurs propriétés dans leur domaine général.

Un orfèvre du raisonnement par récurrence. Observer comment le raisonnement par récurrence devient un véritable outil de démonstration.