Relation d'ordre

Un article de Wikipédia, l'encyclopédie libre.

Une relation d’ordre dans un ensemble $E$ 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.

[modifier] Définitions et exemples

[modifier] Relation d'ordre

Une relation d'ordre sur un ensemble E est une relation binaire sur E réflexive, transitive et antisymétrique

réflexive, si elle met tout élément en relation avec lui-même, c’est-à-dire si :

$\forall x \in E , \quad \ x \mathcal{R} x \,$

antisymétrique, si les éléments distincts ne sont jamais en relation mutuelle, c’est-à-dire si :

$\forall (x,y) \in E^2 , \quad \ x \mathcal{R} y \;\wedge\; y \mathcal{R} x \Longrightarrow x = y \,$

transitive, si deux éléments sont mis en relation dès qu'on peut transiter par un troisième, c'est-à-dire

$\forall (x,y,z) \in E^3 , \quad \ x \mathcal{R} y \;\wedge\; y \mathcal{R} z \Longrightarrow x \mathcal{R} z \,$

On peut tout de suite remarquer que, de par la forme même de ces axiomes, ils sont vérifiés par la relation inverse ou réciproque $\mathcal{R}^{-1}$ , qui est définie par

$x \mathcal{R}^{-1} y \iff y \mathcal{R} x$

À toute relation d'ordre est donc associé un ordre réciproque (plus petit ou égal/plus grand ou égal, inférieur ou égal / supérieur ou égal etc.).

[modifier] Exemples et contre-exemples

La relation « est inférieur ou égal à » est une relation d'ordre sur l'ensemble des entiers (naturels ou relatifs), sur l'ensemble des rationnels ou l'ensemble des réels. Elle peut être définie explicitement par

$\forall (x,y) \in E^2, \quad x \le y \iff y - x \in E_+$

où

$E_+=\{x\in E | x\geq 0\}$

la relation « est strictement inférieur à » n'est pas une relation d'ordre car elle n'est pas réflexive.
La relation « est multiple de » est une relation d'ordre sur l'ensemble des entiers naturels.
La relation « divise » est une relation d'ordre sur les entiers naturels.
La relation « est multiple de » n'est pas un relation d'ordre sur les entiers relatifs car elle n'est pas antisymétrique : 6 est multiple de -6 et -6 est multiple de 6 mais 6 n'est pas égal à -6.
La relation « est un sous-ensemble de » ou « est contenu dans » est une relation d'ordre sur l'ensemble des parties d'un ensemble.
La relation « est placé avant » définie sur l'ensemble des points du cercle trigonométrique par

M est avant N si et seulement si la mesure principale de l'angle $(\overrightarrow{OM}; \overrightarrow{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 réflexive.
La relation définie sur l'ensemble des complexes par

$\forall (x,y) \in \mathbb C^2 , \quad x \le y \iff y - x \in \R_+$

est une relation d'ordre.

La relation $\mathcal R$ définie sur l'ensemble des complexes par

$\forall (x,y) \in \mathbb C^2 , \quad x \mathcal R y \iff \mathrm{Re}(x) < \mathrm{Re}(y) \;\vee\; (\mathrm{Re}(x)=\mathrm{Re}(y) \;\wedge\; \mathrm{Im}(x)\le \mathrm{Im}(y))$

est une relation d'ordre. Elle n'est cependant pas compatible avec la structure de corps de $\mathbb C$ .

[modifier] Applications croissantes

Si $(E,\mathcal{R})$ et $(F,\mathcal{S})$ sont deux ensembles ordonnés, une application $f:E \to F$ est dites croissante si elle est compatible avec les relations, i.e. si :

$\forall (x,y) \in E^2 , \quad x\mathcal{R}y \Longrightarrow f(x)\mathcal{S}f(y)$ .

[modifier] Relation d'ordre strict

