L’ensemble des entiers naturels noté $\N$ est formé de tous les entiers positifs en commençant par $0$ qui est lui aussi positif.
Il est impossible de démontrer que l’ensemble $\N$ existe : on travaille à partir d’axiomes qui justifient son existence.
L’ensemble $\N$ possède deux propriétés fondamentales qui sont équivalentes :
- Le « bon ordre ». Toute partie de $\N$, non vide, admet un plus petit élément.
- Le « principe » de récurrence. Pour tout entier $n\in\N$, notez $P(n)$ une propriété qui peut être vraie ou fausse en fonction de la valeur de l’entier naturel $n$. Supposez que $P(0)$ soit vraie (on parle d’initialisation) et que l’implication $\forall n\in\N, P(n)$ vraie $\Longrightarrow P(n+1)$ vraie soit vérifiée (on parle d’hérédité). Alors la propriété $P(n)$ est vraie quel que soit l’entier naturel $n$.
Note : selon la théorie utilisée, le principe de récurrence peut être considéré comme un axiome ou un théorème.
Passez maintenant à l’équivalence des deux énoncés.
Le bon ordre implique le principe de récurrence
Supposez que $\N$ possède la propriété suivante : « toute partie de $\N$ non vide admet un plus petit élément ».
Pour tout entier naturel $n$, on note $P(n)$ une propriété vraie ou fausse, vérifiant les conditions suivantes.
$P(0)$ est vraie et $\forall n\in\N, P(n)$ vraie $\Longrightarrow P(n+1)$ vraie.
Vous voulez montrer que $P(n)$ est vraie pour tout entier naturel $n$. Vous allez considérer l’ensemble noté $A$ des entiers naturels $n$ tels que $P(n)$ soit fausse.
Si $A$ n’est pas vide, alors $A$ admet un plus petit élément noté $a$. Notez que $a=0$ donne $P(a)$ vraie ce qui contredit le fait que $a\in A$. Par conséquent, $a\neq 0$ donc $a\geq 1$ et $a-1 \in \N$. Comme $a-1$ est strictement inférieur à $a$, $a-1\notin A$, donc $P(a-1)$ est vraie. Du coup, $P(a-1+1)$ est vraie et $P(a)$ est vraie donc $a\notin A$, contradiction.
Il en résulte que $A$ est vide, donc $\forall n\in\N$, la propriété $P(n)$ est vraie.
Le principe de récurrence implique que le bon ordre
Partir d’une partie de $\N$ non vide et chercher un plus petit élément est quelque chose de délicat.
Le principe, c’est de regarder si $0$ est un élément de cette partie. Si oui, c’est le plus petit élément recherché. Sinon, vous regardez si $1$ est un élément de cette partie, et ainsi de suite…
Pour traduire rigoureusement le « ainsi de suite », vous utiliserez le principe de récurrence pour montrer que si une partie de $\N$ n’admet pas de plus petit élément, alors elle est vide.
Supposez que $\N$ vérifie le principe de récurrence et notez $A$ une partie de $\N$ n’admettant pas de plus petit élément.
Pour tout entier naturel $n$, vous notez $P(n)$ la propriété : « Pour tout entier naturel $k$ inférieur ou égal à $n$, $k\notin A.$ »
Initialisation : pour $k=0$. Si $0$ appartenait à $A$, alors $0$ serait le plus petit élément de $A$, contradiction. Donc $0\notin A$ et par conséquent $P(0)$ est vérifiée.
Hérédité : soit $n$ un entier naturel. Supposez que $P(n)$ est vérifiée.
Notez que tous les entiers naturels $k$ compris entre $0$ et $n$ n’appartient pas à $A$. Si $n+1$ appartenait à $A$, $n+1$ serait le plus petit élément de $A$, contradiction. Donc $n+1\notin A$.
Conclusion : vous venez de montrer que $\forall n\in\N$, $P(n)$ est vraie. Vous en déduisez que $\forall n\in\N, n\notin A.$ Comme $A$ est une partie de $\N$, il s’ensuit que $A$ est vide.
Par contraposée, si $A$ est une partie non vide de $\N$, elle admet un plus petit élément.
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !