Ordre total
# 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 ».

