Contruction des entiers naturels

Nous allons proposer une définition axiomatique de l'ensemble $\mathbb{N}$ des entiers naturels. Nous déduirons ensuite de cette définition axiomatique les principales propriétés de $\mathbb{N}$ . En particulier nous définirons l'addition de deux entiers naturels, la relation d'ordre sur $\mathbb{N}$ et la multiplication de deux entiers naturels.

Nous avons choisi d'exposer ici l'axiomatique dite de Peano. D'autres choix sont possibles comme par exemple l'axiomatique de l'ordre, comme nous le verrons plus loin.

Définition 1 On appelle triplet naturel un triplet $(O,\mathcal{N},s)$ , où $\mathcal{N}$ est un ensemble, un élément de $\mathcal{N}$ et une application de $\mathcal{N}$ dans $\mathcal{N}$ qui vérifie les propriétés suivantes :

: est injective,
: $s(\mathcal{N})=\mathcal{N}\setminus\{O\}$ ,
: Si est une partie de $\mathcal{N}$ telle que si $O\in A$ et $s(A)\subset A$ alors $A=\mathcal{N}$ .

Les 3 propriétés

sont les axiomes de Peano (bien qu'ils soient dus à Dedekind). L'application

est l'application «successeur» : comprenez

« origine» ou «zéro», et

; mais ne le dites pas tout haut tant que nous n'avons pas défini l'addition.

Il convient de s'assurer qu'il existe effectivement de tels triplets $(O,\mathcal{N},s)$ ... sans bien sûr invoquer l'ensemble des entiers que nous sommes en train de construire. On peut en exhiber dans différents contextes, selon le langage logique que l'on suppose connu. Puisque la notion de triplet naturel suppose la notion d'ensemble, nous pouvons supposer au minimum que les notions d'ensemble vide et de réunion sont connues. Dans notre premier exemple $\mathcal{N}$ sera un ensemble d'ensembles dont le zéro est l'ensemble vide. Définissons l'application successeur par $s(A)= A\cup \{A\}$ . Les premiers éléments de $\mathcal{N}$ sont :

$\displaystyle \emptyset ,\; \{\emptyset\} ,\; \{\emptyset, \{\emptyset\}\} ,... ...tyset\}\}, \{\emptyset, \{\emptyset\}, \{\emptyset,\{\emptyset\}\}\}\} \ldots$

Ce n'est pas le plus commode pour compter, d'accord. Disons que vous soyez doté de la notion de chaîne de caractères, et de la concaténation. Commencez par la chaîne vide, puis définissez le successeur d'une chaîne comme la concaténation de cette chaîne avec la chaîne composée d'un seul caractère, mettons

. Voici les premiers éléments.

$\displaystyle [] ,\;[a] ,\;[a,a] ,\;[a,a,a] ,\;[a,a,a,a] ,\;[a,a,a,a,a] \ldots$

Disons maintenant que vous soyez à la préhistoire, et que vos «naturels» sont des paquets de barres, tracées sur la paroi de la caverne. L'application successeur consiste à tracer une nouvelle barre à la suite des barres déjà écrites.

$\displaystyle \vert ,\;\vert\vert \;\vert\vert\vert ,\;\vert\vert\vert\vert ,\;\vert\vert\vert\vert\vert ,\;\vert\vert\vert\vert\vert\vert \ldots$

L'axiome s'appelle l'axiome de récurrence. On en déduit la formulation classique du raisonnement par récurrence.

Proposition 1 (raisonnement par récurrence) Soit $(O,\mathcal{N},s)$ un triplet naturel et $\mathcal{P}$ une propriété définie sur $\mathcal{N}$ , qui vérifie :

$\mathcal{P}(O)$ est vraie
Pour tout $a\in\mathcal{N}$ , ( $\mathcal{P}(a)$ vraie) implique ( $\mathcal{P}(s(a))$ vraie).

Alors $\mathcal{P}(a)$ est vraie pour tout $a\in\mathcal{N}$ .

Démonstration : Il suffit d'appliquer l'axiome

au sous-ensemble

$\displaystyle A=\{a\in\mathcal{N} \vert \mathcal{P}(a) \mathrm{est vraie}\}$

de $\mathcal{N}$ . $\square$

