Axiomes de Peano

Autres leçons de mathématiques

Département

Fondements logiques et ensemblistes des mathématiques

 

Interwikis

Les axiomes de Peano

L'ensemble des entiers naturels, noté $\mathbb {N}$, 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 $S:\mathbb {N} \to \mathbb {N}$ est injective, c'est-à-dire que si deux éléments ont le même successeur, ils sont égaux.
• (P5) : Toute partie de $\mathbb {N}$ contenant 0 et stable par S est égale à $\mathbb {N}$ tout entier (axiome de récurrence).

Suite définie par une relation de récurrence

Début d’un théorème

Théorème

Soient $X$ un ensemble, $f:X\to X$ une application et $a$ un élément de $X$.

Alors, il existe une unique suite $(u_{n})_{n\in \mathbb {N} }$ d'éléments de $X$ vérifiant :

• $u_{0}=a$ ;
• $\forall n\in \mathbb {N} \quad u_{S(n)}=f(u_{n})$.

Fin du théorème

Démonstration

Il suffit de montrer par récurrence, c'est-à-dire à l'aide de l'axiome (P5), que pour tout $n\in \mathbb {N}$, il existe une unique suite finie $u^{n}=\left(u_{k}^{n}\right)_{0\leq k\leq n}$ satisfaisant les deux points ; la suite $u=\left(u_{k}\right)_{k\in \mathbb {N} }$ définie par : $u_{k}=$ la valeur commune $u_{k}^{n}$ pour tous les $n\geq k$ sera alors l'unique suite infinie satisfaisant les deux points.

• L'existence et l'unicité de $u^{0}$ sont immédiates.
• Supposons l'existence et l'unicité de $u^{n}$ et montrons celles de $u^{S(n)}$. Une suite $v=\left(v_{k}\right)_{0\leq k\leq S(n)}$ vérifie les deux points si et seulement si sa restriction à $\{0,\dots ,n\}$ les vérifie c'est-à-dire est égale à $u^{n}$ et de plus, $v_{S(n)}=f(v_{n})$ c'est-à-dire $v_{S(n)}=f(u_{n}^{n})$.

 

On en déduit la généralisation suivante :

Corollaire

Soient $E$ un ensemble, $h:\mathbb {N} \times E\to E$ une application et $b$ un élément de $E$.

Alors, il existe une unique suite $(v_{n})_{n\in \mathbb {N} }$ d'éléments de $E$ vérifiant :

• $v_{0}=b$ ;
• $\forall n\in \mathbb {N} \quad v_{S(n)}=h(n,v_{n})$.

Démonstration

En appliquant le théorème à

$X=\mathbb {N} \times E,\quad f:X\to X,\;(n,e)\mapsto (S(n),h(n,e)),\quad a=(0,b)$,

on obtient une suite $(u_{n})$ d'éléments de $X$, donc de la forme $u_{n}=(w_{n},v_{n})$ (en particulier, $w_{0}=0$ et $v_{0}=b$).

On démontre alors facilement (par récurrence) que

$\forall n\in \mathbb {N} \quad w_{n}=n$,

et l'on en déduit que

$\forall n\in \mathbb {N} \quad (S(n),v_{S(n)})=u_{S(n)}=f(u_{n})=f(n,v_{n})=(S(n),h(n,v_{n}))$,

ce qui prouve que $v_{S(n)}=h(n,v_{n})$.

 

Addition et multiplication

On peut ensuite définir l'addition de la façon suivante. Pour un élément $m\in \mathbb {N}$, le théorème ci-dessus permet de définir la suite $(m+n)_{n\in \mathbb {N} }$ par :

${\begin{cases}&m+0=m\\\forall n\in \mathbb {N} \quad &m+S(n)=S(m+n).\end{cases}}$

On pose $1=S(0)$. On remarque alors que $\forall n\in \mathbb {N} \quad n+1=S(n)$.

On peut définir de même la multiplication. Pour un élément $m\in \mathbb {N}$, la suite $(m\times n)_{n\in \mathbb {N} }$ est définie par :

${\begin{cases}&m\times 0=0\\\forall n\in \mathbb {N} \quad &m\times S(n)=(m\times n)+m.\end{cases}}$.
L'entier $m\times n$ est également noté $mn$.

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 $(\mathbb {N} ,+)$ est un monoïde commutatif ;

• pour la multiplication :
  • la commutativité,
  • l'associativité,
  • la distributivité,
  • la neutralité de 1.

Démonstration

Toutes les démonstrations se font par récurrence, c'est-à-dire à l'aide de l'axiome (P5).

• $\forall m,n,p\in \mathbb {N} \quad (m+n)+p=m+(n+p)$. Démonstration par récurrence sur $p$, pour $m$ et $n$ fixés.
  • L'initialisation est immédiate.
  • Pour l'hérédité, supposant que $(m+n)+p=m+(n+p)$, on en déduit : $(m+n)+S(p)=S((m+n)+p)=S(m+(n+p))=m+S(n+p)=m+(n+S(p))$.
