title: Ordre total
text: # Ordre total
  
  En mathématiques, on appelle relation d'ordre total sur un ensemble E toute relation d'ordre ≤ pour laquelle deux éléments de E sont toujours comparables, c'est-à-dire que
  
  $\forall x,y\in E\quad x\leq y{\text{ ou }}y\leq x$
  
  On dit alors que E est totalement ordonné par ≤.
  
  ## Définition
  
  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
  
  * 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 : $x_1$ ≼ $x_2$ si et seulement si $f(x_1)$ ≤ $f(x_2).$ 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
  
  * 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
  
  * 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, 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
  
  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 ».
  
  