Aller au contenu

Ordre total

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, on appelle relation d'ordre total ou d'ordre linéaire sur un ensemble E toute relation d'ordre ≤ pour laquelle deux éléments de E sont toujours comparables, c'est-à-dire que

.

On dit alors que E est totalement ordonné par ≤.

Définition

[modifier | modifier le code]

Une relation binaire ≤ sur un ensemble E est un ordre total si (pour tous éléments x, y et z de E) :

Les trois premières propriétés sont celles faisant de ≤ une relation d'ordre. La quatrième fait de cet ordre un ordre total.

  • L'ensemble des lettres d'un alphabet est totalement ordonné par un ordre alphabétique.
  • Tout corps euclidien, comme le corps ℝ des réels, est muni d'un ordre total naturel : xy si et seulement si y – x est un carré.
  • Soient f : XY une injection, ≤ un ordre sur Y, et ≼ l'ordre induit sur X en posant : x1x2 si et seulement si f(x1) ≤ f(x2). Si ≤ est total alors ≼ aussi. En particulier : toute restriction à une partie X de Y d'un ordre total sur Y est un ordre total sur X. Par exemple, toute partie de ℝ est totalement ordonnée par la relation d'ordre usuelle.
  • Si un ordre ≤ sur E est total, alors l'ordre opposé ≥ sur E est total (la réciproque en résulte).
  • 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.
  • Une chaîne d'un ensemble partiellement ordonné (E, ≤) est une partie de E sur laquelle l'ordre ≤ est total. 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 {ab, ab} = {a, b} pour tous a, b ; on peut alors poser ab si et seulement si a = ab ; on démontre qu'un ordre total est aussi un treillis distributif.
  • D'après le théorème d'extension de Szpilrajn, tout ordre partiel ≤ sur un ensemble E est prolongeable en un ordre total sur E, appelé une extension linéaire de ≤.

Contre-exemples

[modifier | modifier le code]

Le cas fini

[modifier | modifier le code]

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, dont les morphismes sont les applications croissantes.

Toute bijection croissante d'un ordre total dans ordre quelconque est un isomorphisme d'ordres.

Ordre strict total

[modifier | modifier le code]

La bijection canonique entre les ordres stricts et les ordres sur un même ensemble E associe une relation d'ordre strict < (antiréflexive et transitive donc antisymétrique) à une relation d'ordre ≤ (réflexive, transitive et antisymétrique), par :

x < y ⇔ (xy et xy)

ou encore :

xy ⇔ (x < y ou x = y).

Un ordre ≤ est total si et seulement si son ordre strict associé < vérifie :

x, yE (x < y ou x = y ou y < x).

On appelle ordre strict total tout ordre strict vérifiant cette propriété, dite « de trichotomie ».

Référence

[modifier | modifier le code]
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Total order » (voir la liste des auteurs).