Ordre total
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
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) :
- x ≤ x (réflexivité) ;
- si x ≤ y et y ≤ x, alors x = y (antisymétrie) ;
- si x ≤ y et y ≤ z, alors x ≤ z (transitivité) ;
- x ≤ y ou y ≤ x (totalité).
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.
Exemples
[modifier | modifier le code]- 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 : x ≤ y si et seulement si y – x est un carré.
- Soient f : X → Y une injection, ≤ un ordre sur Y, et ≼ l'ordre induit sur X en posant : x1 ≼ x2 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 {a∨b, a∧b} = {a, b} pour tous a, b ; on peut alors poser a ≤ b si et seulement si a = a∧b ; 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]- Sur l'ensemble des entiers naturels, la relation d'ordre « est un diviseur de » n'est pas un ordre total, car on peut trouver des paires d'entiers positifs dont aucun n'est diviseur de l'autre.
- De même, sur l'ensemble des parties d'un ensemble qui contient au moins deux éléments a et b (distincts), l'inclusion n'est qu'un ordre partiel : on n'a ni {a} ⊂ {b}, ni {b} ⊂ {a}.
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, 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 ⇔ (x ≤ y et x ≠ y)
ou encore :
- x ≤ y ⇔ (x < y ou x = y).
Un ordre ≤ est total si et seulement si son ordre strict associé < vérifie :
- ∀ x, y ∈ E (x < y ou x = y ou y < x).
On appelle ordre strict total tout ordre strict vérifiant cette propriété, dite « de trichotomie ».