Théorème 1 Soient $(O_1,\mathcal{N}_1,s_1)$ et $(O_2,\mathcal{N}_2,s_2)$ deux triplets qui vérifient les axiomes , il existe une unique application bijective $f_{12} : \mathcal{N}_1\to\mathcal{N}_2$ telle que

$\displaystyle f_{12}(O_1)=O_2,$

(1)

$\displaystyle f_{12}\circ s_1=s_2\circ f_{12}.$

(2)

Démonstration : Vérifions que les deux conditions (1) et (2) définissent une unique application $f_{12}$ de $\mathcal{N}_1$ dans $\mathcal{N}_2$ . Soit l'ensemble des éléments de $\mathcal{N}_1$ pour lesquels $f_{12}(a)$ est défini de manière unique. La partie satisfait les hypothèses de l'axiome et par conséquent $A=\mathcal{N}_1$ .

De manière analogue on définit $f_{21}$ en échangeant les rôles de $\mathcal{N}_1$ et $\mathcal{N}_2$ . Montrons que $f_{21}\circ f_{12}=Id_{\mathcal{N}_1}$ par récurrence. Pour $a\in\mathcal{N}_1$ considérons la propriété :

$\displaystyle \mathcal{P}(a) : f_{21}\circ f_{12}(a)=a.$

Par définition de $f_{12}$ et $f_{21}$ , $\mathcal{P}(O_1)$ est vraie. Soit $a\in\mathcal{N}_1$ , supposons que $\mathcal{P}(a)$ est vraie, c'est-à-dire $f_{21}\circ f_{12}(a)=a$ . Alors

