Ensemble bien ordonné

• 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 ω²) ;
  • 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).

• 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.

• 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.

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.

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].

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].

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.