À une relation d'ordre on associe naturellement la relation obtenue en restreignant celles-ci aux couples d'éléments distincts. On parle alors d’ordre strict. Si la relation d'ordre est notée $\le$ , on définit donc la relation d'ordre strict associée, notée $<$ par :

$x < y \iff x \le y \;\wedge\; x \ne y$ .

On peut alors préciser relation d'ordre large quand on veut distinguer la notion de relation d'ordre de celle d'ordre strict.

Il est tout à fait possible d'axiomatiser directement la notion d'ordre strict. Cela peut même s'avérer plus naturel dans certains cas.

Une relation d'ordre strict est une relation binaire irréflexive, et transitive. C’est-à-dire qu'une relation $R$ définie sur un ensemble $E$ est un ordre strict quand elle vérifie les deux propriétés suivantes :

(Irreflexivité) aucun élement de $E$ n'est en relation avec lui-même par $R$ :

$\forall x \in E , \quad x \not\! R x$ ;

(transitivité) deux éléments sont mis en relation dès qu'on peut transiter par un troisième, c'est-à-dire :

$\forall (x,y,z) \in E^3 , \quad \ x \mathcal{R} y \;\wedge\; y \mathcal{R} z \Longrightarrow x \mathcal{R} z \,$

On déduit immédiatement de ces deux propriétés qu'une relation d'ordre strict est antisymétrique. À dire vrai une relation d'ordre strict est antisymétrique en un sens plus fort qu'une relation d'ordre large, c’est-à-dire que si $x$ est en relation avec $y$ par $R$ alors $y$ n'est pas en relation avec $x$ par cette relation. C'est pourquoi on qualifie parfois cette propriété d'antisymétrie forte.

La relation $R$ définie sur $E$ est fortement antisymétrique si :

$\forall (x,y) \in E^2 , \quad x R y \Longrightarrow y \not\!R x$

Cependant pour une relation irréflexive, comme les ordres stricts, cette propriété est équivalente à la propriété d'anti-symétrie définie pour les ordres larges. Il n'y a donc pas d'inconvénient à parler d'anti-symétrie dans les deux cas.

À une relation d'ordre strict, notons la $<$ , on associe naturellement une relation d'ordre large, notons la $\le$ , définie par :

$x \le y \iff x<y \;\vee\; x=y$

Choisir l'une ou l'autre des axiomatisations n'a pas d'importance en soi. Dans les deux cas on a défini un ordre large et un ordre strict associés. En effet on vérifie facilement, en utilisant les propriétés de l'égalité, que :

La relation d'ordre strict associée à une relation d'ordre large (transitive, réflexive et antisymétrique) vérifie bien les axiomes d'ordre stricts (elle est transitive et irréflexive).
La relation d'ordre large associée à une relation d 'ordre strict (transitive et irréflexive) vérifie bien les axiomes d'ordre large (elle est transitive, réflexive et antisymétrique).

[modifier] Propriétés complémentaires

[modifier] Ordre total, ordre partiel

Une relation d’ordre large est totale si elle vérifie :

$\forall (x,y) \in E^2 , \quad x \le y \;\vee\; y \le x$

L’ensemble

E

est alors dit totalement ordonné. On dit aussi que la relation d’ordre $\le$ est totale ou que $(E, \le)$ est un ordre total.

Une relation d’ordre est partielle si elle n’est pas totale, c’est-à-dire s'il existe deux éléments que l'on ne peut mettre en relation, ni dans un sens ni dans l'autre :

$\exists (x,y) \in E^2, x \not\leq y \;\wedge\; y \not\leq x$

L’ensemble

E

est alors dit partiellement ordonné.

Deux éléments $x$ et $y$ tels que ( $x \le y \;\vee\; y \le x$ ) sont dits comparables. La comparabilité est en quelque sorte la symétrisation d’une relation d’ordre. Ainsi un ordre total est un ordre dont tous les éléments sont deux à deux comparables.

Exemples :

