Ordre total


Ordre total

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

Sommaire

Exemples

  • Les lettres de l'alphabet données dans l'ordre standard du dictionnaire, soit abc etc ;
  • 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\vee b, a\wedge b\} = \{a, b\} pour tous a, b ;
on peut alors poser ab si et seulement si a = a\wedge b ;
on démontre qu' un ordre total est aussi un treillis distributif.

Le cas fini

  • 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

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

Voir aussi



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Ordre total de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Ordre total sur un ensemble E — ● Ordre total sur un ensemble E relation d ordre sur cet ensemble pour laquelle tous les éléments de E sont comparables …   Encyclopédie Universelle

  • Relation d'ordre total — Ordre total 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, x ≤ y ou y ≤ x ; l ensemble E …   Wikipédia en Français

  • total — total, ale, aux [ tɔtal, o ] adj. et n. • 1361; lat. médiév. totalis, du class. totus « tous » 1 ♦ (Actions) Qui affecte toutes les parties, tous les éléments (de la chose ou de la personne considérée). ⇒ 1. complet, 1. général. Destruction… …   Encyclopédie Universelle

  • Ordre lexicographique sur un ensemble ordonné E — ● Ordre lexicographique sur un ensemble ordonné E relation d ordre total définie sur l ensemble E × E telle que (x0, y0) et (x1, y1) étant deux couples de E × E, si x0 ≠ x1, les couples sont rangés dans le même ordre que x0 et …   Encyclopédie Universelle

  • Ordre (relation) — Relation d ordre Une relation d’ordre dans un ensemble E est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout… …   Wikipédia en Français

  • Ordre croissant — Relation d ordre Une relation d’ordre dans un ensemble E est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout… …   Wikipédia en Français

  • Ordre décroissant — Relation d ordre Une relation d’ordre dans un ensemble E est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout… …   Wikipédia en Français

  • Ordre partiel — Relation d ordre Une relation d’ordre dans un ensemble E est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout… …   Wikipédia en Français

  • Ordre lexicographique — Un ordre lexicographique est un ordre que l on définit sur les suites finies d éléments d un ensemble ordonné (ou, de façon équivalente, les mots construits sur un ensemble ordonné). Sa définition est une généralisation de l ordre du… …   Wikipédia en Français

  • Total — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Total », sur le Wiktionnaire (dictionnaire universel) Total est la qualité de ce qui est complet, sans …   Wikipédia en Français