Relation d'ordre
Un article de Freepedia.
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.
Sommaire |
Présentation
Principales propriétés d’une relation binaire
- Réflexivité : Une relation binaire <math>\mathcal{R}</math> est :
- réflexive, si elle met tout élément en relation avec lui-même, c’est-à-dire si :
- <math> \forall x \in E , \ x \mathcal{R} x \,</math>
- irréflexive, si aucun élément n’est en relation avec lui-même, c’est-à-dire si :
- <math> \forall x \in E , \ x \not \!\,\mathcal{R} x \,</math>
- aréflexive dans les autres cas.
- Symétrie : Une relation binaire <math>\mathcal{R}</math> est :
- symétrique, si tout antécédent est image de ses images, c’est-à-dire si :
- <math> \forall x \in E , \forall y \in E , \ ( x \mathcal{R} y ) \Rightarrow ( y \mathcal{R} x ) \,</math>
- (faiblement) antisymétrique, si les éléments distincts ne sont jamais en relation mutuelle, c’est-à-dire si :
- <math> \forall x \in E , \forall y \in E , \ [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} x ) ] \Rightarrow [ x = y ] \,</math>
- dissymétrique dans les autres cas.
- une relation <math>\mathcal{R}</math> sera fortement antisymétrique (ou asymétrique) si aucune paire d'éléments, distincts ou non, ne sont jamais en relation mutuelle, c'est-à-dire si :
- <math> \forall x \in E , \forall y \in E , \ ( x \mathcal{R} y ) \Rightarrow ( y \not \!\,\mathcal{R} x ) \,</math>
- on peut montrer qu'il est équivalent pour une relation binaire d'être fortement antisymétrique ou d'être faiblement antisymétrique et irréflexive.
- Transitivité : Une relation binaire <math>\mathcal{R}</math> est :
- transitive, si tout élément est image de tout antécédent de ses antécédents, c'est-à-dire lorsque si un élément est image d'un autre élément, alors toutes ses images sont images de cet autre élément, ou encore si :
- <math> \forall x \in E , \forall y \in E , \forall z \in E , \ [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} z ) ] \Rightarrow [ x \mathcal{R} z ] \,</math>
- antitransitive, si tout élément n'est image d'aucun antécédent de ses antécédents, c'est-à-dire si :
- <math> \forall x \in E , \forall y \in E , \forall z \in E , \ [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} z ) ] \Rightarrow [ x \not \!\,\mathcal{R} z ] \,</math>
- circulaire, si tout élément est antécédent de tout antécédent de ses antécédents, c'est-à-dire si :
- <math> \forall x \in E , \forall y \in E , \forall z \in E , \ [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} z ) ] \Rightarrow [ z \mathcal{R} x ] \,</math>
- anticirculaire, si tout élément n'est antécédent d'aucun antécédent de ses antécédents, c'est-à-dire si :
- <math> \forall x \in E , \forall y \in E , \forall z \in E , \ [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} z ) ] \Rightarrow [ z \not \!\,\mathcal{R} x ] \,</math>
Semi-ordre
Pour permettre la comparaison d'éléments, une relation binaire doit avant tout être antisymétrique; pour que cette comparaison soit cohérente pour l'ensemble des éléments, il faut que la relation soit aussi transitive.
Un semi-ordre est ainsi une relation binaire (faiblement) antisymétrique et transitive.
Définition
Une relation d'ordre large est un semi-ordre réflexif, c'est-à-dire une relation binaire réflexive, faiblement antisymétrique et transitive. L'ordre large est noté dans le cas général par « ≤ ».
Une relation d'ordre strict est un semi-ordre irréflexif, c'est-à-dire une relation binaire fortement antisymétrique et transitive. L'ordre strict est noté dans le cas général par « <math> <\,</math> ».
Notions dérivées
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’antisymétrie rend impossible la présence de ces cycles non triviaux.
Ordre dual
Les notions d’ordre large et d’ordre strict sont duales : à tout ordre large correspond un et un seul ordre strict dual obtenu en ôtant les couples ( x , x ) du graphe de la relation, et inversement, à tout ordre strict correspond un et un seul ordre large dual obtenu en ajoutant tous les couples ( x , x ) possibles au graphe; en résumé : G( ≤ ) = G( <math> <\,</math> ) ∪ ΔE et G( <math> <\,</math> ) = G( ≤ ) \ ΔE. C’est pourquoi on ne considère souvent que les relations d’ordre large, que l’on appelle alors relations d’ordre sans autre précision.
Ordre réciproque
- La correspondance réciproque d’un ordre large est encore un ordre large, appelé ordre large réciproque et noté « ≥ ».
- La correspondance réciproque d’un ordre strict est encore un ordre strict, appelé ordre strict réciproque et noté « <math> >\,</math> ».
Pour un ordre donné, l’ordre dual de son réciproque se confond avec l’ordre réciproque de son dual.
Ordre complémentaire
- la correspondance complémentaire d’un ordre large est un ordre strict, appelé ordre strict complémentaire de l’ordre initial.
- De même, l’ordre large complémentaire d’un ordre strict est sa correspondance complémentaire.
Ordre total, ordre partiel
- Une relation d’ordre large est totale si elle est totale, c’est-à-dire si pour tous x, y dans E, on a soit x ≤ y, soit y ≤ x :
- ∀ x, y ∈ E, ( x ≤ y ) ∨ ( y ≤ x )
- L’ensemble E est alors dit totalement ordonné. On dit aussi que la relation d’ordre « ≤ » est totale ou que ( E, ≤ ) est un ordre total.
- Quand une relation d’ordre large est totale, la relation d’ordre strict duale est connexe, c’est-à-dire que pour tous x, y distincts dans E, on a soit x <math> <\,</math> y, soit y <math> <\,</math> x :
- ∀ x, y ∈ E, ( x <math> <\,</math> y ) ∨ ( y <math> <\,</math> x ) ∨ ( x = y )
- On dit alors par abus de langage que la relation d’ordre « <math> <\,</math> » est totale ou que ( E, <math> <\,</math> ) est un ordre total.
- Une relation d’ordre est partielle si elle n’est pas totale . Alors :
- ∃ x ∈ E, ∃ y ∈ E / ¬ ( x ≤ y ) ∧ ¬ ( y ≤ x )
- L’ensemble E est alors dit partiellement ordonné.
L’ordre complémentaire d’un ordre total se confond avec l’ordre réciproque de son dual, mais ce n’est pas vrai pour un ordre partiel. C’est pourquoi, dans la définition de l’ordre partiel ci-dessus, il ne faut surtout pas remplacer les négations « ¬ ( x ≤ y ) » par « ( x <math> >\,</math> y ) ».
Autres notions
- Toute paire d’éléments x et y telle que ( x ≤ y ) ∨ ( y ≤ x ) est dite comparable. 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.
- Une relation d’ordre « ≤ » sur un ensemble E muni d’une loi de composition interne « <math> *\,</math> » est compatible avec cette loi si et seulement si :
- pour tous x, y et z de E, si x ≤ y, alors x <math> *\,</math> z ≤ y <math> *\,</math> z et z <math> *\,</math> x ≤ z <math> *\,</math> y.
- Un ordre large est dit bien fondé si l’ordre strict dual est une relation bien fondée.
- Un ensemble est dit bien ordonné si toute partie non vide de cet ensemble possède un plus petit élément.
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ésention habituelle d’un graphe sur papier. C’est le diagramme de Hasse.
Pour dessiner un diagramme de Hasse :
- On représente les éléments de l’ordre par des points.
- Si un élément x est plus grand qu’un autre élément y selon « ≤ », on place la représentation de x plus haut que celle de y.
- Le fait que deux éléments sont en relation est représenté par un segment entre ces deux points. Du fait de la disposition des points, on n’a pas besoin d’orienter ces segments avec une flèche (on sait qu’on va du bas vers le haut).
- Pour ne pas charger le schéma, on ne représente pas toute la relation d’ordre, mais seulement sa réduction réflexive transitive : d’une part si x ≤ y, mais qu’il existe z différent de x et de y tel que ( x ≤ z ) ∧ ( z ≤ y ), alors on ne trace pas le segment entre x et y ; d’autre part on ne représente pas les boucles d’un élément vers lui-même.
- On veille autant que possible à ne pas croiser les segments.
En cas d’ordre infini, on peut néanmoins aussi utiliser le diagramme de Hasse pour représenter une restriction finie de l’ordre.
- Exemple de diagramme de Hasse :
|
Ici, on a représenté un ensemble ordonné de 11 éléments avec trois éléments maximaux, et un minimum (qui est donc aussi un minorant de l’ensemble et sa borne inférieure). |
Exemples
- L’ensemble des entiers naturels muni de la relation d’ordre usuelle est un ensemble totalement ordonné.
- L’ensemble des parties d’un ensemble muni de l’inclusion est un ensemble partiellement ordonné.
- L’ensemble des entiers naturels non nuls muni de la divisibilité est un ensemble partiellement ordonné.
- Un ensemble E quelconque muni de la relation d’égalité est un ensemble ordonné mais sans grand intérêt.
- L’ensemble <math>\mathbb{C}\,</math> des nombres complexes n’est pas ordonnable par une relation d’ordre compatible avec les opérations d’addition et de multiplication.
