Précédent / Suivant / Table des matières

0. Relations binaires

0-1. Généralités

Définition 1 : Une relation binaire d’un ensemble E vers un ensemble F est  une partie R de E×F. Si (x,y)R on dit que x est en relation avec y et on note xRy. Si (x,y)R on dit que x n’est pas en relation avec y et on note xRy. Dans le cas particulier où E=F on dit que R est une relation binaire définie sur E.

 

Remarque 1 : Souvent on peut représenter une relation binaire  par un diagramme sagittal, par un diagramme cartésien, par une table ou encore par une matrice.

 

Définition 2 : Soit R une relation binaire d’un ensemble E vers un ensemble F.
On appelle domaine de R  et on note Dom(R) l’ensemble Dom(R,)={xE tq yF tq xRy}
On appelle codomaine de R  et on note Codom(R) l’ensemble Codom(R)={yF tq xE tq xRy}
On appelle coupe de R  selon un élément x0 de E et on note Coupex0(R) l’ensemble
Coupex0(R) ={(x0,y)E×F tq x0Ry}

 

Cas particuliers : Soit R=, R=E×F et l’égalité Δ : (x,y)Δ  x=y

 

Définition 3 : Soit R une relation binaire d’un ensemble E vers un ensemble F. On appelle relation réciproque de R et on note R -1 la relation binaire de F vers E définie par :
((x,y)E×F)   (xR -1y)  (yRx).

 

Définition 4 : On dit qu’une relation R est incluse dans une relation S et on note RS, si
(x,y)E×F (x,y)R  (x,y)S. On dit que deux relations R et S sont égales si RS et S  R.

 

Définition 5 : Soit R une relation binaire d’un ensemble E vers un ensemble F.
On appelle relation complémentaire de R  et on note R’ la relation binaire de E vers F définie par : ((x,y)E×F) (x,y)R’  (x,y)R.

 

Définition 6 : Soient R et S deux relations binaires d’un ensemble E vers un ensemble F. On appelle réunion de R et S et on note T=RS la relation binaire T de E vers F définie par : ((x,y)E×F)   xTy  (xRy)(xSy).
On appelle intersection de R et S et on note T=R∩S la relation binaire T de E vers F définie par : ((x,y)E×F)   xTy  (xRy)(xSy).
De même on définit sur les relations binaires l’analogue des opérations ensemblistes R\S etc.

 

Définition 7 : Soient R une relation binaire d’un ensemble E vers un ensemble F et S une relation binaire de l’ensemble F vers un ensemble G. La composée T de R et S est une relation binaire de l’ensemble E vers l’ensemble G notée T =RοS ou T =RS et définie par :
((x,y)E×G)   (xTy)  (zF tq (xRz)(zSy)).

 

Notation 1 : Dans le cas particulier où E=F=G on note R2 =RοR=RR

 

Proposition 1 : Soient R une relation binaire d’un ensemble E vers un ensemble F, S une relation binaire de l’ensemble F vers un ensemble G et T une relation binaire de l’ensemble G vers un ensemble H. Alors (RS)T =R(ST). (associativité de la composition des relations binaires)

 

Proposition 2 : Soit R une relation binaire d’un ensemble E vers un ensemble F, S et T deux relations binaires de l’ensemble F vers un ensemble G et U une relation binaire de l’ensemble G vers un ensemble H. Alors :

·       R(ST)=RSRT

·       R(S∩T)RS∩RT

·       (ST)U=SUTU

·       (S∩T)USU∩TU

 

Remarque 3 : La composition des relations binaires étant associative on supprimera les parenthèses : (RS)T =R(ST)=RST. En particulier si R une relation binaire définie sur un ensemble E on notera Rn =RR … R où nN*. En particulier R1 =R et par convention R0 sera l’égalité Δ.

 

Définition 8 : On dit qu’une relation binaire R définie sur un ensemble E est :

·     réflexive si   (xE)   xRx.

·     symétrique si   ((x,y)E2)   (xRy)  (yRx).

·     transitive si   ((x,y,z)E3)   (xRy)(yRz)  (xRz).

·     antisymétrique si   ((x,y)E2)   (xRy)(yRx)  (x=y).

 

