Ensemble bien ordonné

En mathématiques, un ensemble ordonné (E, ≤) est bien ordonné et la relation ≤ est un bon ordre si la condition suivante est satisfaite :

Toute partie non vide de E possède un plus petit élément. Formellement cela donne ∀X⊆E, X≠∅ ⇒ (∃u∈X, ∀v∈X u≤v).

Si (E, ≤) est bien ordonné alors ≤ est nécessairement un ordre total, c'est-à-dire que deux éléments quelconques x et y de E sont toujours comparables. En effet, l'ensemble { x, y } possède un plus petit élément, donc on a x ≤ y ou y ≤ x.

Si de plus l'axiome du choix dépendant est vérifié, cette propriété (être bien ordonné) est équivalente, pour un ordre présupposé total, à la condition de chaîne descendante « il n'existe pas de suite infinie strictement décroissante ». D'après le théorème de Zermelo, l'axiome du choix dans toute sa force équivaut au fait que tout ensemble peut être bien ordonné.

Exemples et contre-exemples

• Toute partie d'un ensemble bien ordonné est elle-même bien ordonnée (pour l'ordre induit).
• L'ensemble vide est bien ordonné par sa seule relation : (Ø, Ø) (c'est le plus petit ordinal).
• Plus généralement, tout ensemble totalement ordonné fini est bien ordonné. Un tel ensemble ordonné est caractérisé (à isomorphisme près) par le nombre n d'éléments de l'ensemble, ce qui légitime la notation n pour le type d'ordre correspondant.
• Si ${\displaystyle \leq }$ définit un ordre bien fondé sur ${\displaystyle (E,\leq )}$ et ${\displaystyle C}$ une chaîne de ${\displaystyle (E,\leq )}$, la restriction ${\displaystyle (C,\leq )}$ est un bon ordre.
• L'ensemble (ℕ, ≤) des entiers naturels, muni de son ordre usuel, est bien ordonné ; il est souvent noté ω dans ce contexte.
• Si ${\displaystyle (E_{i},\leq _{i})_{i\in I}}$ est une famille d'ensembles bien ordonnés et si ${\displaystyle I}$ est muni d'un bon ordre, alors :
  • si ${\displaystyle I}$ est fini, sur le produit ${\displaystyle \prod _{i\in I}E_{i}=\{(x_{i})_{i\in I}\mid \forall i\in I,\ x_{i}\in E_{i}\}}$, l'ordre lexicographique est un bon ordre. Pour quatre exemples de produits d'un couple de bons ordres, voir n×p, 2×N, N×2 et N×N (isomorphes respectivement aux ordinaux produits pn, ω2, 2ω (= ω) et ω^2) ;
  • l'union disjointe ${\displaystyle \bigsqcup _{i\in I}E_{i}=\{(i,x)\mid i\in I,\ x\in E_{i}\}}$ est bien ordonnée par : ${\displaystyle (i,x)\leq (j,y)}$ si ${\displaystyle i<j}$ ou (${\displaystyle i=j}$ et ${\displaystyle x\leq _{i}y}$). Ce bon ordre s'appelle la somme ordinale de la famille[1]. Remarquons que ${\displaystyle \sum _{i\in I}E=I\times E}$. La somme ordinale d'un couple ${\displaystyle (A,B)}$ de bons ordres se note ${\displaystyle A+B}$[1]. Pour trois exemples, voir ω + ω (= ω2) et 3 + ω, ω + 3 (⊂ ω2).

Démonstration

