Ordre total

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

On appelle relation d'ordre total sur un ensemble E toute relation d'ordre ≤ telle que tout élément de E soit comparable avec tout autre élément de E, c'est-à-dire que pour tout x et y éléments de E, xy ou yx ; l'ensemble E est dit alors totalement ordonné.

Exemples[modifier | modifier le code]

  • L'ensemble des lettres de l'alphabet ordonnées par l'ordre standard du dictionnaire (soit abc etc) est totalement ordonné;
  • L'ensemble des entiers positifs ordonnés par la relation ≤ est totalement ordonné, car tout nombre positif peut être comparé avec tous les autres, mais si on remplace la relation ≤ par la relation "est un diviseur de", celle-ci est toujours une relation d'ordre, mais elle n'est pas un ordre total, car on peut trouver des paires de nombre qui ne sont pas diviseurs l'un de l'autre.
  • toute partie E d'un ensemble totalement ordonné F, munie de la restriction à E de l'ordre défini sur F ;
  • s'il y a une injection f de X vers un ensemble totalement ordonné Y alors f induit un ordre total sur X en posant x1 < x2 si et seulement si f(x1) < f(x2) ;
  • l'ordre lexicographique sur le produit cartésien d'un ensemble bien ordonné d'ensembles totalement ordonnés, est lui-même un ordre total ; par exemple, tout ensemble de mots est totalement ordonné par l'ordre alphabétique, et tout bon ordre est un ordre total.
  • l'ensemble des nombres réels est totalement ordonné par la relation usuelle, donc aussi le sous-ensemble formé par les nombres rationnels, et celui formé par les nombres entiers naturels ;
  • une chaîne est un ensemble totalement ordonné inclus dans un ensemble partiellement ordonné ; cette notion joue un rôle important en théorie des ensembles par le lemme de Zorn ;
  • on peut définir un ensemble totalement ordonné comme un treillis dans lequel {a∨b, a∧b} = {a, b} pour tous a, b ; on peut alors poser ab si et seulement si a = a∧b ; on démontre qu'un ordre total est aussi un treillis distributif.

Le cas fini[modifier | modifier le code]

  • Dans un ensemble fini totalement ordonné, toute partie non vide a un plus petit élément. Autrement dit : sur un ensemble fini, tout ordre total est un bon ordre.
  • Tout ensemble fini totalement ordonné est isomorphe pour l'ordre à un segment initial de N.

En théorie des catégories[modifier | modifier le code]

Les ensembles totalement ordonnés forment une sous-catégorie de la catégorie des ordres, les morphismes étant les applications qui conservent l'ordre. Une bijection entre deux ensembles totalement ordonnés qui conserve l'ordre est un isomorphisme dans cette catégorie.

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]