Relation binaire

Si ${\displaystyle {\mathcal {R}}}$ est une relation de E dans F et ${\displaystyle {\mathcal {S}}}$ de F dans G, on peut définir une relation ${\displaystyle {\mathcal {S}}\circ {\mathcal {R}}}$ de E dans G par :

${\displaystyle {\mathcal {G}}_{{\mathcal {S}}\circ {\mathcal {R}}}=\left\{(x,y)\in E\times G\mid \exists z\in F\quad (x,z)\in {\mathcal {G}}_{R}{\text{ et }}(z,y)\in {\mathcal {G}}_{S}\right\}.}$

Notation : si ${\displaystyle {\mathcal {R}}}$ est une relation interne sur un ensemble E et n un entier naturel, on note ${\displaystyle {\mathcal {R}}^{n}}$ la composition de ${\displaystyle {\mathcal {R}}}$ avec elle-même n fois, avec la convention que ${\displaystyle {\mathcal {R}}^{0}}$ dénote la relation d'égalité sur E.

Si ${\displaystyle {\mathcal {R}}}$ est une relation de E sur F, on peut définir une relation de F sur E dite relation inverse, réciproque ou converse, par :

${\displaystyle {\mathcal {G}}_{{\mathcal {R}}^{-1}}=\left\{(x,y)\in F\times E\mid (y,x)\in {\mathcal {G}}_{\mathcal {R}}\right\}.}$

Exemples :

« plus petit que » (≤) et « plus grand que » (≥) sont des relations réciproques l'une de l'autre (pour n'importe quelle relation d'ordre ≤) ;

« aime » et « est aimé par » sont aussi réciproques l'une de l'autre.

La représentation d'une relation réciproque se déduit simplement de celle de la correspondance de départ :

• pour la représentation sagittale, en changeant le sens des liens (vu de la gauche vers la droite sur le schéma) ;
• pour une représentation matricielle, en échangeant lignes et colonnes, c'est-à-dire en prenant la matrice transposée.

Par construction, la réciproque d'une relation binaire a les propriétés suivantes :

• le domaine et l'image de ${\displaystyle {\mathcal {R}}}$⁻¹ sont respectivement l'image et le domaine de ${\displaystyle {\mathcal {R}}}$ ;
• la réciproque de la réciproque d'une relation ${\displaystyle {\mathcal {R}}}$ est la relation ${\displaystyle {\mathcal {R}}}$ elle-même.

De plus, une relation interne est symétrique (resp. réflexive, resp. antiréflexive) si (et seulement si) sa réciproque l'est.

Si ${\displaystyle {\mathcal {R}}}$ est une relation de E vers F, on peut définir une relation de E vers F dite relation complémentaire[3], ou complément logique, par :

${\displaystyle {\mathcal {G}}_{\mathcal {{} \over R}}=\left\{(x,y)\in E\times F\mid (x,y)\notin {\mathcal {G}}_{\mathcal {R}}\right\}.}$

Exemples :

« plus petit que » (≤) et « strictement plus grand que » (>) sont des relations complémentaires l'une de l'autre pour n'importe quel ordre total ≤ (comme l'ordre sur les réels) ;

« aime » et « n'aime pas » sont aussi complémentaires l'une de l'autre.

La représentation de la relation complémentaire de ${\displaystyle {\mathcal {R}}}$ se déduit simplement de celle de ${\displaystyle {\mathcal {R}}}$ :

• pour la représentation sagittale, en supprimant tous les liens déjà existants et ajoutant ceux qui n'existent pas encore (y compris ceux en sens opposés si c'est une composition interne et la représentation est un graphe orienté sur un seul ensemble, sinon en ajoutant ceux qui manquent dans le même sens entre les éléments des deux ensembles tracés séparément) ;
• pour une représentation matricielle, en remplaçant par leur complément logique les valeurs booléennes de chacune des cellules de la matrice.

Par construction, le complémentaire d'une relation binaire a les propriétés suivantes :

• le complémentaire du complémentaire d'une relation ${\displaystyle {\mathcal {R}}}$ est la relation ${\displaystyle {\mathcal {R}}}$ elle-même ;
• le complémentaire de la réciproque d'une relation ${\displaystyle {\mathcal {R}}}$ est la réciproque du complémentaire de ${\displaystyle {\mathcal {R}}}$.

De plus, une relation interne est :

