$\mathbb N$ (4). Relation d'ordre $\leq$.

Cet article fait suite à 

• [N1] $\mathbb N$ (1). Définition de l'ensemble des entiers naturels. Axiomes de Peano. Récurrence.
• [N2] $\mathbb N$ (2) Addition des nombres entiers naturels.
• [N3] $\mathbb N$ (3). La multiplication.

 De la façon dont $\mathbb N$ a été construit (axiomes de Peano) $0$ est le plus petit élément de $\mathbb N$. 

Nous allons ordonner de manière évidente les éléments de $\mathbb N$ : 

$$0,1,2,3 \ldots$$

Ceci définira une relation $\leq$ sur $\mathbb N$ appelée relation d'ordre. 

Nous verrons aussi quelques propriétés vérifiées par $"\leq"$ en rapport avec les opérations de $\mathbb N$ définies dans les articles précédents, l'addition et la multiplication.

Définition de la relation $\leq$

Pour tout $a\in \mathbb N$, si $b=a+n$, avec $n\in \mathbb N$, on note $a\leq b$, et on dit que $a$ est inférieur ou égal à $b$.

Remarquons en particulier que pour tout $n$, $0\leq n$.

Propriété 1 (réflexivité). Pour tout $a\in\mathbb N$, $a\leq a$. 

Preuve. $a=a+0$.

Lemme A. Si $a=a+k$, alors $k=0$.

Démonstration. Par récurrence sur $a$. 

Si $a=0$, alors $0=0+k$ implique $0=k$, ce qui initialise la propriété.

Supposons que $a=a+k$ implique $k=0$, et supposons que $a+1=(a+1)+k$. 

Le successeur de $a$ est $a+1$ et le successeur de $a+k$ est $(a+k)+1=(a+1)+k$ par commutativité et associativité de l'addition. Comme $a$ et $(a+k)$ ont le même successeur $a+1=(a+1)+k$, ils sont égaux d'après l'axiome N°4 de Peano. Donc $a=a+k$, d'où l'on déduit par l'hypothèse de récurrence que $k=0$. 

Propriété 2 (antisymétrie). Si $a\leq b$ et $b\leq a$, alors $a=b$.

Démonstration. $a\leq b$ implique $b=a+c$ et $b\leq a$ implique $a=b+d$. On en déduit que $$a=b+d=(a+c)+d=a+(c+d)$$

En prenant $k=c+d$, le lemme A nous permet de conclure. 

Lemme B. 

Tout entier $a$ différent de 0 admet un prédécesseur, nous le noterons $a-1$. 

Démonstration. En effet, cela sur montre par récurrence sur $a$ : "Si $a$ est un entier naturel, soit $a=0$ soit $a$ est le successeur d'un entier naturel $b$, i.e. $a=b+1$."

• Initialisation. Si $a=0$, alors $a$ la propriété est vérifiée.
• Hérédité. Supposons que "Si $a$ est un entier naturel, soit $a=0$ soit $a$ est le successeur d'un entier naturel $b$, i.e. $a=b+1$."

Alors $a+1$ est clairement le successeur de $a$. (On n'utilise pas l'hypothèse de récurrence !)

Propriété 3 (transitivité). Si $a\leq b$ et $b\leq c$, on a $a\leq c$.

Démonstration. $b=a+k$ et $c=b+m$ donc $c=(a+k)+m=a+(k+m)$.

Ces trois propriétés (réflexivité, antisymétrie et transitivité) font de la relation $\leq$ ce que l'on appelle une relation d'ordre.

Propriété 4 (totalité). Si $a$ et $b$ sont deux entiers naturels, alors on a toujours $a\leq b$ ou $b\leq a$.

Démonstration. Faisons une démonstration par récurrence sur $b$. 

Si $b=0$, c'est vrai, car $0\leq a$. 

Supposons que pour un certain $b$, $b \leq a$ ou $a\leq b$ et montrons que cela implique $a\leq b+1$ ou $b+1\leq a$.