0-2. Fermeture des relations binaires

 

Définition 9 : Soit R une relation binaire définie sur un ensemble E. On appelle fermeture réflexive de R et on note r(R) la plus petite (au sens de l’inclusion) relation réflexive définie sur E contenant R. Autrement dit r(R) est la relation binaire définie sur l’ensemble E telle que :

·       r(R) est réflexive

·       Rr(R)

·       Pour toute relation binaire S réflexive définie sur l’ensemble E, si SR alors Sr(R)

 

Définition 10 : Soit R une relation binaire définie sur un ensemble E. On appelle fermeture symétrique de R et on note s(R) la plus petite (au sens de l’inclusion) relation symétrique définie sur E contenant R. Autrement dit s(R) est la relation binaire définie sur l’ensemble E telle que :

·       s(R) est symétrique

·       Rs(R)

·       Pour toute relation binaire S symétrique définie sur l’ensemble E, si SR alors Ss(R)

 

Définition 11 : Soit R une relation binaire définie sur un ensemble E. On appelle fermeture transitive de R et on note t(R) la plus petite (au sens de l’inclusion) relation transitive définie sur E contenant R. Autrement dit t(R) est la relation binaire définie sur l’ensemble E telle que :

·       t(R) est transitive

·       Rt(R)

·       Pour toute relation binaire S transitive définie sur l’ensemble E, si SR alors St(R)

 

Remarque 4 : Soit R une relation binaire définie sur un ensemble E. Alors

·       R est réflexive si et seulement si R=r(R)

·       R est symétrique si et seulement si R=s(R)

·       R est transitive si et seulement si R=t(R)

 

Théorème 4 : Soit R une relation binaire définie sur un ensemble E. Alors

·       r(R)= RΔ où Δ est la relation « égalité » sur E

·       s(R)= RR1 où R1  est la relation réciproque de R

·        =RR2R3…..

 

Remarque 5 : Soit R une relation binaire définie sur un ensemble E. Alors (x,y)t(R) si et seulement si il existe une suite c0, c1, c2, …, cn d’éléments de E où n≥1, c0=x et cn=y et telle que 0≤i<n  ciRci+1 (notion de chemin).

 

Notation 2 : On note R+ la fermeture transitive de R et R* la fermeture réflexive et transitive de R.

 

0-3. Relations d’équivalence

 

Définition 12 : Une relation binaire dans un ensemble E est une relation d’équivalence si elle est réflexive, symétrique et transitive.

 

Définition 13 : Soit R une relation d’équivalence dans un ensemble E et xE. On appelle classe d’équivalence de x par R (ou modulo R ) et on note  l’ensemble   = {yE  tq  xRy}.
Un élément d’une classe d’équivalence est appelé représentant de cette classe d’équivalence. L’ensemble de toutes les classes d’équivalence est appelé ensemble quotient de E par R. On le note E/R.

 

Remarque 6 : Soit R une relation d’équivalence dans un ensemble E et xE. On a :
E          E/R             E/RP(E)

 

Lemme 1 : Soit R une relation d’équivalence dans un ensemble E et x et y deux éléments de E. Alors  

 

Proposition 3 » : Toute relation d’équivalence dans un ensemble E détermine une partition de E. Inversement toute partition de E détermine une relation d’équivalence dans E.

0-4. Relations d’ordre

 

Définition 14 : Une relation binaire dans un ensemble E est une relation de préordre si elle est réflexive et transitive. C’est une relation d’ordre si en plus elle est antisymétrique.
Une relation d’ordre est totale si  ((x,y)E2)   (xRy)(yRx).
Elle est dite partielle dans le cas contraire.

 

Définition 15 : Un couple (E,R) formé d’un ensemble E et d’une relation d’ordre R est appelé ensemble ordonné. Si R est totale l’ensemble est dit totalement ordonné.

 

Notation 3 : Soit (E, R) un ensemble ordonné et (x,y)E2. On note :

·     [x , y] = {zE  tq  (xRz)(zRy)}

·     [x , y[ = {zE  tq  (xRz)(zRy)(z≠y)}

·     ]x , y] = {zE  tq  (xRz)(zRy)(z≠x)}

