128
40
1 re année
Relations
1. Relation binaire
Choisir une partie de E × E, c'est définir une relation binaire R sur E. Si
(x,y) ∈ , on dit que x et y sont en relation, et on note xRy.
Une relation binaire R , définie sur un ensemble E, est :
réflexive si elle vérifie :
∀x ∈ E xRx ;
symétrique si
∀x ∈ E ∀y ∈ E xRy ⇒ yRx ;
antisymétrique si elle vérifie l'une des deux propriétés équivalentes :
∀x ∈ E ∀y ∈ E
(xRy et yRx) ⇒ x = y ,
∀x ∈ E ∀y ∈ E
(xRy et x = / y) ⇒ non (yRx) .
transitive si elle vérifie :
∀x ∈ E ∀y ∈ E ∀z ∈ E
(xRy et yRz) ⇒ xRz .
Attention, l'antisymétrie n'est pas le contraire de la symétrie.
L'égalité est à la fois symétrique et antisymétrique. Une relation peut
n'être ni symétrique, ni antisymétrique.
2. Relation d'ordre
2.1 Définitions
Une relation binaire R , définie sur un ensemble E, est une relation d'ordre si elle
est, à la fois, réflexive, antisymétrique et transitive.
Notons la ≺.
Une relation d'ordre ≺ dans E est dite relation d'ordre total si deux éléments quelconques x et y de E sont toujours comparables, c'est-à-dire si l'on a x ≺ y ou
y ≺ x.
Dans le cas contraire, l'ordre est partiel.
2.2 Exemples
est un ordre total dans R. ⊂ est un ordre partiel dans P(E).
9782100549245-fredon-C37-51.qxd 18/06/10 10:33 Page 128