Composition

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.

Réciproque

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.

Complémentaire

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.

Propriétés liées à la réflexivité

Propriétés liées à la symétrie

Transitivité

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}}}$.

Relation totale

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.

Relation d'équivalence

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

Relation d'ordre

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.

Relation de tournoi

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.

Relation bien fondée