Relation d'ordre
Une relation d'ordre est une relation binaire
réflexive, antisymétrique et transitive. Un ensemble muni d'une relation d'ordre
est un ensemble ordonné ou tout simplement un ordre.
Propriétés et défitions complémentaires
- Une relation d'ordre est totale si pour tout 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).
- Une relation d'ordre est partielle si elle n'est pas totale :
- ∃ x, y ∈ E, ¬(x ≼ y) ∧ ¬ (y ≼ x)
- L'ensemble E est alors dit partiellement ordonné.
- 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 opération ⊤ (ou loi de composition interne) est compatible avec ⊤ si pour tous x,
y et z de E, si x ≼ y, alors x ⊤ z ≼ y ⊤ z et z
⊤ x ≼ z ⊤ y.
Relation d'ordre stricte
Une relation d'ordre stricte est une relation binaire asymétrique et transitive :
- (asymétrie) pour tout
x, y dans E, si on a x ≺ y alors on n'a pas y ≺ x :
- ∀ x, y ∈ E, (x ≺ y) ⇒ ¬(y ≺ x)
- (transitivité) pour tout x, y, z dans
E, si x ≺ y et y ≺ z alors x ≺ z :
- ∀ x, y, z ∈ E, (x ≺ y) ∧ (y ≺ z) ⇒ (x ≺
z)
Une relation d'ordre stricte peut être obtenue à partir d'une relation d'ordre à laquelle on ôte la réflexivité, c'est-à-dire
tous les couples de la forme (x, x) (et réciproquement : en ajoutant la réflexivité à une relation d'ordre
stricte, on obtient une relation d'ordre).
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 il existe z différent de x et 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 :
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 ℂ des nombres complexes n'est pas ordonnable par une relation d'ordre compatible avec les opérations d'addition et
de multiplication.
Voir aussi
Page d'accueil
encyclopedie-enligne.com en page d'accueil