Mon but initial était de trouver un bon ordre sur ℝ alors qu'on ne connait au mieux qu'une relation d'ordre total sur ℝ ! Par la suite, j'ai généralisé le problème en essayant de démontré que « Tout ensemble construit à partir d'ensembles bien ordonnables est bien ordonnable ». Évidemment, comme ℝ peut être construit à partir de ℕ et ℚ, ensembles dont on sait qu'ils sont bien ordonnables, il en découle que ℝ peut lui aussi être muni d'une structure de bon ordre.
Pour la démonstration, il faut détailler pour chaque axiome de construction, l'existence d'un bon ordre sur le nouvel ensemble. Cela se fait plus ou moins facilement, sauf pour l'axiome des parties qui m'a posé plus de problème (il occupe deux pages WEB pour lui seul). La page sur l'ensemble des parties d'un ensemble bien ordonnable est finie, mais la proposition 4.5 n'est pas bien démontré.
Quelques années après avoir réalisées ces pages, je me suis rendu compte que la démonstration ne pouvait pas être achevée en prouvant que " est bien ordonnable pour tout ensemble E bien ordonnable" était indécidable dans ZF. De plus, on peut contruire un modèle de ZF dans lequel n'est pas bien ordonnable... - Frédéric, jeudi 16 août
Avant de parler d'ensembles bien ordonnables, précisons tout d'abord que nous nous servirons pour nos démonstrations, des axiomes de la théorie des ensembles (sans l'axiome du choix) ainsi que des définitions qui en découlent : ensemble vide, intersections, relations d'ordres...
Soit donc E un ensemble. On dit que E est bien ordonnable si on peut le munir d'une relation d'ordre strict <E tel que (E, <E) est bien ordonné, c'est-à-dire tel que toute partie non vide de E possède un plus petit élément que l'on notera, quand aucune confusion n'est à craindre, min(E). De même, on notera ≤E l'inégalité large correspondant à <E, c'est-à-dire pour tous éléments x et y de E, x ≤E y ⇔ (x <E y ⊦ x = y). ≤E est alors réflexive, il restera à chaque fois à démontrer qu'elle est aussi symétrique et transitive pour prouver que c'est une relation d'ordre, et donc que <E est une relation d'ordre strict. Le théorème de Zermelo, équivalent à l'axiome du choix, affirme que tout ensemble est bien ordonnable, mais n'indique pas de moyen pour trouver, sur un ensemble donné, une relation de bon ordre.
Le but recherché est simple : en utilisant les axiomes de construction de la théorie des ensembles, on prouve l'existence de nouveaux ensembles à partir d'ensembles déjà existants. Nous allons donc démontré que tout ensemble construit à partir d'ensembles bien ordonnables est bien ordonnable, en donnant une relation de bon ordre sur cet ensemble. Notons enfin que chaque fois qu'on montrera qu'un ensemble est bien ordonnable, on aura aussi trouvé une fonction de choix sur cet ensemble : celle qui associe à une partie non vide de E son plus petit élément.
Lorsque l'on contruit, via le schéma d'axiomes de compréhension, un ensemble E' à partir d'un ensemble E bien ordonnable, on obtient un sous-ensemble de E. L'ensemble E' est alors bien ordonné par le bon ordre induit de E puisque toute partie non vide de E' est une partie non vide de E et possède un plus petit élément.
Il est facile de bien ordonner une paire de deux ensembles A et B en choisissant arbitrairement un plus petit élément. On obtient ainsi la relation <{A,B} = {(A,B)} dont on montre aisément que c'est une relation de bon ordre avec min({A,B}) = A. Cette relation est ici donnée en terme d'ensemble, elle signifie que sur l'ensemble {A,B} on a seulement l'inégalité A <{A,B} B.
Soit F[a,b] une fonctionnelle et E un ensemble bien ordonné par la relation <E. D'après l'axiome de compréhension, pour tout élément x de F(E), il existe un ensemble Ax = {a∈E | F[a,x]}. Ax est une partie non vide de E (ou sinon x ∉ F(E)) et possède un plus petit élément que l'on notera ax. F(E) est alors bien ordonné par la relation <F(E) définie ainsi : ∀(x,y)∈F(E)2, x <F(E) y ⇔ ax <Eay
Soit I un ensemble bien ordonné par la relation <i, et dont
chaque élément i est bien ordonné par une relation <i. D'après
l'axiome de compréhension, pour tout élément x de ∪I, il existe un
ensemble Ix = {i∈I | x∈i}. Ix est alors
une partie non vide de I (ou sinon x ∉ ∪I) et possède un plus
petit élément que l'on notera ix. ∪I est bien ordonné par la
relation <∪I définie ainsi :
∀(x,y)∈∪I2, x <∪I y
⇔ [ [ ix ≤i iy ]
∧ [ (ix=iy) → (x y) ] ]
Soit E un ensemble bien ordonné par la relation <E. Alors
℘(E) est bien ordonné par la relation <℘(E)
définie ainsi :
∀(X,Y)∈℘(E)2, X<℘(E)Y
⇔ [ (X≠Y) ∧
(min((X∪Y)\(X∩Y))∈X) ]
On a finalement réussi à montrer que « Tout ensemble construit à partir d'ensembles bien ordonnables est bien ordonnable ». On peut donc maintenant utiliser ce résultat pour construire d'autres bons ordres sur les objets mathématiques usuels.
Soient x1, x2, x3,... , xn des ensembles. Alors il existe un unique (axiome d'extensionnalité) ensemble donc les éléments sont exactement ces ensembles. Cet ensemble est bien ordonnable et on le note {x1, x2, x3,... , xn}.
Démontrons-le par récurrence. Pour n=1 et n=2, a déjà montré plus haut l'existence d'un tel ensemble bien ordonnable. Supposons donc que n > 2. On pose alors A={x1, x2, x3,... , xn - 1} qui par hypothèse de récurrence, existe et est bien ordonnable et B={xn} qui existe par l'axiome de la paire et est aussi bien ordonnable. On se sert une nouvelle fois de l'axiome de la paire pour prouvé l'existence de l'ensemble bien ordonnable I={A,B}. Puis on construit la réunion de I et on obtient l'ensemble ∪I={x1, x2, x3,... , xn}. De plus, les ensembles I, A et B étant bien ordonnables, ∪I l'est aussi. Cqfd.
Soient E un ensemble bien ordonnable et R une relation d'équivalence sur cet ensemble (réflexive, symétrique et transitive). On rappel que l'ensemble quotient E/R est l'ensemble dont les éléments sont des classes d'équivalence pour la relation R (sous-ensemble de E dont les éléments sont équivalents pour R). Cet ensemble est inclus dans ℘(E) et est donc bien ordonnable.
On peut cependant trouver un bon ordre sur E/R sans passer par l'ensemble des parties. En effet, les classes d'équivalence possèdent la particularité d'être toutes disjointes entre elles. Pour comparer ces classes d'équivalence, il suffit donc de comparer leurs minima (qui existent car une classe d'équivalence est inclus dans E). Le bon ordre sur E assure alors celui sur E/R pour la relation suivante :
Tous ces objets se construisent aussi à partir des axiomes de ZF, ce qui permet encore d'obtenir des bon ordres pour l'ensemble des applications d'un ensemble dans un autre, pour un produit cartésien de deux ensembles etc... Pour plus de détails, regardez dans la partie cours...
Dans la suite, on donnera la façon dont sont construits les ensembles de nombres, pour pouvoir ainsi montrer qu'ils peuvent être munis d'une structure de bon ordre, mais on ne rentrera pas en détail dans leurs propriétés algébriques.
Il existe plusieurs définition de l'ensemble des entiers naturels. Dans le cadre de la théorie des ensembles, on peut la construire à l'aide de l'axiome suivant :
On peut à partir de ces 3 propriétés définir une addition, une multiplication, une division euclidienne, la notion de successeur, de principe de récurrence... On note évidemment 0 = ∅, 1 = 0 ∪ {0}, 2 = 1 ∪ {1}, 3 = 2 ∪ {2} et ainsi de suite, tandis que nous noterons la relation de bon ordre pour l'inclusion ≤ℕ (qui est aussi la relation d'ordre ≤). Ainsi, (ℕ, ≤ℕ) est bien ordonné.
Ces deux ensembles peuvent être mis en bijection avec ℕ, et sont par conséquent bien ordonnables. Nous allons cependant utiliser une nouvelle fois notre méthode pour construire un bon ordre sur ces ensembles.
Soit R la relation d'équivalence sur ℕ × ℕ définie ainsi :
(n1, n2) R (n'1, n'2)
⇔ n1 + n'2 = n1' +
n2
ℕ est bien ordonnable donc ℤ = ℕ × ℕ / R peut aussi être
muni d'un bon ordre <ℤ.
Finalement, (ℤ, <ℤ) est bien ordonné (mais ce n'est
pas le cas de (ℤ, <) !).
Pour ℚ, on procède de la même façon, à l'aide de la relation d'équivalence R' sur ℤ × $* définie par : (z1, z2) R' (z'1, z'2) ⇔ z1 × z'2 = z1' × z2. On pose alors ℚ = ℤ × $ / R', que l'on muni là encore d'un bon ordre <ℚ. Par conséquent, (ℚ, <ℚ) est donc lui aussi bien ordonné.
Pour définir ℝ, on utilise en général la construction à l'aide des suites de Cauchy de rationnels. Une suite de rationnels est une application u : ℕ → ℚ, notons l'ensemble de ces applications S. Comme ℕ et ℚ sont bien ordonnables, S l'est aussi, comme on la vu précédemment. On peut en plus le munir d'une structure d'anneau abélien, en reprenant les opérations de ℚ. Rapidement, la suite u + v (respectivement u × v) est définie comme la somme (respectivement le produit) terme à terme de u et v, l'élément neutre pour l'addition (respectivement la multiplication) est la suite dont les termes sont tous nuls (respectivement égaux à 1) et -u comme la suite comportant les opposés des termes de u.
On s'intéresse ensuite à deux sous-ensembles de S, définis par l'axiome de compréhension (ils sont de ce fait biens ordonnables) : C qui est l'ensemble des suites de Cauchy, c'est-à-dire telles qu'à partir d'un certain rang, la différence entre deux termes de la suite est "aussi petite que l'on veut" ; et I l'ensemble des suites de Cauchy qui tendent vers zéro. On démontre ensuite que C est un sous-anneau de S, et I un idéal de C, et il s'ensuit que C/I est muni d'une structure d'anneau. Pour rappel, cet ensemble est défini comme l'ensemble quotient C/R, où R est la relation d'équivalence sur C : u R v ⇔ u - v ∈ I. Comme C est bien ordonnable, et que R est une relation d'équivalence, on a donc C/R = C/I qui est bien ordonnable.
En réalité, il faut savoir que C/I peut être muni d'une structure de corps et on pose donc ℝ = C/I. Cela qui signifie que l'on peut trouver <ℝ tel que (ℝ, <ℝ) est bien ordonné.
