Ensemble bien ordonné

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

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 xy ou yx.

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, à dire qu'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[modifier | modifier le code]

  • L'ensemble vide, muni du seul ordre qui y soit possible : (Ø, Ø) (c'est le plus petit ordinal).
  • Plus généralement tout ensemble totalement ordonné fini est bien ordonné, un tel ensemble est caractérisé par son nombre d'éléments
  • L'ensemble (ℕ, ≤) des entiers naturels, muni de son ordre usuel est bien ordonné, il est souvent noté ω dans ce contexte.
  • Toute partie d'un ensemble bien ordonné est elle-même bien ordonnée (pour l'ordre induit).
  • L'ensemble des entiers relatifs, ou l'intervalle réel ]0,1[ (munis de leurs ordres usuels) 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[.

Prédécesseurs et successeurs[modifier | modifier le code]

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.

Opérations sur les bons ordres[modifier | modifier le code]

Somme[modifier | modifier le code]

Produit[modifier | modifier le code]

Exponentielle[modifier | modifier le code]

Segment initial[modifier | modifier le code]

Un segment initial d'un ensemble ordonné (E, ≤) est une partie S de E telle que tout élément de E inférieur à un élément de S soit dans S. De façon évident, E est un segment initial de (E, ≤), et on appelle segment initial propre d'un ensemble ordonné, un segment initial qui n'est pas l'ensemble lui-même.

Pour xE, l'ensemble Sx des éléments de E inférieurs strictement à x est toujours un segment initial propre de E. Dans le cas des bons ordres les segments initiaux propres de (E,≤) sont exactement ces ensembles : il suffit de prendre pour S un segment initial propre donné, le plus petit élément x de l'ensemble (non vide) des éléments de E qui ne sont pas dans S.

Proposition.— Les segments initiaux propres d'un ensemble bien ordonné (E,≤) sont les Sx, xE, où Sx = {yE | y < x}.

L'application xSx est donc bijective de E dans l'ensemble de ses segments initiaux propres, si ce dernier est muni de la relation d'inclusion, c'est une application bijective croissante.

Comparaison de bons ordres et ordinaux[modifier | modifier le code]

Les bons ordres peuvent être comparés par morphisme, un morphisme d'ordre 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 xSx du paragraphe précédent définit un isomorphisme entre un ensemble bien ordonné et l'ensemble de ses segments initiaux propres.

Les isomorphismes d'ordre permettent de classer les bons ordres, deux bons ordres isomorphes étant « essentiellement identiques », grâce à une propriété fondamentale sur les bons ordres (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.

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). Un ensemble bien ordonné n'est jamais isomorphe à un de ses segments initiaux propres.

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.

Bon ordre fini[modifier | modifier le code]

Dans un ensemble bien ordonné fini toute partie non vide possède également un plus grand élément, c'est-à-dire que l'ordre inverse 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) et des ensembles finis, en bijection avec un entier naturel, qui sont alors les ensembles que l'on peut munir d'un bon ordre fini.

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Relation bien fondée