Cas où $a\leq b$. Alors $b=a+c$ donc $b+1=(a+c)+1=a+(c+1)$, et $a\leq b+1$. 

Cas où $b\leq a$. Alors $a=b+c$. Si $c=0$, alors $b=a=a+0$ donc $a\leq b$, et on est ramené au cas précédent. Supposons donc $c$ différent de $0$. $c$ est donc le successeur d'un nombre $c-1$, ou encore $c=(c-1)+1$. On ainsi $$a=b+c=b+((c-1)+1)=(b+1)+(c-1)$$ par commutativité et associativité de l'addition.  

Par conséquent $b+1\leq a$.

Cette dernière propriété (totalité) fait de $\leq$ ce que l'on nomme une relation d'ordre totale. 

Compatibilité de $\leq$ avec $+$ et $\times$

Propriété 5. 

Si $a\leq b$ et $c\leq d$, alors $a+c\leq b+d$. 

En particulier $a+c\leq b+c$.

Preuve. On a $b=a+n$ et $d=c+m$, donc $b+d=(a+n)+(c+m)=(a+c)+(n+m)$. On obtient la suite avec $c=d$.

Propriété 6. 

Si $a\leq b$, alors pour tout entier naturel $k$, on a $k\times a\leq k \times b$.

Preuve. On suppose $a\leq b$. Par récurrence sur $k$.

Si $k=0$, alors $k\times a=0$ et $k\times b =0$ donc la propriété est initialisée. 

Supposons que $k\times a\leq k\times b$. D'après la propriété 5, on a donc $(k\times a)+a\leq (k\times b)+b$, c'est-à-dire $(k+1)\times a \leq (k+1)\times b$.

La relation $\geq$

Si $a\leq b$, on note $b\geq a$ et on dit que $b$ est supérieur à $a$.

On vérifier facilement que $\geq$ est aussi une relation d'ordre totale sur $\mathbb N$.

On remarque également en utilisant la réflexivité de $\leq$ que

$$a=b \Longleftrightarrow a\leq b\ \textrm{et}\ b\geq a$$

Les relations $<$ et $>$

Si $a\leq b$ et $a\neq b$, on note $a<b$. On dit alors que $a$ est strictement inférieur à $b$. 

On a donc une relation $<$ que n'est pas réflexive. Elle est dite antiréflexive. 

La transitivité est vraie pour $<$. 

La totalité de $<$ est stricte dans le sens ou deux éléments distincts $a$ et $b$ vérifient $a<b$ ou bien $b<a$.

Concernant l'antisymétrie, elle est vraie car on ne peut pas avoir à la fois $a<b$ et $b<a$.

On dit que $<$ est une relation d'ordre stricte totale. 

La relation $>$ définie par 

$$a>b \Longleftrightarrow b<a$$

est clairement aussi une relation d'ordre stricte totale. On dit que $a$ est strictement supérieur à $b$.

Propriété A. 

Si $a<b$ alors $a+k<b+k$.

Démonstration.

Par récurrence sur $k$.

• Si $k=0$, il n'y a rien à montrer.
• Supposons que pour tous $a,b$, avec $a<b$ : $a<b$ implique $a+k<b+k$. 
  Alors d'après la propriété 5, comme  $a+k\leq b+k$, on a $a+k+1\leq b+k+1$.
  Si $a+k+1=b+k+1$, alors par unicité du prédécesseur, $a+k=b+k$ contredisant $a+k<b+k$. 

Propriété B. 

Soit $k$ un entier naturel différent de $0$.

(1) Si $ak=bk$, alors $a=b$.

(2) Si $ak\leq bk$, alors $a\leq b$.

Preuve. 

(1) Si $a\neq b$, disons $a<b$, alors $ak<bk$.

(2) Si $a>b$, alors $ak >bk$. 

Et ensuite

Dans des articles à venir, nous pourrons définir la soustraction des entiers naturels et la division euclidienne. Nous pourrons aussi aborder la méthode de descente infinie de Fermat.