$\displaystyle f_{21}\circ f_{12}(s_1(a))=f_{21}(s_2(f_{12}(a))=s_1(f_{21}\circ f_{12}(a))=s_1(a)$

et $\mathcal{P}(s(a))$ est donc vraie. De la même manière on montrerait que $f_{12}\circ f_{21}=Id_{\mathcal{N}_2}$ , ce qui prouve que $f_{12}$ est bijective. $\square$

Le Théorème 1 montre que les axiomes caractérisent le triplet
$(O,\mathcal{N},s)$ à isomorphisme près.

On peut donc identifier tous les triplets $(O,\mathcal{N},s)$ qui vérifient les axiomes , , à un triplet modèle que l'on notera $(0,\mathbb{N},s)$ et que l'on appelle ensemble des entiers naturels.

Opérations sur les entiers Sur l'ensemble des entiers naturels, nous allons maintenant définir l'addition, la multiplication et la relation d'ordre. Commençons par l'addition.

Définition 2 On définit par récurrence sur l'ensemble $\mathbb{N}$ des entiers naturels, une loi de composition interne appelée addition et notée , en posant :

(i): $\forall a\in\mathbb{N},\quad a+0=a$
(ii): $\forall (a,b)\in\mathbb{N}^2,\quad a+s(b)=s(a+b)$

Ces propriétés définissent complètement la loi . En effet considérons la partie de $\mathbb{N}$ définie par

$\displaystyle A=\{b\in\mathbb{N} \vert \forall a\in\mathbb{N}\quad a+b\textrm{ est bien d\'efini}\}.$

On vérifie facilement que $0\in A$ et $s(A)\subset A$ d'où $A=\mathbb{N}$ par

Traditionnellement on note et, par définition de la loi , on a pour tout $a\in\mathbb{N}$ .

Proposition 2 La loi définie ci-dessus est associative, commutative, admet 0 comme élément neutre et tout entier naturel est régulier par rapport à cette opération.

Démonstration :

Associativité : Soient $a,b,c\in\mathbb{N}$ , on montre que par récurrence sur , et étant fixés. Le cas est une conséquence immédiate de (i). Supposons que alors

$\displaystyle (a+b)+s(c)$ $\displaystyle =s((a+b)+c) \qquad$ $\displaystyle \textrm {d'apr{\\lq e}s (ii)}$

$\displaystyle =s(a+(b+c)) \qquad$ $\displaystyle \textrm {par hypoth\\lq ese de r\'ecurrence}$

$\displaystyle =a+s(b+c) \qquad$ $\displaystyle \textrm {d'apr\\lq es (ii)}$

$\displaystyle =a+(b+s(c)) \qquad$ $\displaystyle \textrm {d'apr\\lq es (ii)},$

d'où le résultat.
Élément neutre : Montrons par récurrence que pour tout $a\in\mathbb{N}$ on a , d'après (i) on aura et 0 sera donc l'élément neutre de la loi .
Par définition de , et pour $a\in\mathbb{N}$ tel que , on a . Par conséquent si $A=\{a\in\mathbb{N} \vert 0+a=a\}$ , $0\in A$ et $s(A)\subset A$ et par $A=\mathbb{N}$ .
Commutativité : Si $a\in\mathbb{N}$ est fixé, montrons par récurrence sur que . On sait déjà que , car 0 est l'élément neutre de .
Montrons que pour tout $a\in\mathbb{N}$ . C'est vrai pour et si c'est vrai pour un donné, l'associativité permet d'écrire

$\displaystyle s(a)+1=(a+1)+1=(1+a)+1=1+(a+1)=1+s(a)$
ce qui achève le raisonnement.
Supposons que , alors grâce à l'associativité,

$\displaystyle a+s(b)=a+(b+1)$ $\displaystyle =(a+b)+1=(b+a)+1$

$\displaystyle =b+(a+1)=b+(1+a)=(b+1)+a=s(b)+a$

ce qui termine la récurrence.
Régularité : Montrons que pour tous , et de $\mathbb{N}$ on a

$\displaystyle a+x=a+y \Longrightarrow x=y.$ (3)

Soient $x,y\in\mathbb{N}$ , on pose $A=\{a\in\mathbb{N} \vert a+x=a+y \Rightarrow x=y\}$ . La partie contient 0, par définition de l'élément neutre. Soit $a\in A$ , supposons que . Par la propriété (ii) de , on obtient et grâce à l'injectivité de (axiome ) . Mais puisque $a\in A$ , cela implique et donc $s(A)\subset A$ d'où $A=\mathbb{N}$ par .

$\square$

Proposition 3 Soient $a,b\in\mathbb{N}$ tels que alors .

Démonstration : Soit $b\in\mathbb{N}^*$ , il existe alors $c\in\mathbb{N}$ tel que

et si $a\in\mathbb{N}$ on a

par définition de l'addition. Mais l'application

est à valeurs dans $\mathbb{N}^*$ et par conséquent $a+b\neq 0$ . On a donc prouvé que si $a,b\in\mathbb{N}$ sont tels que

alors

et de plus

. $\square$ Passons maintenant à la relation d'ordre.

Définition 3 Soient $(a,b)\in\mathbb{N}^2$ , on dira que $a\leqslant b$ , s'il existe $c\in\mathbb{N}$ tel que .

Proposition 4 La relation $\leqslant$ est une relation d'ordre sur $\mathbb{N}$ compatible avec l'addition.

Démonstration : Nous devons prouver que $\leqslant$ est réflexive, antisymétrique, transitive et que si $a,b\in\mathbb{N}$ vérifient $a\leqslant b$ , alors $a+n\leqslant b+n$ pour tout $n\in\mathbb{N}$ .

Réflexivité : Pour tout $a\in\mathbb{N}$ , on a par définition de l'addition, soit $a\leqslant a$ .
Antisymétrie : Soient $a,b\in\mathbb{N}$ tels que $a\leqslant b$ et $b\leqslant a$ , c'est-à-dire il existe $c,d\in\mathbb{N}$ tels que et . Par conséquent et puisque est associative et que tout élément est régulier pour , on a , d'où par la Proposition 3, soit .
Transitivité : Soient $a,b,c\in\mathbb{N}$ tels que $a\leqslant b$ et $b\leqslant c$ , c'est-à-dire il existe $n,p\in\mathbb{N}$ tel que et . Alors car est associative, d'où $a\leqslant c$ .
Compatibilité avec l'addition : Soient $a,b\in\mathbb{N}$ tels que $a\leqslant b$ , c'est-à-dire il existe $c\in\mathbb{N}$ tel que , et $n\in\mathbb{N}$ . Alors

$\displaystyle b+n=(a+c)+n=a+(c+n)=a+(n+c)=(a+n)+c$
grâce à l'associativité et à la commutativité de l'addition, soit $a+n\leqslant b+n$ .

$\square$

Proposition 5 L'ensemble ordonné $(\mathbb{N},\leqslant)$ vérifie les propriétés suivantes :

0 est le plus petit élément de $\mathbb{N}$ ;
toute partie non vide de $\mathbb{N}$ possède un plus petit élément;
toute partie non vide et majorée de $\mathbb{N}$ possède un plus grand élément;
l'ensemble $\mathbb{N}$ n'admet pas de plus grand élément.

Les propriétés

constituent les axiomes de l'ordre: le terme axiome peut vous sembler inappropri'e, car ce sont autant de propositions que nous allons démontrer. Il se trouve que

, si on les prend comme axiomes, constituent une définition alternative de $\mathbb{N}$ , à partir de laquelle on peut démontrer ce qui précède. Démonstration : Puisque 0 est élément neutre de l'addition, pour tout $a\in\mathbb{N}$ on a

, soit $0\leqslant a$ par définition de la relation d'ordre. L'élément 0 de $\mathbb{N}$ est donc son plus petit élément.

Axiome : Soit une partie non vide de $\mathbb{N}$ . Si $0\in\mathbb{N}$ , c'est terminé, 0 est le plus petit élément de . Si $0\notin A$ , l'ensemble $B=\{n\in\mathbb{N}\setminus A \vert \forall a\in A, n\leqslant a\}$ des minorants stricts de est non vide puisqu'il contient 0, de plus $B\neq \mathbb{N}$ puisque $A\neq \emptyset$ . Il résulte alors de l'axiome qu'il existe $b\in B$ tel que $s(b)=b+1\notin B$ . Vérifions que est un minorant de . Puisque $b\in B$ , on a $b\leqslant a$ pour tout $a\in A$ . Si $a\in A$ , il existe donc $c\in\mathbb{N}$ tel que avec $c\neq 0$ car $b\neq a$ et donc . Par conséquent, grâce à l'associativité et à la commutativité de l'addition, , soit $s(b)=b+1\leqslant a$ . Mais $s(b)\in A$ car sinon il serait dans ce qui contredirait la définition de , c'est donc le plus petit élément de .
Axiome : Supposons que $\mathbb{N}$ possède un plus grand élément . Alors vérifie $N\leqslant s(N)$ , par définition de la relation d'ordre, et comme est le plus grand élément de $\mathbb{N}$ , $s(N)\leqslant N$ et donc , c'est-à-dire et par régularité de pour l'addition , ce qui contredit .
Axiome : Soit une partie non vide, majorée de $\mathbb{N}$ et $B=\{n\in\mathbb{N}\setminus A \vert \forall a\in A, a\leqslant n\}$ l'ensemble des majorants stricts de . L'ensemble n'est pas vide car nous avons prouvé que $\mathbb{N}$ satisfait , il possède donc, comme nous venons de le montrer, un plus petit élément $b\neq 0$ puisque est non vide. Grâce à , il existe alors $c\in\mathbb{N}$ tel que . Vérifions que est un majorant de . Puisque $s(c)\in B$ , on a $a\leqslant s(c)$ et $a\neq s(c)$ pour tout $a\in A$ . Si $a\in A$ , il existe donc $d\in\mathbb{N}^*$ tel que , avec et par conséquent, grâce à l'associativité de l'addition, et, par régularité de pour , , soit $a\leqslant c$ . Mais alors $c\in A$ car sinon il serait dans ce qui contredirait la définition de comme plus petit élément de , puisque .

$\square$ Sur le même modèle que l'addition, nous allons construire une nouvelle loi de composition interne dans $\mathbb{N}$ , la multiplication.

Définition 4 On définit par récurrence sur l'ensemble $\mathbb{N}$ des entiers naturels, une loi de composition interne appelée multiplication et notée $\times$ , en posant :

(i): $\forall a\in\mathbb{N},\quad a\times 0=0$
(ii): $\forall (a,b)\in\mathbb{N}^2,\quad a\times s(b)=(a\times b)+a$

Comme dans le cas de l'addition, ces propriétés définissent complètement la loi $\times$ , en vertu de .

Proposition 6 La loi $\times$ définie ci-dessus est associative, commutative, distributive par rapport à l'addition, admet comme élément neutre et tout entier naturel non nul est régulier par rapport à cette opération.

Démonstration : Remarquons tout d'abord que par définition de la multiplication on a pour tout $n\in\mathbb{N}$

$\displaystyle n\times 1=n\times s(0)=(n\times 0)+n=0+n=n.$

Montrons par récurrence que pour tout $n\in\mathbb{N}$ on a

$\displaystyle 0\times n=0\quad \mathrm{et}\quad 1\times n=n.$

Ces propriétés sont vraies pour

et si elles sont vraies au rang

, on a

$\displaystyle 0\times s(n)=(0\times n)+0=0+0=0\quad \mathrm{et}\quad 1\times s(n)=(1\times n)+1=n+1=s(n),$

ce qui termine la récurrence.

Nous venons en particulier de prouver que est l'élément neutre de la multiplication.

Distributivité : Montrons par récurrence sur que pour tout $a,b,c\in\mathbb{N}$ on a $(a+b)\times c=a\times c+b\times c$ . Fixons $a,b\in\mathbb{N}$ , pour nous obtenons $(a+b)\times 0=0$ et $a\times 0+b\times 0=0$ , d'où $(a+b)\times 0=a\times 0+b\times 0=0$ . Supposons que l'égalité est satisfaite pour et calculons $(a+b)\times s(c)$ et $a\times s(c)+b\times s(c)$ . En appliquant l'hypothèse de récurrence, on obtient

$\displaystyle (a+b)\times s(c)=(a+b)\times c+a+b=a\times c+b\times c+a+b$
et

$\displaystyle a\times s(c)+b\times s(c)=a\times c+a+b\times c+b=a\times c+b\times c+a+b$
par définition de la multiplication et grâce à la commutativité de l'addition, d'où le résultat.
Commutativité : Montrons par récurrence sur que pour tout $a,b\in\mathbb{N}$ on a $a\times b=b\times a$ . Fixons quelconque dans $\mathbb{N}$ , si , nous avons déjà prouvé que $a\times 0=0=0\times a$ . Supposons que $a\times b=b\times a$ , alors $a\times s(b)=a\times b +a$ et $s(b)\times a=(b+1)\times a=(b\times a)+(1\times a)=(b\times a)+a$ grâce à la distributivité de $\times$ par rapport à , soit $a\times s(b)=s(b)\times a$ en utilisant l'hypothèse de récurrence.
Associativité : Montrons par récurrence sur que pour tout $a,b,c\in\mathbb{N}$ on a $(a\times b)\times c=a\times (b\times c)$ . Fixons $a,b\in\mathbb{N}$ , pour nous obtenons $(a\times b)\times 0=0$ et $a\times (b\times 0)=a\times 0=0$ . Supposons que l'égalité est satisfaite pour et calculons $(a\times b)\times s(c)$ et $a\times (b\times s(c))$ . Par définition de la multiplication, on obtient en utilisant l'hypothèse de récurrence

$\displaystyle (a\times b)\times s(c)=((a\times b)\times c)+a\times b=(a\times(b\times c))+a\times b$
et

$\displaystyle a\times (b\times s(c))$ $\displaystyle =$ $\displaystyle a\times ((b\times c)+b)=((b\times c)+b)\times a$

$\displaystyle =$ $\displaystyle (b\times c)\times a+b\times a$

$\displaystyle =$ $\displaystyle =(a\times (b\times c))+a\times b\;,$

grâce à la commutativité de $\times$ et à la distributivité de $\times$ par rapport à . D'où le résultat.
Régularité : Montrons que pour tous $a\neq 0$ , et de $\mathbb{N}$ on a :

$\displaystyle x\times a=y\times a \Longrightarrow x=y.$ (4)

Soient $x,y\in\mathbb{N}$ , on pose $A=\{a\in\mathbb{N}^* \vert x\times a=y\times a \Rightarrow x=y\}$ . La partie contient , par définition de l'élément neutre. Soit $a\in A$ , supposons que $x\times s(a) =y\times s(a)$ . Par définition de la multiplication, on obtient $(x\times a)+x=(y\times a)+y$ puis $(y\times a)+x=(y\times a)+y$ , puisque $a\in A$ . La régularité de l'addition implique alors , donc $s(a)\in A$ et par conséquent $A=\mathbb{N}^*$ .
Notons que la régularité des éléments non nuls de $\mathbb{N}$ par rapport à la multiplication implique en particulier que si $a,b\in\mathbb{N}$ vérifient $a\times b=0$ alors ou .

$\square$

Montrons maintenant le lien entre la multiplication et l'addition dans $\mathbb{N}$ .

Proposition 7 Soient $a\in\mathbb{N}$ et $n\in\mathbb{N}^*$ , alors :

$\displaystyle a\times n=\underbrace{a+\dots +a}_{\mathrm{n fois}}\;.$

Démonstration : Soit $a\in\mathbb{N}$ , prouvons le résultat par récurrence sur

. Si

, c'est évident puisque $a\times 1=a$ . Supposons le résultat vrai pour $n\leqslant 1$ alors par définition de la multiplication

$\displaystyle a\times s(n)=(a\times n)+a=(\underbrace{a+\dots +a}_{\mathrm{n fois}})+ a=\underbrace{a+\dots +a}_{\mathrm{(n+1) fois}}\;,$

d'où le résultat puisque

. $\square$

Voici maintenant la compatibilité entre la relation d'ordre et la multiplication.

Proposition 8 La relation d'ordre $\leqslant$ sur $\mathbb{N}$ est compatible avec la multiplication :

$\displaystyle a\leqslant b\;\Longrightarrow\;\Big(\forall n\in\mathbb{N} ,\;an\leqslant bn\Big)\;.$

Démonstration : Soient $a,b\in\mathbb{N}$ tels que $a\leqslant b$ , prouvons que, pour tout $n\in\mathbb{N}$ , on a $a\times n\leqslant b\times n$ . Puisque $a\leqslant b$ , il existe $c\in\mathbb{N}$ tel que

, alors $b\times n=(a+c)\times n=a\times n +c\times n$ grâce à la distributivité de $\times$ par rapport à

, d'où $a\times n\leqslant b\times n$ .

Notons que si de plus $a\neq b$ et $n\neq 0$ alors $a\times n\neq b\times n$ . En effet si $a\neq b$ alors $c\neq 0$ et $c\times n\neq 0$ puisque $n\neq 0$ . $\square$

Proposition 9 L'ensemble ordonné $(\mathbb{N},\leqslant)$ est archimédien, c'est-à-dire pour tout $a\in\mathbb{N}^*$ et tout $b\in\mathbb{N}$ , il existe $n\in\mathbb{N}$ tel que $b\leqslant n\times a$ et $n\times a\neq b$ .

Démonstration : Soient $a,b\in\mathbb{N}$ . Si $b\leqslant a$ et $a\neq b$ ,

convient. Si $a\leqslant b$ , on considère l'ensemble

$\displaystyle B=\{x\times a, x\in\mathbb{N} \vert 1\leqslant x\times a\leqslant b\}.$

L'ensemble

est non vide, puisque $a\in B$ , et il est majoré par

. Il possède donc un plus grand élément $x_0\times a$ . Posons

, alors $x_0\times a\leqslant n\times a$ et $n\times a\neq x_0\times a$ donc $n\times a\notin B$ soit $b\leqslant n\times a$ et $n\times a\neq b$ . $\square$

$\displaystyle (a+b)+s(c)$	$\displaystyle =s((a+b)+c) \qquad$	$\displaystyle \textrm {d'apr{\\lq e}s (ii)}$
	$\displaystyle =s(a+(b+c)) \qquad$	$\displaystyle \textrm {par hypoth\\lq ese de r\'ecurrence}$
	$\displaystyle =a+s(b+c) \qquad$	$\displaystyle \textrm {d'apr\\lq es (ii)}$
	$\displaystyle =a+(b+s(c)) \qquad$	$\displaystyle \textrm {d'apr\\lq es (ii)},$

$\displaystyle a+s(b)=a+(b+1)$	$\displaystyle =(a+b)+1=(b+a)+1$
	$\displaystyle =b+(a+1)=b+(1+a)=(b+1)+a=s(b)+a$

$\displaystyle a\times (b\times s(c))$	$\displaystyle =$	$\displaystyle a\times ((b\times c)+b)=((b\times c)+b)\times a$
	$\displaystyle =$	$\displaystyle (b\times c)\times a+b\times a$
	$\displaystyle =$	$\displaystyle =(a\times (b\times c))+a\times b\;,$