Axiomes de Peano
Les axiomes de Peano
[modifier | modifier le wikicode]L'ensemble des entiers naturels, noté , est défini par les axiomes de Peano :
- (P1) : L'ensemble possède un élément particulier que l’on note 0.
- (P2) : Chaque élément n possède un successeur que l’on note S(n).
- (P3) : 0 n'est le successeur d'aucun élément.
- (P4) : L'application est injective, c'est-à-dire que si deux éléments ont le même successeur, ils sont égaux.
- (P5) : Toute partie de contenant 0 et stable par S est égale à tout entier (axiome de récurrence).
Suite définie par une relation de récurrence
[modifier | modifier le wikicode]Soient un ensemble, une application et un élément de .
Alors, il existe une unique suite d'éléments de vérifiant :
- ;
- .
Il suffit de montrer par récurrence, c'est-à-dire à l'aide de l'axiome (P5), que pour tout , il existe une unique suite finie satisfaisant les deux points ; la suite définie par : la valeur commune pour tous les sera alors l'unique suite infinie satisfaisant les deux points.
- L'existence et l'unicité de sont immédiates.
- Supposons l'existence et l'unicité de et montrons celles de . Une suite vérifie les deux points si et seulement si sa restriction à les vérifie c'est-à-dire est égale à et de plus, c'est-à-dire .
On en déduit la généralisation suivante :
Soient un ensemble, une application et un élément de .
Alors, il existe une unique suite d'éléments de vérifiant :
- ;
- .
En appliquant le théorème à
- ,
on obtient une suite d'éléments de , donc de la forme (en particulier, et ).
On démontre alors facilement (par récurrence) que
- ,
et l'on en déduit que
- ,
ce qui prouve que .
Addition et multiplication
[modifier | modifier le wikicode]On peut ensuite définir l'addition de la façon suivante. Pour un élément , le théorème ci-dessus permet de définir la suite par :
On pose . On remarque alors que .
On peut définir de même la multiplication. Pour un élément , la suite est définie par :
- .
L'entier est également noté .
Les axiomes de Peano permettent de démontrer, et non plus d'admettre, toutes les propriétés des deux opérations de base. Ainsi, on démontre :
- pour l'addition :
- l'associativité,
- la neutralité de 0,
- la commutativité.
- On résume ces trois propriétés en disant que est un monoïde commutatif ;
- pour la multiplication :
- la commutativité,
- l'associativité,
- la distributivité,
- la neutralité de 1.
Toutes les démonstrations se font par récurrence, c'est-à-dire à l'aide de l'axiome (P5).
- . Démonstration par récurrence sur , pour et fixés.
- L'initialisation est immédiate.
- Pour l'hérédité, supposant que , on en déduit : .
- . Démonstration par récurrence sur . L'initialisation est immédiate. Pour l'hérédité, supposant que , on en déduit : .
- Lemme : . Démonstration par récurrence sur . L'initialisation est immédiate. Pour l'hérédité, supposant que , on en déduit (d'après la remarque faite lors de la définition de 1, et par associativité de +) : .
- . Démonstration par récurrence sur , pour fixé.
- Initialisation : c'est la neutralité de 0, déjà démontrée.
- Hérédité : supposant que , on en déduit (grâce au lemme, et par associativité de +) : .
- La preuve des propriétés de la multiplication est laissée en exercice.
Quelques autres conséquences
[modifier | modifier le wikicode]- On peut définir l'ordre usuel par : . On vérifie alors (exercice) que ≤ est bien une relation d'ordre et que 0 est le plus petit entier naturel. On démontre aussi (par récurrence sur , pour fixé) que pour tous , il existe tel que ou . Autrement dit : l'ordre est total.
- On peut enfin énoncer le théorème de récurrence, qui est une version affaiblie de l'axiome (P5) : si est un prédicat dans le langage du premier ordre sur tel que :
- est vraie — c'est l'initialisation de la récurrence,
- — c'est l'hérédité,
- alors est vrai.
Axiomatisation équivalente
[modifier | modifier le wikicode]Les axiomes P1 à P5 ci-dessus (associés à la définition de ≤ qu'ils permettent) sont équivalents à :
est un ensemble ordonné non vide vérifiant :
- (N1) : Toute partie non vide de admet un plus petit élément,
- (N2) : Toute partie non vide et majorée de admet un plus grand élément,
- (N3) : lui-même n'a pas de plus grand élément.
Soit comme ci-dessus.
- L'ordre sur est total puisque toute paire a un plus petit élément.
- (P1) : En tant que partie non vide de lui-même, admet un plus petit élément, noté .
- (P2) : Pour tout , l'ensemble des majorants stricts de est non vide d'après (N3), donc admet un plus petit élément d'après (N1). On le note .
- (P3) : n'est le successeur d'aucun élément de car il n'est, par définition, majorant strict d'aucun élément.
- (P4) : est injective car strictement croissante. En effet, si alors .
- Tout possède un antécédent par . En effet, l'ensemble des minorants stricts de contient et est majoré par . D'après (N2), admet donc un plus grand élément, . Pour tout , on a . En particulier, on n'a ni , ni , donc .
- (P5) : Soit tel que et , montrons par l'absurde que . Sinon, d'après (N1), il existerait un plus petit entier n'appartenant pas à , notons le . Comme , est non nul, et admet donc un antécédent par , qu'on note . Ainsi, et donc par définition de , , d'où , ce qui est contradictoire.
Soit défini, comme dans les sections précédentes, à partir des axiomes P1 à P5.
- (N1) : soit A une partie de sans plus petit élément. D'après (P5), l'ensemble des minorants de A est égal à , donc A est vide.
- (N2) : soit A une partie de non vide et majorée, par un entier n. L'ensemble a un plus petit élément , et est alors le plus grand élément de A.
- (N3) : tout élément de a des majorants stricts, à commencer par son successeur.
Référents
Ces personnes sont prêtes à vous aider concernant ce cours :
cette liste