• Produit cartésien (fini) : on raisonne par récurrence sur le cardinal de ${\displaystyle I}$ :
  • initialisation : si ${\displaystyle |I|=0}$, c'est-à-dire ${\displaystyle I=\varnothing }$, alors ${\displaystyle \prod _{i\in I}E_{i}}$ est réduit à un singleton (rigoureusement, celui contenant la suite vide : ${\displaystyle \{()\}}$), donc bien ordonné ;
  • hérédité : on suppose la propriété génériquement vraie pour tout ensemble d'indices de cardinal n ; on suppose ${\displaystyle |I|=n+1}$. Soit A une partie non vide de ${\displaystyle \prod _{i\in I}E_{i}}$. I étant bien ordonné, il admet un plus petit élément i₀ ; on pose ${\displaystyle I'=I\setminus \{i_{0}\}}$, puis ${\displaystyle E'=\prod _{i\in I'}E_{i}}$ et ${\displaystyle A_{i_{0}}=\pi _{i_{0}}(A)}$ (où ${\displaystyle \pi _{i_{0}}}$ désigne la projection canonique sur la composante i₀). On définit alors A' par ${\displaystyle A'=\{(x_{i})_{i\in I'}\in E'\mid (x_{i})_{i\in I}\in A\ \ \mathrm {et} \ x_{i_{0}}=\operatorname {min} (A_{i_{0}})\}}$, ce qui est légitime puisque A_i0 est une partie non vide (par non-vacuité de A) de l'ensemble ordonné E_i0 et donc admet bien un minimum. A' est alors non vide (toujours parce que A ne l'est pas non plus) ; or c'est une partie de l'ensemble E', qui est bien ordonné (pour l'ordre lexicographique induit) par hypothèse de récurrence puisque ${\displaystyle |I'|=n}$, et par voie de conséquence, A' possède un plus petit élément ${\displaystyle (m_{i})_{i\in I'}}$.
    En notant ${\displaystyle m_{i_{0}}=\operatorname {min} (A_{i_{0}})}$, on obtient avec ${\displaystyle (m_{i})_{i\in I}}$ un minimum de A : en effet, si ${\displaystyle (x_{i})_{i\in I}\in A}$, alors ${\displaystyle m_{i_{0}}\leq x_{i_{0}}}$ ; il y a une alternative : soit ${\displaystyle m_{i_{0}}<x_{i_{0}}}$, et alors ${\displaystyle (m_{i})_{i\in I}\leq _{\mathrm {lex} _{I}}(x_{i})_{i\in I}}$, soit ${\displaystyle m_{i_{0}}=x_{i_{0}}}$, et on a alors ${\displaystyle (x_{i})_{i\in I'}\in A'}$, d'où ${\displaystyle (m_{i})_{i\in I'}\leq _{\mathrm {lex} _{I'}}(x_{i})_{i\in I'}}$ par minimalité de ${\displaystyle (m_{i})_{i\in I'}}$ dans A', ce qui, d'après la définition récursive de l'ordre lexicographique, redonne bien ${\displaystyle (m_{i})_{i\in I}\leq _{\mathrm {lex} _{I}}(x_{i})_{i\in I}}$.

• Somme disjointe : soit A une partie non vide de ${\displaystyle \bigsqcup _{i\in I}E_{i}}$. On pose ${\displaystyle I_{A}=\{i\in I\mid \exists x\in E_{i},(i,x)\in A\}}$ ; I_A est une partie de I non vide puisque A est non vide, donc, I étant bien ordonné, I_A admet un minimum i₀. On définit ensuite E' par ${\displaystyle E'=\{x\in E_{i_{0}}\mid (i_{0},x)\in A\}}$ ; E' est une partie non vide de E_i0 par construction, or ce dernier est bien ordonné, donc E' possède un plus petit élément x₀.
  On vérifie alors que (i₀, x₀) est le minimum de A pour l'ordre de la somme ordinale : si ${\displaystyle (i,x)\in A}$, alors ${\displaystyle i\in I_{A}}$ et donc ${\displaystyle i_{0}\leq i}$ ; si ${\displaystyle i_{0}<i}$, on a bien ${\displaystyle (i_{0},x_{0})\leq (i,x)}$, sinon, ${\displaystyle i_{0}=i}$ et alors ${\displaystyle (i_{0},x)\in A}$ d'où ${\displaystyle x\in E_{i_{0}}}$, ce qui entraîne ${\displaystyle x_{0}\leq _{i_{0}}x}$ puis ${\displaystyle (i_{0},x_{0})\leq (i,x)}$.

• L'ensemble des entiers relatifs ou l'intervalle réel ]0, 1[ (munis de leurs ordres usuels respectifs) ne sont pas bien ordonnés puisqu'ils n'ont eux-mêmes pas de plus petit élément. Les intervalles réels [0, 1[ et [0, 1] ne sont pas bien ordonnés non plus puisqu'ils ont pour partie non vide ]0, 1[.
• L'ensemble des suites infinies de 0 et de 1, qui peut s'écrire ${\displaystyle \prod _{i\in \mathbb {N} }\{0,1\}}$ et être muni de l'ordre lexicographique associé (induit par 0 < 1 et l'ordre habituel sur ${\displaystyle \mathbb {N} }$, donc deux bons ordres), n'est alors pas bien ordonné, puisque ${\displaystyle \{0^{i}1^{\omega }\mid i\in \mathbb {N} \}}$ en est une partie non vide n'admettant pas de minimum (en effet, 1… > 01… > 001… > 0001… > …) ; cela constitue un contre-exemple à la propriété sur le produit cartésien mentionnée plus haut dans le cas où ${\displaystyle I}$ est infini.
• Plus simplement, l'ordre lexicographique sur l'ensemble infini des mots finis sur l'alphabet ${\displaystyle \{a,b\}}$(ou tout autre alphabet de taille au moins 2) n'est pas un bon ordre. On a par exemple comme chaine infinie décroissante: ${\displaystyle ab>aab>aaab>aaaab>aaaaab>...}$

• L'ensemble des nombres fusibles, plus petit sous-ensemble des nombres dyadiques positifs stable pour l’opération ${\displaystyle (x,y)\mapsto (x+y+1)/2}$ (avec |x-y|<1) est bien ordonné (d’ordinal ${\displaystyle \varepsilon _{0}}$), bien que cela ne soit pas démontrable à l'aide des axiomes de Peano.

Prédécesseurs et successeurs

Soit (E, ≤) un ensemble bien ordonné non vide.

• Il a un plus petit élément, mais peut (comme dans le cas E = ω, l'ensemble des entiers naturels pour l'ordre usuel) ne pas en avoir de plus grand ; mais rien n'empêche de lui en ajouter un — c'est le tout début d'une construction naïve des ordinaux transfinis.
• Soit α un élément de E : si α n'est pas le plus grand élément de E, il existe, parmi les éléments de E strictement supérieurs à α, un plus petit élément β, appelé successeur de α et noté souvent α + 1, dont α est le prédécesseur.
• Un élément de E a au plus un prédécesseur ; le plus petit élément n'en a évidemment pas et c'est le seul cas pour E = ω, mais en général, dans un ensemble bien ordonné E, beaucoup d'éléments n'ont pas de prédécesseur — c'est d'ailleurs une propriété caractéristique des ordinaux transfinis > ω. Un élément de E ayant un prédécesseur est dit de première espèce (ou successeur), et de deuxième espèce (ou limite) sinon, et s'il n'est pas le plus petit élément de E. Cette distinction est souvent utile pour raisonner par récurrence transfinie.

Segment initial

Un segment initial d'un ensemble ordonné (E, ≤) est une partie S de E telle que tout minorant d'un élément de S est dans S. L'ensemble E lui-même est un segment initial de (E, ≤), et tous les autres sont dits propres.

Pour x ∈ E, l'ensemble S_x : = {y ∈ E | y < x} est toujours un segment initial propre de E, et l'application x ↦ S_x est croissante de (E, ≤) dans (P(E), ⊂).

Si (E, ≤) est un bon ordre, tout segment initial propre S est égal à S_x, où x est le plus petit élément du complémentaire de S. L'application x ↦ S_x est alors bijective de E dans l'ensemble de ses segments initiaux propres.

Un ensemble bien ordonné n'est jamais isomorphe à l'un de ses segments initiaux propres[2].

Comparaison de bons ordres et ordinaux

Les bons ordres peuvent être comparés par morphisme ; un morphisme d'ordres est une application croissante. Un isomorphisme de bons ordres est donc une application croissante bijective, la réciproque étant alors également croissante (car un bon ordre est total). Par exemple l'application x ↦ S_x du paragraphe précédent définit un isomorphisme entre un ensemble bien ordonné et l'ensemble de ses segments initiaux propres.

Si deux bons ordres sont isomorphes, l'isomorphisme entre eux est unique[3].

Les isomorphismes d'ordres permettent de classer les bons ordres, grâce à une propriété fondamentale (démontrée par Georg Cantor) :

Théorème.— Étant donnés deux bons ordres, l'un est isomorphe à un segment initial de l'autre.

Par exemple on montre que tout ensemble infini bien ordonné a un segment initial isomorphe à ω (l'ordre usuel sur ℕ), par le théorème de définition par récurrence sur ℕ.

Le théorème se déduit facilement du théorème de définition par récurrence sur un bon ordre[4]. Plus directement[5] : soient ${\displaystyle (E,\leq )}$ et ${\displaystyle (F,\leq )}$ deux bons ordres, dans lesquels les segments initiaux propres sont notés respectivement ${\displaystyle S_{e}}$ et ${\displaystyle T_{f}}$ ; alors, l'ensemble des couples ${\displaystyle (e,f)\in E\times F}$ tels que ${\displaystyle S_{e}}$ est isomorphe à ${\displaystyle T_{f}}$ est le graphe d'un isomorphisme entre deux segments initiaux, ${\displaystyle S\subset E}$ et ${\displaystyle T\subset F}$, qui ne peuvent pas être tous deux propres.

Cette propriété exprime essentiellement qu'à isomorphisme près, la comparaison par segment initial ordonne totalement les bons ordres. On peut préciser en se restreignant à tous les bons ordres que l'on peut définir sur un ensemble donné E ; alors, l'ensemble des classes d'isomorphie (classe d'équivalence pour la relation d'isomorphisme) de ces bons ordres est totalement ordonné par la relation « être isomorphe à un segment initial », et même bien ordonné comme on le déduit de la caractérisation des segments initiaux des bons ordres (c'est une construction de l'ordinal de Hartogs associé à l'ensemble E).

On appelle ordinal un bon ordre vu à isomorphisme près. En théorie des ensembles la définition des classes d'isomorphie comme classe d'équivalences se heurte aux paradoxes usuels, ces classes ne pouvant être des ensembles. Une solution est de pouvoir définir de façon uniforme un représentant par classe : c'est la construction des ordinaux due à von Neumann (elle consiste à définir un ordinal comme l'ensemble de ses segments initiaux propres).

Cette construction se fait dans la théorie des ensembles de Zermelo-Fraenkel, elle demande impérativement le schéma d'axiomes de remplacement. La théorie des ensembles de Zermelo (sans ce schéma d'axiomes) ne permet pas de montrer l'existence de l'ordinal de von Neumann ω + ω (ni ceux au-delà), alors qu'un bon ordre de type ω + ω se définit facilement par somme dans cette théorie.

Théorème (ZF).— Tout ensemble bien ordonné est isomorphe à un et un seul ordinal de von Neumann[6].

Bon ordre fini

Dans un ensemble bien ordonné fini, toute partie non vide possède également un plus grand élément, c'est-à-dire que l'ordre opposé est également un bon ordre. Cette propriété est caractéristique des bons ordres finis. En théorie des ensembles, elle peut fournir une définition :

• des entiers naturels, qui sont alors les ordinaux finis (en ce sens) ;
• des ensembles finis, c'est-à-dire en bijection avec un entier naturel, qui sont alors les ensembles que l'on peut munir d'un bon ordre fini.

Cas des ensembles partiellement ordonnés

On peut également définir la notion de bon ordre sur des ensembles partiellement ordonnés mais, la relation d'ordre n'étant pas totale, on ne parlera pas de plus petit élément mais d'élément minimal. Un ensemble partiellement bien ordonnée est donc un ensemble ordonné dont l'ordre est bien fondé

Définition[7].— Un ensemble partiellement ordonné est partiellement bien ordonné lorsque toutes ses parties non vides possèdent au moins un élément minimal.

On trouve également cette définition équivalente:

Définition (bis)[8].— Un ensemble partiellement ordonné est partiellement bien ordonné lorsque tous ses sous-ensembles totalement ordonnés sont bien ordonnés.

Démonstration de l'équivalence

Étape 1: Si toute partie non vide possède au moins un élément minimal alors toute partie totalement ordonnée est bien ordonnée.

Soit E un ensemble partiellement ordonné et F une partie totalement ordonnée de E. Soit A une partie non vide de F, alors A possède un élément minimal. Comme A est inclus dans F totalement ordonné, cet élément minimal est un minimum de A dans F. Donc, F est bien ordonné.

Étape 2: Si toute partie totalement ordonnée est bien ordonnée alors toute partie non vide possède au moins un élément minimal.

Soit E un ensemble partiellement ordonné et A une partie non vide de E. Supposons que A ne possède pas d'élément minimal. Alors pour tout a de A il existerait a' dans A tel que a > a'. Il serait alors possible de créer dans A une suite totalement ordonnée sans élément minimal ${\displaystyle a>a_{1}>a_{2}>\cdots }$. Ce qui serait en contradiction avec le fait que toute partie totalement ordonnée de E doit être bien ordonné.

Notes et références

1. Paul Halmos, Introduction à la théorie des ensembles [détail des éditions], p. 82 de l'édition en anglais, aperçu sur Google Livres.
2. (en) Kenneth Kunen, Set Theory: An Introduction To Independence Proofs, Elsevier, 2014 (lire en ligne), p. 14-15, lemme 6.1.
3. Kunen 2014, p. 15, lemme 6.2.
4. Moschovakis 2006, p. 99, théorème 7.31.
5. Kunen 2014, p. 15, théorème 6.3.
6. Kunen 2014, p. 17, théorème 7.4.
7. Maurice Pouzet, « Sur les chaînes d’un ensemble partiellement bien ordonné », Publications du Département de Mathématiques de Lyon, vol. 16,‎ 1979, p. 21-26 (lire en ligne)
8. Georges Kurepa, « Ensembles partiellement ordonnés et ensembles partiellement bien ordonnés », Publications de l'Institut Mathématique de Serbie, n^o (S.S.) III (03),‎ 1950, p. 119-125 (ISSN 0350-1302, lire en ligne)

Voir aussi

Bibliographie

(en) Yiannis Moschovakis, Notes on Set Theory [détail des éditions]

Article connexe

Relation bien fondée