Voir la source de Ensemble bien ordonné

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

: Toute [[Sous-ensemble|partie]] non [[Ensemble vide|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 binaire|relation]] : (Ø, Ø) (c'est le plus petit [[Nombre ordinal|ordinal]]).
* Plus généralement, tout ensemble totalement ordonné [[Ensemble fini|fini]] est bien ordonné. Un tel ensemble ordonné est caractérisé (à [[#Comparaison de bons ordres et ordinaux|isomorphisme]] [[à quelque chose près|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 <math> \leq </math> définit un [[Relation_bien_fondée|ordre bien fondé]] sur <math> (E,\leq) </math> et <math> C </math> une [[Ordre_total#Exemples|chaîne]] de <math> (E,\leq) </math>, la restriction <math> (C,\leq) </math> est un bon ordre.
* L'ensemble (ℕ, ≤) des [[entier naturel|entiers naturels]], muni de son ordre usuel, est bien ordonné ; il est souvent noté [[Omega|ω]] dans ce contexte.
* Si <math>(E_i,\le_i)_{i\in I}</math> est une [[famille d'ensembles]] bien ordonnés et si <math>I</math> est muni d'un bon ordre, alors :
** si <math>I</math> est fini, sur le [[Produit cartésien#Produit cartésien d'une famille d'ensembles|produit]] <math>\prod_{i\in I}E_i=\{(x_i)_{i\in I}\mid\forall i\in I, \ x_i\in E_i\}</math>, l'[[Relation d'ordre#Exemples et contre-exemples|ordre lexicographique]] est un bon ordre. Pour quatre exemples de produits d'un [[Couple (mathématiques)|couple]] de bons ordres, voir [[Ordre lexicographique#Ordre lexicographique sur un produit cartésien|''n''×''p'', 2×'''N''', '''N'''×2 et '''N'''×'''N''']] (isomorphes respectivement aux [[Nombre ordinal#Multiplication|ordinaux produits]] ''pn'', ω2, 2ω (= ω) et ω{{2}}) ;
** l'[[union disjointe]] <math>\bigsqcup_{i\in I} E_i = \{(i,x)\mid i\in I, \ x\in E_i\}</math> est bien ordonnée par : <math>(i,x)\le(j,y)</math> si <math>i<j</math> ou (<math>i=j</math> et <math>x\le_iy</math>). Ce bon ordre s'appelle la '''somme ordinale''' de la famille<ref name=Halmos82>{{Halmos65}}, p. 82 de l'édition en anglais, {{Google Livres|jV_aBwAAQBAJ|page=82|aperçu}}.</ref>. Remarquons que <math>\sum_{i\in I}E=I\times E</math>. La somme ordinale d'un couple <math>(A,B)</math> de bons ordres se note <math>A+B</math><ref name=Halmos82/>. Pour trois exemples, voir [[Nombre ordinal#Addition|ω + ω (= ω2) et 3 + ω, ω + 3 (⊂ ω2)]].
{{Démonstration|
* '''Produit cartésien (fini)''' : on [[Raisonnement par récurrence|raisonne par récurrence]] sur le cardinal de <math>I</math> :
** ''initialisation'' : si <math>|I| = 0</math>, c'est-à-dire <math>I = \varnothing</math>, alors <math>\prod_{i\in I}E_i</math> est réduit à un singleton (rigoureusement, celui contenant la suite vide : <math>\{()\}</math>), donc bien ordonné ;
** ''hérédité'' : on suppose la propriété génériquement vraie pour tout ensemble d'indices de cardinal {{Formule|''n''}} ; on suppose <math>|I| = n+1</math>. Soit {{Formule|''A''}} une partie non vide de <math>\prod_{i\in I}E_i</math>. {{Formule|''I''}} étant bien ordonné, il admet un plus petit élément {{Formule|''i''{{ind|0}}}} ; on pose <math>I' = I \setminus \{i_0\}</math>, puis <math>E' = \prod_{i\in I'}E_i</math> et <math>A_{i_0} = \pi_{i_0}(A)</math> (où <math>\pi_{i_0}</math> désigne la projection canonique sur la composante {{Formule|''i''{{ind|0}}}}). On définit alors {{Formule|''A''{{'}}}} par <math>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})\}</math>, ce qui est légitime puisque {{Formule|''A''{{ind|''i''{{ind|0}}}}}} est une partie non vide (par non-vacuité de {{Formule|''A''}}) de l'ensemble ordonné {{Formule|''E''{{ind|''i''{{ind|0}}}}}} et donc admet bien un minimum. {{Formule|''A''{{'}}}} est alors non vide (toujours parce que {{Formule|''A''}} ne l'est pas non plus) ; or c'est une partie de l'ensemble {{Formule|''E''{{'}}}}, qui est bien ordonné (pour l'ordre lexicographique induit) par hypothèse de récurrence puisque <math>|I'| = n</math>, et par voie de conséquence, {{Formule|''A''{{'}}}} possède un plus petit élément <math>(m_i)_{i \in I'}</math>.<br/>En notant <math>m_{i_0} = \operatorname{min}(A_{i_0})</math>, on obtient avec <math>(m_i)_{i \in I}</math> un minimum de {{Formule|''A''}} : en effet, si <math>(x_i)_{i \in I} \in A</math>, alors <math>m_{i_0} \leq x_{i_0}</math> ; il y a une alternative : soit <math>m_{i_0} < x_{i_0}</math>, et alors <math>(m_i)_{i \in I} \leq_{\mathrm{lex}_I} (x_i)_{i \in I}</math>, soit <math>m_{i_0} = x_{i_0}</math>, et on a alors <math>(x_i)_{i \in I'} \in A'</math>, d'où <math>(m_i)_{i \in I'} \leq_{\mathrm{lex}_{I'}} (x_i)_{i \in I'}</math> par minimalité de <math>(m_i)_{i \in I'}</math> dans {{Formule|''A''{{'}}}}, ce qui, d'après la [[Ordre lexicographique#Généralisation aux produits cartésiens finis|définition récursive de l'ordre lexicographique]], redonne bien <math>(m_i)_{i \in I} \leq_{\mathrm{lex}_I} (x_i)_{i \in I}</math>.

* '''Somme disjointe''' : soit {{Formule|''A''}} une partie non vide de <math>\bigsqcup_{i\in I}E_i</math>. On pose <math>I_A = \{i \in I \mid \exists x \in E_i, (i, x) \in A\}</math> ; {{Formule|''I{{ind|A}}''}} est une partie de {{Formule|''I''}} non vide puisque {{Formule|''A''}} est non vide, donc, {{Formule|''I''}} étant bien ordonné, {{Formule|''I{{ind|A}}''}} admet un minimum {{Formule|''i''{{ind|0}}}}. On définit ensuite {{Formule|''E{{'}}''}} par <math>E' = \{x \in E_{i_0} \mid (i_0, x) \in A\}</math> ; {{Formule|''E{{'}}''}} est une partie non vide de {{Formule|''E''{{ind|''i''{{ind|0}}}}}} par construction, or ce dernier est bien ordonné, donc {{Formule|''E{{'}}''}} possède un plus petit élément {{Formule|''x''{{ind|0}}}}.<br />On vérifie alors que {{Formule|(''i''{{ind|0}}, ''x''{{ind|0}})}} est le minimum de {{Formule|''A''}} pour l'ordre de la somme ordinale : si <math>(i, x) \in A</math>, alors <math>i \in I_A</math> et donc <math>i_0 \leq i</math> ; si <math>i_0 < i</math>, on a bien <math>(i_0, x_0) \leq (i, x)</math>, sinon, <math>i_0 = i</math> et alors <math>(i_0, x) \in A</math> d'où <math>x \in E_{i_0}</math>, ce qui entraîne <math>x_0 \leq_{i_0} x</math> puis <math>(i_0, x_0) \leq (i, x)</math>.
}}

* L'ensemble des [[entier relatif|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 <math>\prod_{i\in \mathbb N}\{0, 1\}</math> et être muni de l'ordre lexicographique associé (induit par 0 < 1 et l'ordre habituel sur <math>\mathbb N</math>, donc deux bons ordres), n'est alors pas bien ordonné, puisque <math>\{0^i 1^\omega \mid i \in \mathbb N\}</math> 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ù <math>I</math> est infini.
* Plus simplement, l'[[Relation d'ordre#Exemples et contre-exemples|ordre lexicographique]] sur l'ensemble infini des mots finis sur l'alphabet <math>\{a,b\}</math>(ou tout autre alphabet de taille au moins 2) [[Relation bien fondée#Chaînes de caractères|n'est pas un bon ordre]]. On a par exemple comme chaine infinie décroissante:  <math>ab > aab > aaab > aaaab > aaaaab > ... </math>

* L'ensemble des [[Nombre fusible|nombres fusibles]], plus petit sous-ensemble des [[Nombre dyadique|nombres dyadiques]] positifs stable pour l’opération <math>(x,y)\mapsto (x+y+1)/2</math> (avec |x-y|<1) est bien ordonné (d’ordinal <math>\varepsilon_0</math>), 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 [[Nombre transfini|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 {{nobr|α + 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 [[Section commençante|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<sub>x</sub>'' : = {''y'' ∈ ''E'' | ''y'' < ''x''} est toujours un segment initial propre de ''E'', et l'application ''x'' ↦ ''S<sub>x</sub>'' est croissante de (''E'', ≤) dans ([[Ensemble des parties d'un ensemble|''P''(''E'')]], ⊂).

Si (''E'', ≤) est un bon ordre, tout segment initial propre ''S'' est égal à ''S<sub>x</sub>'', où ''x'' est le plus petit élément du [[Complémentaire (théorie des ensembles)|complémentaire]] de ''S''. L'application ''x'' ↦ ''S<sub>x</sub>'' 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<ref>{{Ouvrage|lang=en|auteur=[[Kenneth Kunen]]|titre=Set Theory: An Introduction To Independence Proofs|éditeur=Elsevier|année=2014|url={{Google Livres|wWniBQAAQBAJ|page=14}}|page=14-15}}, lemme 6.1.</ref>.

== Comparaison de bons ordres et ordinaux ==
Les bons ordres peuvent être comparés par morphisme ; un [[Morphisme#Cas des ensembles ordonnés|morphisme d'ordres]] est une application croissante. Un [[Isomorphisme d'ordres|isomorphisme]] de bons ordres est donc une application croissante bijective, [[Ordre total#En théorie des catégories|la réciproque étant alors également croissante]] (car un bon ordre est total). Par exemple l'application ''x'' ↦ ''S<sub>x</sub>'' 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<ref>{{Harvsp|Kunen|2014|p=15}}, lemme 6.2.</ref>.

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 [[Récurrence transfinie#Définition par récurrence sur un ordinal|théorème de définition par récurrence sur un bon ordre]]<ref>{{harvsp|Moschovakis-notes|texte=Moschovakis 2006|p=99}}, théorème 7.31.</ref>. Plus directement<ref>{{Harvsp|Kunen|2014|p=15}}, théorème 6.3.</ref> : soient <math>(E,\le)</math> et <math>(F,\le)</math> deux bons ordres, dans lesquels les segments initiaux propres sont notés respectivement <math>S_e</math> et <math>T_f</math> ; alors, l'ensemble des couples <math>(e,f)\in E\times F</math> tels que <math>S_e</math> est isomorphe à <math>T_f</math> est le graphe d'un isomorphisme entre deux segments initiaux, <math>S\subset E</math> et <math>T\subset F</math>, 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 ''[[nombre ordinal|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 [[nombre ordinal|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 [[Nombre ordinal#Addition|ω + ω]] (ni ceux au-delà), alors qu'un bon ordre de [[type d'ordre|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 [[nombre ordinal|ordinal de von Neumann]]<ref>{{Harvsp|Kunen|2014|p=17}}, théorème 7.4.</ref>.

== Bon ordre fini ==
{{article détaillé|Ensemble fini#Les entiers et les bons ordres}}
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 [[Nombre ordinal#Propriétés|ordinaux finis]] (en ce sens) ;
* des ensembles finis, c'est-à-dire [[équipotence|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 [[Ensemble partiellement ordonné|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 maximal|élément minimal]]. Un ensemble partiellement bien ordonnée est donc un ensemble ordonné dont l'ordre est [[relation bien fondée|bien fondé]]

'''Définition'''<ref>{{Article|auteur1=Maurice Pouzet|titre=Sur les chaînes d’un ensemble partiellement bien ordonné|périodique=Publications du Département de Mathématiques de Lyon|volume=16|pages=21-26|date=1979|lire en ligne=http://www.numdam.org/item/PDML_1979__16_1_21_0.pdf}}</ref>'''.—''' 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)'''<ref>{{Article|auteur1=Georges Kurepa|titre=Ensembles partiellement ordonnés et ensembles partiellement bien ordonnés|périodique=Publications de l'Institut Mathématique de Serbie|numéro=(S.S.) III (03)|pages=119-125|date=1950|issn=0350-1302|lire en ligne=http://elib.mi.sanu.ac.rs/pages/browse_issue.php?db=publ&rbr=9}}</ref>'''.—''' Un ensemble partiellement ordonné est partiellement bien ordonné lorsque tous ses sous-ensembles totalement ordonnés sont bien ordonnés.
{{démonstration|titre=Démonstration de l'équivalence|contenu=
<!--- En attendant une source universitaire -->
'''É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 <math> a > a_1 > a_2 > \cdots </math>. 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 ==
{{Références}}

== Voir aussi ==
=== Bibliographie ===
{{Moschovakis-notes}}

=== Article connexe ===
[[Relation bien fondée]]

{{Portail|mathématiques}}

[[Catégorie:Théorie des ordres]]
[[Catégorie:Nombre ordinal]]