·     ]x , y[ = {zE  tq  (xRz)(zRy)(z≠x)(z≠y)}

·     [x , →[ = {zE  tq  xRz}

·     ]x , →[ = {zE  tq  (xRz)(z≠x)}

·     ]←, x] = {zE  tq  zRx}

·     ]←, x[ = {zE  tq  (zRx)(z≠x)}

 

Terminologie 1 : Soit (E, R) un ensemble ordonné et (x,y)E2.

·     On dit que x et y sont comparables si (xRy) ou (yRx). Ils sont dits non comparables dans le cas contraire.

·     Si xRy on dit que x est inférieur à y ou que y est supérieur à x.

·     Si xRy et y≠x on dit que x est strictement inférieur à y ou que y est strictement supérieur à x.

·     On dit que y est un successeur immédiat de x (ou que y couvre x) si x est strictement inférieur à y et il n’existe pas de z tel que x soit strictement inférieur à z et z soit strictement inférieur à y. On dit alors que x est un prédécesseur immédiat de y (ou que x est couvert par y).

 

Définition 16 : Soit (E,R) un ensemble ordonné et A une partie de E.

·     aA est un élément maximal de A s’il n’existe pas de yA tel que aRy et y≠a.

·     bA est un élément minimal de A s’il n’existe pas de yA tel que yRb et y≠b.

 

Diagramme de Hasse : un ensemble ordonné (E, R) où E est fini peut être représenté par un diagramme où la réflexivité et la transitivité sont implicites. Chaque élément de E est représentée par un point, un segment (ou arc) joignant deux points x et y représente xRy . On utilise le « haut » et le « bas » (la « gauche » et la « droite ») pour se passer d’un sens fléché.

·     Le diagramme de Hasse d’un ensemble ordonné s’obtient en procédant de proche en proche à partir des éléments maximaux et de leurs prédécesseurs immédiats.

·     Le diagramme d’un ensemble totalement ordonné s’appelle une chaîne

·     Une partie A d’un ensemble ordonné est une chaîne maximale si

            1) C’est une chaîne de E

            2) Il n’existe pas de chaîne B telle que AB.

 

Définition 17 : Soit (E, R) un ensemble ordonné et A une partie de E.

·     On dit qu’un élément x de E est un majorant (resp minorant) de A si (yA)   yRx.
(resp (yA)   xRy.)

·     Si l’ensemble des majorants (resp minorant) de A est non vide on dit que A est majoré (resp minoré).

·     Une partie A majorée et minorée est dite bornée.

 

Définition 18 : Soit (E, R) un ensemble ordonné et A une partie de E.

·     On dit que m est un minimum (ou plus petit élément) de A si m est un minorant de A et mA. On note m = min(A).

·     On dit que M est un maximum (ou plus grand élément) de A si M est un majorant de A et
MA. On note M = max(A).

 

Remarque 7 : Si A admet un plus petit (resp plus grand) élément alors cet élément est unique.

 

Définition 19 : Soit (E,R) un ensemble ordonné et A une partie de E.

·     Si A est majoré et si l’ensemble des majorants de A possède un plus petit élément alors ce dernier est appelé borne supérieure de A et on note SupA.

·     Si A est minoré et si l’ensemble des minorants de A possède un plus grand élément alors ce dernier est appelé borne inférieure de A et on note InfA.

 

Remarque 8 : Si A admet un plus grand (resp plus petit) élément alors on a maxA = SupA (resp minA = InfA).

 

Définition 20 : On appelle treillis un ensemble ordonné (E,R) tel que toute paire {x,y} d’éléments de E possède une borne supérieure (notée x+y) et une borne inférieure (notée x.y)

 

Définition 21 : Soit (E,R1) et (F,R2) deux ensembles ordonnés et f une application de E dans F. On dit que f est croissante (resp décroissante) si pour tout couple  (x,y) de E2 tel que  xR1y on a  f(x)R2f(y) (resp f(y)R2f(x)).

 

Proposition 4 :

·     La composée de deux applications croissantes est croissante.

·     La composée de deux applications décroissantes est croissante.

·     Si f est une bijection croissante sa réciproque n’est pas nécessairement croissante.