Relation d’ordre

Une relation d’ordre est une relation binaire sur un ensemble qui est réflexive, antisymétrique et transitive.

Motivation

L’ordre est une notion courante, avec laquelle nous travaillons aussi dans la vie de tous les jours. On peut ordonner beaucoup de choses de diverses façons : les mots par ordre alphabétique, les élèves d’une classe par taille, les produits par prix. Tout cela est décrit par la relation d’ordre, que l’on note habituellement avec le symbole ≤. Les symboles associés sont : <, >, ≥. Leur sens est évident.

Qu’attendrait-on d’une telle relation ? Dès le symbole, il est clair que, dans une relation d’ordre, il y aura des éléments identiques : il s’agit donc de définir les propriétés de la relation « inférieur ou égal à ». Une telle relation devrait être réflexive. On doit avoir a ≤ a.

Et ensuite ? La symétrie ne sera sûrement pas vraie : si l’on ordonne selon le prix, et que la voiture est moins chère que le pain, alors le pain ne sera sûrement pas moins cher que la voiture. Qu’attendrait-on en général s’il arrivait que a ≤ b et en même temps b ≤ a ? Cela aurait-il un sens ? Oui, si l’on avait a = b. Le seul cas où l’ordre des éléments placés dans la relation n’a pas d’importance, c’est quand ces éléments sont identiques : la relation d’ordre est donc antisymétrique.

Enfin, si l’on sait que la voiture est plus chère que le pain et que l’avion est encore plus cher que la voiture, on s’attend à ce que l’avion soit sûrement plus cher que le pain. C’est ce que décrit la transitivité.

Ordre partiel

Ce que nous venons de définir n’est en réalité qu’un ordre partiel, il n’est pas total. Pourquoi n’est-il pas total ? Essayons de définir un ordre sur des ensembles. Comment pourrait-on comparer deux ensembles ?

Disons que l’ensemble A est inférieur ou égal à l’ensemble B si A ⊂ B, c’est-à-dire si A est une partie de B. Cela a du sens : si l’on a A = {1 ; 2} et B = {1 ; 2 ; 3}, on peut dire que A est plus petit, car B contient les mêmes éléments que A et, en plus, le nombre trois. On aura donc par exemple :

• {a ; c} ≤ {a ; b ; c ; d}
• ∅ ≤ {5 ; n ; x}
• {x ; e ; s} ≤ {x ; e ; s}

La difficulté apparaît quand on veut comparer les ensembles A = {a ; b} et B = {a ; c}. Lequel est le plus petit ou le plus grand ? Le problème est que, certes, les deux ensembles contiennent l’élément a, mais leur second élément est chaque fois différent. Aucun des ensembles n’est une partie de l’autre, donc on n’a ni A ≤ B ni B ≤ A. De tels ensembles sont non comparables pour notre ordre.

C’est pourquoi on définit un ensemble totalement ordonné, ou encore chaîne, comme un ensemble dont deux éléments quelconques sont comparables. Les ensembles de nombres munis de l’ordre usuel en sont des exemples. Pour deux nombres réels quelconques a, b, tu sais décider si a ≤ b ou b ≤ a.

Exemples de la vie courante

Un exemple où il vaut mieux ne pas comparer serait l’ordre selon la beauté : la relation < signifierait alors « être moins beau ». Peut-être devrions-nous plutôt la définir à l’envers, > comme « être plus beau », pour être plus corrects :-). Comparer deux filles a sans doute du sens, par exemple « Emma » < « Léa » au sens où Léa est plus belle qu’Emma. Ou deux garçons : « Hugo » < « Lucas » au sens où Lucas est plus beau que Hugo.

Le problème, c’est qu’on peut difficilement comparer la beauté d’un garçon et celle d’une fille. Qui est le plus beau, Léa ou Lucas ? Qui est le moins beau, Emma ou Hugo ? Mieux vaut ne pas chercher…

Si, dans le dernier exemple, nous nous limitons par exemple aux filles, nous pouvons dire que nous avons un ensemble totalement ordonné, car nous savons comparer la beauté de toutes les filles.

Élément minimal et maximal, plus petit et plus grand élément

Si l’on a un ensemble ordonné M, on dit qu’un élément min ∈ M est minimal s’il n’existe aucun x ∈ M tel que x < min. Autrement dit, nous ne sommes pas capables de trouver un élément qui soit plus petit que l’élément min.

On dit qu’un élément max ∈ M est maximal s’il n’existe aucun x ∈ M tel que x > max. Autrement dit, nous ne sommes pas capables de trouver un élément qui soit plus grand.

Ces deux notions diffèrent de celles de plus petit et de plus grand élément.

On dit qu’un élément a ∈ M est le plus petit si, pour tout x ∈ M, on a a ≤ x. Le plus petit élément a est donc inférieur ou égal à tous les autres éléments de l’ensemble M.

On dit qu’un élément b ∈ M est le plus grand si, pour tout x ∈ M, on a b ≥ x. Le plus grand élément b est supérieur ou égal à tous les autres éléments de l’ensemble M.

