Introduction aux mathématiques/Entiers naturels

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

L'essentiel de ce chapitre est détaillé dans les leçons « Axiomes de Peano » et « Arithmétique ».

Axiomatique de Peano

Définition

L'ensemble des entiers naturels, noté $\mathbb {N}$, est défini par les axiomes de Peano :

1. L'ensemble possède un élément particulier que l'on note 0 ;
2. Chaque élément n possède un successeur que l'on note S(n) ;
3. 0 n'est le successeur d'aucun élément ;
4. si deux éléments ont le même successeur, ils sont égaux ;
5. Toute partie de $\mathbb {N}$ contenant 0 et stable par S est égale à $\mathbb {N}$ tout entier.

Suite définie par une relation de récurrence

Grâce à l'axiome 5, on démontre :

Début d’un théorème

Théorème

Soient $f:E\rightarrow E$ et $a\in E$.

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

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

Fin du théorème

Addition et multiplication dans $\mathbb {N}$

On note $1=S(0)$, puis $2,3,4,5,6,7,8,9$ les neufs premiers itérés de $0$. Pour ne pas à avoir recours à une infinité de symboles, on a trouvé un moyen plus malin, que vous connaissez depuis l'école élémentaire. On a bien sûr reconnu en $\mathbb {N}$ notre ensemble usuel pour compter ; ceci fera l’objet du prochain chapitre, mais avant cela il nous faut donner un sens à l’addition et à la multiplication.

Le théorème ci-dessus permet de définir l'addition et la multiplication dans $\mathbb {N}$ par :

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

Remarques

• $\forall m\in \mathbb {N} \quad m+1=S(m)$.
• L'entier $m\times n$ est également noté $mn$.

Proposition

*L'addition et la multiplication sur $\mathbb {N}$ sont associatives et commutatives.

• $0$ est neutre pour l'addition et $1$ est neutre pour la multiplication.
• La multiplication est distributive par rapport à l'addition.
• Tout élément $a\in \mathbb {N}$ est régulier pour l'addition, c'est-à-dire : $\forall c,c'\in \mathbb {N} \quad \left(a+c=a+c'\Rightarrow c=c'\right)$.

Ordre sur $\mathbb {N}$

On définit ≤ à partir de l'addition :

$\forall a,b\in \mathbb {N} \quad \left(a\leq b\Leftrightarrow \exists c\in \mathbb {N} \quad b=a+c\right)$

(l'entier $c$ est alors unique et noté $b-a$).

Alors :

• ≤ est une relation d'ordre sur $\mathbb {N}$ ;
• toute partie non vide de $\mathbb {N}$ admet un plus petit élément (en particulier, l'ordre est total) ;
• $\mathbb {N}$ lui-même a 0 pour plus petit élément ;
• le successeur d'un entier est son plus petit majorant strict.

De plus (exercice), ≤ est compatible avec l'addition et la multiplication, au sens où

${\begin{aligned}\forall a,b,c\in \mathbb {N} \quad &a\leq b\Leftrightarrow a+c\leq b+c\\&a\leq b\Rightarrow ac\leq bc.\end{aligned}}$

Division euclidienne

On note $\mathbb {N} ^{*}:=\mathbb {N} \setminus \{0\}$.

Début d’un théorème

Théorème

Soit $(a,b)\in \mathbb {N} \times \mathbb {N} ^{*}$. Il existe un unique couple $(q,r)\in \mathbb {N} \times \mathbb {N}$, tel que $a=bq+r$ et $r<b$. L'entier $q$ (resp. $r$) est appelé le quotient (resp. le reste) de la division euclidienne de $a$ par $b$.

Fin du théorème

'Démonstration'

Deux entiers $q$ et $r$ vérifient ces deux conditions si et seulement si $bq\leq a$, $r=a-bq$ et $a-bq<b$.

L'entier $r$ est donc uniquement déterminé en fonction de $q$, qui doit vérifier $bq\leq a<b(q+1)$, c'est-à-dire $q=\max\{k\in \mathbb {N} \mid bk\leq a\}$. Un tel entier $q$ (donc un tel couple $(q,r)$) est évidemment unique, et existe car $\{k\in \mathbb {N} \mid bk\leq a\}$ est non vide (il contient 0) et majoré (par $a$).

 

Remarque

On a alors : $a<b(q+1)$. En particulier, $\forall (a,b)\in \mathbb {N} \times \mathbb {N} ^{*}\quad \exists n\in \mathbb {N} \quad nb\geq a$. On résume ce fait en disant que l'ordre sur $\mathbb {N}$ est archimédien.

Définition et proposition : divisibilité, nombres premiers

On définit sur $\mathbb {N}$ une relation binaire, la divisibilité par $\forall m,n\in \mathbb {N} \quad \left(m\mid n\Leftrightarrow \exists k\in \mathbb {N} \quad mk=n\right)$. Dans ce cas, on dit que $m$ divise $n$ ou que $n$ est un multiple de $m$. C'est une relation d'ordre. L'élément minimal est $1$ et maximal est $0$. On appelle nombre premier tout entier naturel admettant exactement deux diviseurs : $1$ et lui-même.

Récurrences

On déduit immédiatement du cinquième axiome de Peano (voir supra), et de l'expression de $S(n)$ sous la forme $n+1$ :

Début d’un théorème

Théorème de récurrence

Si ${\mathcal {P}}$ est une propriété telle 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}}(n+1)\right]$ — c'est l'hérédité,

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

Fin du théorème

En appliquant ce théorème à ${\mathcal {P}}(n):={\mathcal {Q}}(n+n_{0})$, on obtient :

Corollaire 1

Soient $n_{0}\in \mathbb {N}$ et ${\mathcal {Q}}$ une propriété telle que :

• ${\mathcal {Q}}(n_{0})$ est vraie ;
• $\forall n\in \mathbb {N} \quad \left[\left(n\geq n_{0}{\text{ et }}{\mathcal {Q}}(n)\right)\Rightarrow {\mathcal {Q}}(n+1)\right]$.

Alors $\forall n\in \mathbb {N} \quad \left(n\geq n_{0}\Rightarrow {\mathcal {Q}}(n)\right)$ est vrai.

En appliquant le théorème à ${\mathcal {P}}(n):=\left[\forall k\in \mathbb {N} \quad \left(k\leq n\Rightarrow {\mathcal {R}}(k)\right)\right]$, que l'on écrit moins formellement ${\mathcal {R}}(0){\text{ et }}{\mathcal {R}}(1){\text{ et }}\dots {\text{ et }}{\mathcal {R}}(n)$, on obtient un autre corollaire :

Corollaire 2 : récurrence forte

Soit ${\mathcal {R}}$ une propriété telle que :

• ${\mathcal {R}}(0)$ est vraie — c'est l'initialisation de la récurrence ;
• $\forall n\in \mathbb {N} \quad \left[({\mathcal {R}}(0){\text{ et }}{\mathcal {R}}(1){\text{ et }}\dots {\text{ et }}{\mathcal {R}}(n))\Rightarrow {\mathcal {R}}(n+1)\right]$ — c'est l'hérédité.

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

Par contraposition, on déduit du corollaire précédent ou, directement, du cinquième axiome de Peano :

Corollaire 3 : descente infinie

Soit ${\mathcal {R}}$ une propriété telle que :

$\forall n\in \mathbb {N} \quad \left[\neg {\mathcal {R}}(n)\Rightarrow \exists k\in \mathbb {N} \quad k<n{\text{ et }}\neg {\mathcal {R}}(k)\right]$ (où $\neg$ est le symbole de négation).

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