• $\forall m\in \mathbb {N} \quad 0+m=m$. Démonstration par récurrence sur $m$. L'initialisation est immédiate. Pour l'hérédité, supposant que $0+m=m$, on en déduit : $0+S(m)=S(0+m)=S(m)$.
• Lemme : $\forall n\in \mathbb {N} \quad S(n)=1+n$. Démonstration par récurrence sur $n$. L'initialisation est immédiate. Pour l'hérédité, supposant que $S(n)=1+n$, on en déduit (d'après la remarque faite lors de la définition de 1, et par associativité de +) : $S(S(n))=S(1+n)=(1+n)+1=1+(n+1)=1+S(n)$.
• $\forall m,n\in \mathbb {N} \quad m+n=n+m$. Démonstration par récurrence sur $n$, pour $m$ fixé.
  • Initialisation : c'est la neutralité de 0, déjà démontrée.
  • Hérédité : supposant que $m+n=n+m$, on en déduit (grâce au lemme, et par associativité de +) : $m+S(n)=S(m+n)=S(n+m)=n+S(m)=n+(1+m)=(n+1)+m=S(n)+m$.
• La preuve des propriétés de la multiplication est laissée en exercice.

 

Quelques autres conséquences

• On peut définir l'ordre usuel par : $\forall a,b\in \mathbb {N} \quad \left(a\leq b\Leftrightarrow \exists c\in \mathbb {N} \quad b=a+c\right)$. 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 $b$, pour $a$ fixé) que pour tous $a,b\in \mathbb {N}$, il existe $c\in \mathbb {N}$ tel que $a=b+c$ ou $b=a+c$. 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 ${\mathcal {P}}$ est un prédicat dans le langage du premier ordre sur $\{0,+,\times ,\leq \}$ tel que :
  • ${\mathcal {P}}(0)$ est vraie — c'est l'initialisation de la récurrence,
  • $\forall n\in \mathbb {N} \quad \left[{\mathcal {P}}(n)\Rightarrow {\mathcal {P}}(\sigma (n))\right]$ — c'est l'hérédité,

  alors $\forall n\in \mathbb {N} \quad {\mathcal {P}}(n)$ est vrai.

Axiomatisation équivalente

Les axiomes P1 à P5 ci-dessus (associés à la définition de ≤ qu'ils permettent) sont équivalents à :

$(\mathbb {N} ,\leq )$ est un ensemble ordonné non vide vérifiant :

• (N1) : Toute partie non vide de $\mathbb {N}$ admet un plus petit élément,
• (N2) : Toute partie non vide et majorée de $\mathbb {N}$ admet un plus grand élément,
• (N3) : $\mathbb {N}$ lui-même n'a pas de plus grand élément.

Preuve de N1…N3 ⇒ P1…P5

Soit $\mathbb {N}$ comme ci-dessus.

• L'ordre sur $\mathbb {N}$ est total puisque toute paire a un plus petit élément.
• (P1) : En tant que partie non vide de lui-même, $\mathbb {N}$ admet un plus petit élément, noté $0$.
• (P2) : Pour tout $n\in \mathbb {N}$, l'ensemble des majorants stricts de $n$ est non vide d'après (N3), donc admet un plus petit élément d'après (N1). On le note $S(n)$.
• (P3) : $0$ n'est le successeur d'aucun élément de $\mathbb {N}$ car il n'est, par définition, majorant strict d'aucun élément.
• (P4) : $S$ est injective car strictement croissante. En effet, si $n<m$ alors $S(n)\leq m<S(m)$.
• Tout $n\in \mathbb {N} \setminus \{0\}$ possède un antécédent par $S$. En effet, l'ensemble $B$ des minorants stricts de $n$ contient $0$ et est majoré par $n$. D'après (N2), $B$ admet donc un plus grand élément, $m$. Pour tout $x\in \mathbb {N}$, on a $x<n\Leftrightarrow x\in B\Leftrightarrow x\leq m\Leftrightarrow x<S(m)$. En particulier, on n'a ni $S(m)<n$, ni $n<S(m)$, donc $n=S(m)$.
• (P5) : Soit $E\subset \mathbb {N}$ tel que $0\in E$ et $S(E)\subset E$, montrons par l'absurde que $E=\mathbb {N}$. Sinon, d'après (N1), il existerait un plus petit entier n'appartenant pas à $E$, notons le $n$. Comme $0\in E$, $n$ est non nul, et admet donc un antécédent par $S$, qu'on note $m$. Ainsi, $m<n$ et donc par définition de $n$, $m\in E$, d'où $n=S(m)\in S(E)\subset E$, ce qui est contradictoire.

 

Preuve de la réciproque

Soit $(\mathbb {N} ,0,+,\times )$ défini, comme dans les sections précédentes, à partir des axiomes P1 à P5.

• (N1) : soit A une partie de $\mathbb {N}$ sans plus petit élément. D'après (P5), l'ensemble des minorants de A est égal à $\mathbb {N}$, donc A est vide.
• (N2) : soit A une partie de $\mathbb {N}$ non vide et majorée, par un entier n. L'ensemble $\{n-a\mid a\in A\}$ a un plus petit élément $n-a_{0}$, et $a_{0}$ est alors le plus grand élément de A.
• (N3) : tout élément de $\mathbb {N}$ a des majorants stricts, à commencer par son successeur.

 

Référents

Ces personnes sont prêtes à vous aider concernant ce cours :

• Loïc Fabiou (discuter)

cette liste