Ordre total

Posez devant vous quatre cartes portant les nombres 2, 5, 9 et 12. Prenez n'importe lesquelles, par exemple 5 et 9 : l'une vient toujours avant l'autre dans l'ordre croissant. Cette possibilité de trancher pour chaque paire est l'idée centrale d'un ordre total.

Les éléments n'ont pas besoin d'être des nombres. Il suffit de disposer d'une relation cohérente qui permette toujours de déclarer le premier inférieur ou égal au second, ou l'inverse.

Un ordre total est une relation d'ordre définie sur un ensemble. Elle est d'abord réflexive : tout élément est inférieur ou égal à lui-même. Elle est antisymétrique : si chacun de deux éléments est inférieur ou égal à l'autre, alors ces éléments sont égaux. Elle est enfin transitive : si un premier élément précède un deuxième, qui précède un troisième, alors le premier précède le troisième.

À ces trois conditions d'un ordre partiel s'ajoute la comparabilité de toute paire. Si l'ensemble est noté E et si ses éléments sont notés x et y, cette condition s'écrit $\mathrm{\forall }x,y\in E,x\le y\text{ ou }y\le x\backslash forall\; x,y\backslash in\; E,\backslash quad\; x\backslash le\; y\backslash \; \backslash text\{\; ou\; \}\backslash \; y\backslash le\; x$. L'ordre est dit total parce qu'aucune paire ne reste incomparable.

L'ordre naturel rend les entiers, les rationnels et les réels totalement ordonnés. « Ordre linéaire » est un autre nom courant. La source emploie aussi « ordre complet » ; ce terme pouvant porter un autre sens selon le contexte, il faut alors vérifier la définition retenue.

Considérons l'ensemble E formé de quatre nombres, muni de l'ordre usuel « inférieur ou égal ».
Données : E = {2, 5, 9, 12} ; les éléments sont des entiers ; la relation utilisée est ≤. Il faut vérifier que toute paire d'éléments de E est comparable.

Étape 1. Rangeons les éléments : 2 ≤ 5 ≤ 9 ≤ 12. La transitivité donne aussi les comparaisons non voisines, comme 2 ≤ 9 et 5 ≤ 12.

Étape 2. Prenons la paire {5, 9}. On obtient 5 ≤ 9 ; il n'est donc pas nécessaire que 9 ≤ 5 soit également vraie.

Étape 3. Le même rangement tranche toutes les autres paires distinctes. Pour une paire répétée, telle que {9, 9}, la réflexivité donne 9 ≤ 9.

Ainsi, l'ordre usuel est total sur E. Le contrôle est refaisable : choisissez deux cartes quelconques ; la carte placée le plus à gauche porte toujours un nombre inférieur ou égal à l'autre.

Pour classer les quatre cartes 2, 5, 9 et 12, l'ordre total permet de décider laquelle placer avant l'autre à chaque comparaison. Si certaines paires ne pouvaient pas être départagées, un ordre partiel décrirait mieux la situation.

Dans une recherche parmi des valeurs déjà triées, la comparaison indique de quel côté poursuivre. Ce geste suppose un ordre total : si deux valeurs peuvent être incomparables, une structure qui conserve plusieurs branches est préférable.

Pour vérifier qu'une règle produit un classement sans ex æquo inexpliqué, on teste des paires. Un seul couple incomparable suffit à écarter l'ordre total, même si la plupart des éléments se comparent sans difficulté.

Ordre partiel. Il satisfait les trois propriétés d'une relation d'ordre, mais il peut laisser des éléments incomparables. Dans l'ensemble des parties de {2, 5}, ordonné par inclusion, {2} et {5} ne sont inclus ni l'un dans l'autre : cet ordre n'est pas total.

Ordre strict. La relation < est irréflexive : 5 < 5 est faux. La relation ≤ est réflexive : 5 ≤ 5 est vrai. Un ordre total peut être présenté sous sa forme stricte ou large, à condition de ne pas mélanger leurs propriétés.

Bon ordre. Il exige que toute partie non vide possède un plus petit élément. L'ordre usuel des entiers est total, mais l'ensemble de tous les entiers n'a pas de plus petit élément : total ne signifie donc pas bien ordonné.

Égalité dans une paire. La comparabilité ne demande pas qu'une inégalité stricte soit toujours vraie. Lorsque x et y désignent le même élément, x ≤ y et y ≤ x sont toutes deux vraies ; l'antisymétrie confirme alors x = y.

Pas nécessairement d'extrémités. Pouvoir comparer toute paire ne garantit ni plus petit ni plus grand élément. Les entiers sont totalement ordonnés par l'ordre usuel, mais tout entier possède un prédécesseur et un successeur. Il faut donc vérifier séparément l'existence d'une extrémité.

Vocabulaire à contrôler. « Ordre linéaire » désigne bien ici un ordre total. En revanche, « ordre complet » peut être compris autrement dans certains contextes ; le symptôme est une définition parlant de bornes plutôt que de comparabilité. Il faut alors revenir aux propriétés énoncées.

La fiche relation d'ordre détaille les trois propriétés sur lesquelles la comparabilité totale vient se greffer.

La fiche Ordre partiel montre ce qui subsiste lorsque certaines paires ne sont pas comparables.

La fiche Bon ordre ajoute une exigence portant sur le plus petit élément de chaque partie non vide.

La fiche Borne supérieure aide à distinguer comparabilité des éléments et existence de certaines bornes.