• symétrique si et seulement si sa relation complémentaire l'est ;
• réflexive si et seulement si sa relation complémentaire est antiréflexive.

La relation ${\displaystyle {\mathcal {R}}}$ sur E est dite réflexive si tout élément de E est en relation avec lui-même, c'est-à-dire si :

${\displaystyle \forall x\in E\quad x{\mathcal {R}}x.}$

La relation ${\displaystyle {\mathcal {R}}}$ sur E est irréflexive ou antiréflexive si aucun élément de E n'est en relation avec lui-même, c'est-à-dire si :

${\displaystyle \forall x\in E\quad x{\cancel {\mathcal {R}}}x.}$

Une relation peut n'être ni réflexive, ni antiréflexive.

La relation ${\displaystyle {\mathcal {R}}}$ est symétrique si :

${\displaystyle \forall (x,y)\in E^{2},x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x.}$

La relation ${\displaystyle {\mathcal {R}}}$ est dite :

• antisymétrique (ou faiblement antisymétrique) si :${\displaystyle \forall (x,y)\in E^{2},(x{\mathcal {R}}y\wedge y{\mathcal {R}}x)\Rightarrow x=y}$ ;
• asymétrique (ou fortement antisymétrique) si :

${\displaystyle \forall (x,y)\in E^{2},x{\mathcal {R}}y\Rightarrow (y{\cancel {\mathcal {R}}}x),}$ ou encore, si elle est à la fois antisymétrique (au sens faible) et antiréflexive.

Une relation peut n'être ni symétrique, ni antisymétrique.

La relation ${\displaystyle {\mathcal {R}}}$ sur E est transitive si, lorsqu'un premier élément de E est en relation avec un deuxième élément lui-même en relation avec un troisième, le premier élément est aussi en relation avec le troisième, c'est-à-dire si :

${\displaystyle \forall x,y,z\in E\quad (x{\mathcal {R}}y\wedge y{\mathcal {R}}z)\Rightarrow x{\mathcal {R}}z,}$

ou encore, si son graphe contient celui de sa composée avec elle-même, ce qui s'écrit :

${\displaystyle {\mathcal {G}}_{{\mathcal {R}}\circ {\mathcal {R}}}\subseteq {\mathcal {G}}_{\mathcal {R}}.}$

On appelle clôture transitive, ou fermeture transitive de ${\displaystyle {\mathcal {R}}}$ la relation

${\displaystyle {\mathcal {R}}^{trans}=\bigcup _{n\geq 1}{\mathcal {R}}^{n}.}$

C'est la plus petite (au sens de l'inclusion des graphes) relation transitive contenant ${\displaystyle {\mathcal {R}}}$.

La relation ${\displaystyle {\mathcal {R}}}$ sur E est totale (en) si :

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

ou encore, si l'union de son graphe avec celui de sa réciproque est égal au carré cartésien de E, ce qui s'écrit :

${\displaystyle {\mathcal {G}}_{\mathcal {R}}\cup {\mathcal {G}}_{{\mathcal {R}}^{-1}}=E^{2}}$.

On emploie le plus souvent ce qualificatif à propos des relations d'ordre.

Toute relation totale est réflexive.

Une relation d'équivalence est une relation réflexive, transitive et symétrique.

Une relation d'ordre est une relation réflexive, transitive et antisymétrique.

Si une relation d'ordre est totale, on dit que c'est un ordre total. Dans les cas contraires, on dit que c'est seulement un ordre partiel.

Un tournoi est une relation binaire totale et antisymétrique[4]. La condition s'écrit :

${\displaystyle \forall (x,y)\in E^{2},\left(x\neq y\Rightarrow (xRy\Leftrightarrow y{\cancel {R}}x)\right)\land \left(x=y\Rightarrow xRy\right)}$

Cette définition est à rapprocher (sans lui correspondre totalement) à celle de tournoi en théorie des graphes : un tournoi est un graphe orienté vérifiant[5]

${\displaystyle \forall (x,y)\in E^{2},x\neq y,(x,y)\in {\mathcal {A}}\Leftrightarrow (y,x)\notin {\mathcal {A}}}$

où ${\displaystyle {\mathcal {A}}}$ est l’ensemble des arêtes du graphe.

Un tournoi permet de modéliser les tournois en compétition sportive où chaque équipe joue contre toutes les autres sans match nul.