Bon ordre

Imaginez les entiers naturels rangés sur un escalier : 0, 1, 2, 3, puis tous les suivants. Si vous marquez au moins une marche, il existe toujours une première marche marquée. Les marques peuvent être très espacées ou infiniment nombreuses ; l'une d'elles vient néanmoins avant toutes les autres.

Le principe du bon ordre transforme cette image en outil de preuve. Si des contre-exemples existaient parmi les entiers naturels, leur ensemble aurait un plus petit élément. On étudie alors ce premier contre-exemple et l'on cherche une contradiction avec le fait que tous les entiers précédents satisfont la propriété.

Notons ℕ l'ensemble des entiers naturels, que la convention choisie fasse commencer cet ensemble à 0 ou à 1. Pour toute partie A de ℕ qui n'est pas vide, le principe du bon ordre garantit l'existence d'un entier m appartenant à A et inférieur ou égal à chacun de ses éléments :L'entier m est le plus petit élément de A. Il est unique, car deux plus petits éléments seraient chacun inférieur ou égal à l'autre.

Cette propriété est équivalente à la récurrence forte sur ℕ. Pour établir une propriété P au rang n, la récurrence forte autorise l'hypothèse que P est vraie à tous les rangs k strictement inférieurs à n. Réciproquement, si P avait des contre-exemples, le bon ordre fournirait le premier ; l'hypothèse portant sur tous les rangs antérieurs conduirait alors à une contradiction.

Dans un ensemble E quelconque, une relation d'ordre est un bon ordre lorsqu'elle compare toute paire d'éléments et que toute partie non vide de E possède un plus petit élément pour cette relation. Le théorème du bon ordre étend donc le schéma de ℕ : en admettant l'axiome du choix, tout ensemble peut recevoir un tel ordre. Un ensemble ainsi ordonné a un type d'ordre représenté de manière canonique par un ordinal de von Neumann.

Montrons que tout entier naturel n supérieur ou égal à 2 possède un diviseur premier. La preuve applique le bon ordre à l'ensemble hypothétique des contre-exemples.

Données :
C est l'ensemble des entiers naturels n ≥ 2 qui n'ont aucun diviseur premier ;
on suppose, pour obtenir une contradiction, que C n'est pas vide ;
m désigne alors le plus petit élément de C.

1. L'entier m n'est pas premier, car un nombre premier se divise lui-même.
2. Comme m ≥ 2 et n'est pas premier, il existe des entiers a et b tels que m = ab, avec 2 ≤ a < m.
3. Puisque a est plus petit que m, la minimalité de m impose que a n'appartienne pas à C. L'entier a possède donc un diviseur premier p.
4. Le nombre p divise a et a divise m ; ainsi p divise m. Cela contredit l'appartenance de m à C.

L'hypothèse C non vide est donc impossible : tout entier naturel n ≥ 2 possède bien un diviseur premier. Pour contrôler la chaîne décisive, on vérifie que 2 ≤ a < m autorise l'usage de la minimalité, puis que la divisibilité est transitive de p à a et de a à m.

Dans une preuve sur les entiers naturels, le bon ordre est utile lorsque raisonner sur le plus petit contre-exemple rend la contradiction visible. La récurrence forte est l'alternative naturelle lorsque la construction de chaque rang dépend explicitement de plusieurs rangs antérieurs.

Pour justifier qu'une procédure choisit un premier entier admissible, on vérifie d'abord que l'ensemble des candidats est une partie non vide de ℕ. Le bon ordre fournit alors un candidat minimal ; il ne prouve pas, à lui seul, que toute procédure répétée s'arrête.

En théorie des ensembles, on emploie le théorème du bon ordre quand il faut comparer un ensemble à un ordinal. Si seul l'ordre usuel des entiers intervient, le principe du bon ordre sur ℕ suffit et évite de mobiliser l'axiome du choix.

Ordre total. Un ordre total compare chaque paire d'éléments, mais il n'est pas forcément un bon ordre. Les entiers relatifs munis de l'ordre usuel sont totalement ordonnés ; leur ensemble entier n'a pourtant pas de plus petit élément.

Ordre bien fondé. Une relation est bien fondée lorsque toute partie non vide possède au moins un élément minimal, sans que tous ses éléments soient nécessairement comparables. Pour parler de bon ordre dans le cadre de la fiche, il faut en plus un ordre total.

Élément minimal. Dans un ordre partiel, plusieurs éléments peuvent être minimaux parce qu'aucun élément ne leur est strictement inférieur. Un plus petit élément est inférieur ou égal à tous les autres ; s'il existe, il est unique.

Ensemble vide. Le principe exige une partie non vide. Si aucun candidat n'existe, chercher son plus petit élément n'a pas de sens ; il faut d'abord établir l'existence d'au moins un élément.

Mauvais ensemble de départ. L'ordre usuel fonctionne sur ℕ, mais pas sur ℤ tout entier : pour chaque entier relatif, il en existe un plus petit. Une preuve par premier contre-exemple doit donc situer ses contre-exemples dans une partie de ℕ, ou justifier un autre bon ordre.

Ordre non précisé. Le théorème général affirme qu'un bon ordre peut être placé sur tout ensemble en admettant l'axiome du choix. Il ne dit pas que l'ordre habituel ou le premier ordre imaginé possède cette propriété ; la relation utilisée doit être nommée.

Existence contre construction. Savoir qu'un bon ordre existe ne fournit pas nécessairement une règle explicite pour classer les éléments. Il faut distinguer l'argument d'existence de la description effective de l'ordre.

Bien ordonné (ensemble) — Approfondir la propriété qui exige un premier élément dans chaque partie non vide.

axiome du choix — Situer l'hypothèse qui permet d'étendre le bon ordre à un ensemble quelconque.

nombre ordinal — Relier un ensemble bien ordonné au représentant canonique de son type d'ordre.

Entiers naturels — Revoir le domaine sur lequel le principe du bon ordre et la récurrence forte s'équivalent.