Relation d'ordre - Définition

Introduction

Une relation d’ordre dans un ensemble est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout simplement un ordre.

Définitions et exemples

Relation d'ordre

Une relation d'ordre est une relation binaire réflexive, transitive et antisymétrique : soit E un ensemble et une relation binaire sur cet ensemble notée « ≤ », cette relation est une relation d'ordre si pour tous x, y et z éléments de E :

• x ≤ x (réflexivité)
• (x ≤ y et y ≤ x) ⇒ x = y (antisymétrie)
• (x ≤ y et y ≤ z) ⇒ x ≤ z (transitivité)

De par la forme même de ces axiomes, ceux-ci sont vérifiés par la relation inverse ou réciproque ≥, qui est définie par

x ≥ y si et seulement si y ≤ x.

À toute relation d'ordre est donc associée une relation d'ordre réciproque sur le même ensemble (plus petit ou égal / plus grand ou égal, inférieur ou égal / supérieur ou égal etc.). On associe également à toute relation d'ordre ≤, une relation dite d’ordre strict notée alors < (qui n'est pas à proprement parlé une relation d'ordre puisque la réflexivité n'est pas satisfaite), qui est la restriction de la relation d'ordre aux couples d'éléments distincts :

x < y si et seulement si x ≤ y et x ≠ y.

Une relation d'ordre au sens de la définition ci-dessus est parfois qualifiée d’ordre large.

Pour certaines relations d'ordre, deux éléments de E sont toujours comparables, c'est-à-dire que pour tous x, y de E :

x ≤ y ou y ≤ x.

On dit alors que la relation d'ordre est totale, et que l'ensemble E est totalement ordonné par cette relation. Une relation d'ordre sur E est dite partielle si elle n'est pas totale, et E est alors partiellement ordonné. Il est à noter qu'en anglais, on désigne par ordre partiel un ordre quelconque, qui peut donc être total. Cette terminologie est parfois également utilisée en français.

Ensemble ordonné

Un ensemble ordonné est un ensemble muni d'une relation d'ordre. Si un ensemble ordonné est fini, il peut être représenté graphiquement sous la forme d'un diagramme de Hasse, de façon similaire à la représentation habituelle d’un graphe sur papier, ce qui peut permettre de travailler plus aisément dessus. Si il est infini, on peut dessiner une partie de son diagramme de Hasse.

Exemples et contre-exemples

• La relation « est inférieur ou égal à » est une relation d'ordre total sur l'ensemble des entiers (naturels ou relatifs), sur l'ensemble des rationnels ou l'ensemble des réels.

• La relation « est strictement inférieur à », par exemple sur l'ensemble des entiers naturels, n'est pas une relation d'ordre car elle n'est pas réflexive (une relation d'ordre strict n'est jamais un ordre large).

• La relation d'inclusion, « est un sous-ensemble de » ou « est contenu dans » est une relation d'ordre partiel sur l'ensemble des parties d'un ensemble. Si l'ensemble donné est fini, son ensemble des parties est fini (plus précisément pour , on a ). La figure ci-dessous représente le diagramme de Hasse d'un ensemble à 3 éléments.

• La relation de divisibilité est une relation d'ordre partiel sur les entiers naturels, mais ce n'est pas une relation d'ordre sur les entiers relatifs car elle n'est pas antisymétrique : 1 divise -1 et -1 divise 1. La figure ci-dessous représente le diagramme de Hasse de la relation de divisibilité entre les entiers de 0 à 9.

• L'ensemble des fonctions de dans , muni de la relation d'ordre f < g si , est un ensemble ordonné infini. Intuitivement, une fonction est plus petite qu'une autre si sa courbe est toujours en dessous de l'autre courbe. On peut généraliser cet exemple aux fonctions d'un ensemble X dans un ensemble ordonné P.

• L'ensemble des partitions d'un ensemble donné est partiellement ordonné, avec la relation d'ordre donnée par le raffinement des partitions : par définition, une partition est plus fine qu'une autre si elle fractionne les parties de l'autre en de plus petites parties.

• Étant donnés deux ensembles ordonnés E et F, il y a au moins deux façons naturelles de définir un ordre sur .
  • L'ordre produit : (x, y) ≤ (x’, y’) si et seulement si x ≤ x’ et y ≤ y’.
  • L'ordre lexicographique : (x, y) ≤ (x’, y’) si et seulement si [x < x’ ou [x = x’ et y ≤ y’]].

Si les ordres initiaux sont totaux, l'ordre lexicographique est aussi total (mais pas en général l'ordre produit). Par exemple la relation ≤ définie sur l'ensemble des complexes par

  si et seulement si   ou et

est une relation d'ordre total. Elle n'est cependant pas compatible avec la structure de corps de l'ensemble des complexes.

• On peut munir R[X₁,...,X_n] l'ensemble des polynômes à n variables d'une relation d'ordre partielle. On commence par comparer les monômes à n variables via l'ordre lexicographique induit par 1 < X₁ < X₂ < ... < X_n (cet ordre lexicographique est total). On compare deux polynômes P et Q en disant que P est strictement plus petit que Q si tout monôme non nul de P est strictement plus petit que tout monôme non nul de Q. Cette relation d'ordre sur les polynômes est partielle.

• On ne peut définir de façon satisfaisante une relation d'ordre sur le cercle qui signifierait « est placé avant ». Par exemple, sur l'ensemble des points du cercle trigonométrique (de centre O), la relation entre deux points M et N définie par « la mesure principale de l'angle ([OM),[ON)) » est positive ou nulle n'est pas une relation d'ordre car elle n'est pas transitive.
• La relation « est le père de » sur un ensemble de personnes n'est pas une relation d'ordre car elle n'est pas transitive.