L'ensemble $\R$ muni de la relation d'ordre $\le$ est totalement ordonné.
L'ensemble des entiers naturels muni de la relation de divisibilité est partiellement ordonné.

Pour un ordre strict, la totalité s'exprime ainsi :

$\forall (x,y) \in E^2 , \quad x < y \;\vee\; x = y \;\vee\; y < x$

et on dit alors que c'est une relation d'ordre strict total. Il n'y a pas de confusion possible avec le sens précédent de relation totale, car une relation d'ordre strict, qui est irréflexive, ne peut être totale au sens où l'est un ordre large.

Pour un ordre strict total, les trois possibilités — $x < y, x = y, y < x$ — sont exclusives, et l'on parle parfois, à la suite de Cantor, de propriété de trichotomie.

[modifier] Négation (ou complémentaire) d'une relation d'ordre

La négation d'une relation binaire $R$ définie sur un ensemble $A$ est la relation de graphe le complémentaire de celui de $R$ dans $A \times A$ . On la note $\not\! R$ . Dit autrement, deux éléments sont en relation par $\not\! R$ si et seulement s'ils ne le sont pas par $R$ .

Dire qu'un ordre est total, c'est dire que sa négation est l'ordre strict inverse. C’est-à-dire qu'il y a équivalence pour un ordre $\leq$ entre :

$\leq$ est total ;
$x \not\leq y \iff y < x$

Par contre dès qu'il existe deux éléments distincts non comparables par un ordre, sa négation ne peut être un ordre (strict ou large), car elle n'est pas anti-symétrique. La négation d'un ordre non total n'est donc jamais un ordre.

Par exemple, la négation de l'inclusion $\not\subset$ sur l'ensemble des parties d'un ensemble d'au moins deux éléments n'est pas un ordre, car, si $a \not= b$ , on a $\{a\} \not\subset \{b\}$ et $\{b\} \not\subset \{a\}$ .

[modifier] Compatibilité

Une relation d’ordre $\le$ sur un ensemble $E$ muni d’une loi de composition interne $*$ est compatible avec cette loi si et seulement si :

$\forall (x,y,z) \in E^3 , \quad x \le y \Longrightarrow x * z \le y * z \;\wedge\; z * x \le z * y$

La relation d'ordre $\le$ sur l'ensemble des réels est compatible avec l'addition mais pas avec la multiplication.
La relation d'ordre $\le$ sur l'ensemble des réels strictement positifs est compatible avec l'addition et la multiplication.
L’ensemble $\mathbb{C}$ des nombres complexes n’est pas ordonnable par une relation d’ordre compatible avec les opérations d’addition et de multiplication.

Si un groupe est muni d'une relation d'ordre compatible avec sa loi interne, on l'appelle groupe ordonné.

Un groupe totalement ordonné vérifiant la propriété

$\forall (x,y) \in (G_+)^2 , \quad \exists n \in \mathbb N , \quad x \le n y$

est dit archimédien.

[modifier] Ensemble bien ordonné

Un ensemble ordonné est dit bien ordonné si toute partie non vide de cet ensemble possède un plus petit élément.

[modifier] Treillis

Un ensemble est appelé treillis s'il est ordonné et que tout couple d'éléments possède une borne supérieure et une borne inférieure.

[modifier] Diagramme de Hasse

Quand on travaille sur un ordre fini, il peut être agréable de disposer d’une représentation visuelle de celui-ci. On peut en proposer une qui est similaire à la représentation habituelle d’un graphe sur papier. C’est le diagramme de Hasse.

[modifier] Notions dérivées

[modifier] Pré-ordre

Un pré-ordre est une relation binaire réflexive et transitive.

Ce serait une relation d’ordre dans laquelle on autoriserait les cycles non triviaux (c’est-à-dire des cycles de plus d’un élément). Ajouter l’anti-symétrie rend impossible la présence de ces cycles non triviaux.