Quelle est la différence entre le plus grand élément et un élément maximal ? Il peut y avoir plusieurs éléments maximaux, car l’ensemble n’est pas forcément totalement ordonné. Revenons à l’exemple de la comparaison des personnes selon leur beauté : on peut dire que Léa est la plus belle fille et que Lucas est le plus beau garçon. Mais ces deux personnes, nous ne sommes plus capables de les comparer entre elles : nous ne savons pas qui, de Léa ou de Lucas, est le plus beau.

Les deux éléments sont donc maximaux. Nous ne sommes pas capables de trouver une personne plus belle que Lucas : Lucas est plus beau que tous les autres garçons, et nous ne pouvons pas le comparer aux filles. De même pour Léa : elle est plus belle que toutes les filles, et nous ne pouvons pas la comparer aux garçons.

Mais aucun des deux n’est le plus grand, c’est-à-dire dans ce sens le plus beau. Car pour que Lucas soit le plus beau/le plus grand, il devrait être plus beau que toutes les personnes, y compris toutes les filles. Or nous avons déjà dit que nous ne pouvons pas le comparer aux filles, il ne peut donc pas être la plus belle personne, il est seulement, dans la terminologie de la théorie de l’ordre, maximal.

On voit sans doute facilement que, si un ensemble a un plus grand élément, cet élément est aussi maximal. Si l’élément a est plus grand que tous les autres éléments de l’ensemble (définition du plus grand élément), on ne trouvera sûrement pas d’élément encore plus grand (définition de l’élément maximal).

Un exemple d’ensemble qui a un plus grand et un plus petit élément est l’intervalle fermé [0 ; 1]. Si l’on choisissait le même intervalle, mais ouvert, il n’aurait ni plus grand ni plus petit élément : ]0 ; 1[.

Si nous voulions une infinité d’éléments minimaux, nous pourrions définir l’ordre R ainsi. Définissons d’abord des ensembles auxiliaires M_x. Les ensembles auront cette forme : pour tout x de l’intervalle ]0 ; 1[, nous définissons l’ensemble M_x = {y ∣ y = x + n}, où n est un entier naturel. Nous obtenons par exemple des ensembles comme ceux-ci :

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Sur chaque ensemble M_x, nous définissons l’ordre usuel, que nous notons R_x. À la fin, il ne reste qu’à faire la réunion de ces ordres : R = ∪ R_x. Dans cet ordre, on ne peut donc comparer qu’à l’intérieur des chaînes d’origine. Nous pouvons savoir si 0,5 ≤ 2,5, mais nous ne pouvons pas savoir si 0,5 ≤ 2,7, car ces nombres ne se trouvaient pas dans le même ensemble M_x et leur relation n’est donc pas définie.

Dans cette relation d’ordre, chaque élément de l’intervalle ]0 ; 1[ est alors un élément minimal.

Diagrammes de Hasse

On peut représenter les ensembles ordonnés par un diagramme de Hasse. C’est un graphe dans lequel les sommets représentent les éléments de l’ensemble, et une arête entre les sommets (a ; b) nous dit que a < b et qu’il n’existe pas de c tel que a < c < b. Donc, entre les éléments a et b, il n’y a aucun autre élément. De plus, dans le graphe, le sommet a doit être plus bas que le sommet b. Exemple de diagramme de Hasse :

Ce diagramme de Hasse représente l’ensemble ordonné {A ; B ; C ; D ; E ; F}. On a ici : A < B, B < E, et bien sûr aussi A < E, mais il n’y a pas d’arête entre ces sommets, car il existe le sommet B tel que A < B < E. Les éléments E et D sont non comparables, car aucun n’est au-dessus ou en dessous de l’autre.

Bien que l’on dessine habituellement les diagrammes de Hasse avec cet alignement soigné, ce n’est pas absolument obligatoire. Le diagramme de Hasse précédent peut aussi ressembler à ceci :

Un autre exemple est l’ensemble A = {1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 10 ; 12 ; 15 ; 20 ; 30 ; 60}. Ce sont les diviseurs positifs du nombre 60. L’ordre de divisibilité peut être représenté ainsi :

L’ordre de divisibilité signifie que (a ; b) ∈ R si et seulement si a divise b. Sur le diagramme, on remarque qu’au-dessus de chaque nombre se trouvent les nombres qu’il divise. Par exemple, au-dessus du nombre 6 se trouvent les nombres 12, 30 et 60. Au-dessus du nombre 4 se trouvent les nombres 12, 20 et 60. Etc. En revanche, le nombre 3 n’a pas au-dessus de lui le nombre 10, car il ne le divise pas — attention, le nombre 10 est visuellement au-dessus du nombre 3, mais aucune ligne ne mène « de bas en haut » jusqu’à lui. Si, à partir du nombre 3, nous nous déplaçons uniquement vers le haut, nous pouvons aller vers les nombres 15 et 6, puis de là vers le nombre 30. Nous n’atteindrions le nombre 10 qu’en redescendant, ce qui est interdit.