Pour comprendre ce principe, il faut d’abord définir ce qu’est un bon ordre.
Un ensemble $(E, \le)$ est dit bien ordonné si c’est un ensemble totalement ordonné (deux éléments sont toujours comparables) dans lequel tout sous-ensemble non vide possède un plus petit élément.
- L’ensemble des entiers naturels $(\mathbb{N}, \le)$ est l’exemple canonique d’ensemble bien ordonné.
- L’ensemble des entiers relatifs $(\mathbb{Z}, \le)$ ou des réels $(\mathbb{R}, \le)$ ne sont pas bien ordonnés. Par exemple, $\mathbb{Z}$ lui-même n’a pas de plus petit élément, et l’intervalle ouvert $]0, 1[$ n’a pas de plus petit élément dans $\mathbb{R}$.
L’ensemble des entiers naturels $\mathbb{N}$, muni de sa relation d’ordre usuelle $\le$, est bien ordonné. Autrement dit :
Toute partie non vide de $\mathbb{N}$ admet un plus petit élément.
Cette propriété est souvent prise comme un axiome fondamental de l’arithmétique (faisant partie des axiomes de Peano).
Démonstration (à partir du principe de récurrence)
On peut démontrer le principe du bon ordre en supposant le principe de récurrence comme acquis. La démonstration se fait par l’absurde.
- Hypothèse par l’absurde : Supposons qu’il existe une partie non vide $A \subseteq \mathbb{N}$ qui n’admet pas de plus petit élément.
- Construction d’une propriété : Soit $P(n)$ la propriété « l’entier $n$ n’appartient pas à $A$ ». Nous allons montrer par récurrence forte que $P(n)$ est vraie pour tout $n \in \mathbb{N}$.
- Base (n=0) : Montrons que $P(0)$ est vraie, c’est-à-dire $0 \notin A$. Si $0$ était dans $A$, il serait nécessairement le plus petit élément de $A$ (puisqu’il n’y a pas d’entier naturel plus petit). Or, nous avons supposé que $A$ n’a pas de plus petit élément. Donc, $0 \notin A$. La propriété $P(0)$ est vraie.
-
Hérédité : Supposons que pour un entier $k \ge 0$, la propriété $P(i)$ est vraie pour tous les entiers $i$ de 0 à $k$. Cela signifie que $\{0, 1, \dots, k\} \cap A = \emptyset$. Montrons que $P(k+1)$ est vraie, c’est-à-dire $(k+1) \notin A$.
Si $(k+1)$ appartenait à $A$, comme aucun entier plus petit que lui n’est dans $A$, il serait le plus petit élément de $A$. Ceci contredit notre hypothèse initiale. Par conséquent, $(k+1) \notin A$. - Conclusion de la récurrence : Par le principe de récurrence, la propriété $P(n)$ est vraie pour tout $n \in \mathbb{N}$. Cela signifie qu’aucun entier naturel n’appartient à $A$, et donc que $A$ est vide.
- Contradiction finale : Nous arrivons à la conclusion que $A$ est vide, ce qui contredit notre hypothèse de départ selon laquelle $A$ était une partie non vide. L’hypothèse de départ est donc fausse, et toute partie non vide de $\mathbb{N}$ doit admettre un plus petit élément.
Tout ensemble peut être muni d’une relation de bon ordre.
Remarques et Équivalence avec l’Axiome du Choix
Cette version générale est un théorème beaucoup plus puissant et non-intuitif que le principe appliqué à $\mathbb{N}$.
- Équivalence : Le théorème du bon ordre est logiquement équivalent à l’Axiome du Choix et au Lemme de Zorn. Accepter l’un de ces trois énoncés comme axiome revient à accepter les deux autres.
- Caractère non constructif : Le théorème garantit l’existence d’un bon ordre sur n’importe quel ensemble (comme $\mathbb{R}$), mais il ne donne aucune méthode pour le construire. Un bon ordre sur $\mathbb{R}$ serait très « exotique » et complètement différent de l’ordre usuel.
Implications et Utilisation
- Fondement de la récurrence : Le principe du bon ordre sur $\mathbb{N}$ est la justification la plus profonde du raisonnement par récurrence. Il garantit qu’il ne peut pas exister de suite infinie strictement décroissante d’entiers naturels.
- Induction Transfinie : Le théorème général de Zermelo permet d’étendre le principe de récurrence à des ensembles non dénombrables, une technique appelée « induction transfinie », qui est un outil essentiel en théorie des ensembles.