Relation binaire

En mathématiques, une relation binaire entre deux ensembles $E$ et $F$ (ou simplement relation entre $E$ et $F$) est définie par un sous-ensemble du produit cartésien $E\times F$, soit une collection de couples dont la première composante est dans $E$ et la seconde dans $F$. Cette collection est désignée par le graphe de la relation. Les composantes d'un couple appartenant au graphe d'une relation ${\mathcal {R}}$ sont dits en relation par ${\mathcal {R}}$. Une relation binaire est parfois appelée correspondance entre les deux ensembles.

Par exemple, en géométrie plane, la relation d'incidence entre un point et une droite du plan « le point A est sur la droite d » est une relation binaire entre l'ensemble des points et l'ensemble des droites du plan. Les fonctions ou applications d'un ensemble $E$ dans un ensemble $F$ peuvent être vues comme des cas particuliers de relations binaires entre $E$ et $F$.

Lorsque $F=E$, l'ordre des deux composantes d'un couple a son importance. Par exemple, la relation « … est strictement inférieur à … », notée <, sur l'ensemble N des entiers naturels est une relation sur N ; on note $n<p$ pour indiquer que $n$ et $p$ sont en relation. Le couple (1, 2) est un élément du graphe, contrairement au couple (2, 1).

La notion de relation peut être généralisée à plus de deux arguments, voir « Relation (mathématiques) ».

Introduction

De manière informelle, une relation entre deux ensembles est une proposition qui lie certains éléments du premier ensemble avec d'autres éléments du second ensemble.

Sur un ensemble F constitué de filles et un ensemble G constitué de garçons, par exemple, on pourrait définir une relation « Alice aime Bernard », ou une autre relation « Béatrice connaît Paul »… On peut donc voir la relation comme étant des fils reliant des éléments de deux ensembles.

Exemple de représentation sagittale dans le cas d'une composition externe entre deux ensembles disjoints.

Si la relation est une composition interne au sein du même ensemble, ou entre deux ensembles dont l'un recouvre totalement ou en partie l'autre, la représentation sagittale pourra être plutôt celle d'un graphe orienté, afin de ne positionner qu'une seule fois au même endroit sur le graphe les nœuds qui représentent des éléments présents dans les deux ensembles. (Le sens des flèches doit être explicitement indiqué, et les liens d'un nœud vers lui-même pour chacun des éléments liés réflexivement ne doivent pas être omis à moins qu'ils soient implicites pour tous les éléments d'une relation interne).

Dans le cas d'un ensemble fini, on peut alors tenter de représenter la relation par un diagramme. Si F = {Lucie, Béatrice, Delphine, Alice} et si G = {Bernard, Antoine, Paul, Charles}, la relation aime peut être schématisée par le diagramme joint (un tel diagramme est dit diagramme sagittal).

On peut également représenter cette relation, par un tableau à deux entrées, avec en première colonne la liste des éléments de l'ensemble de départ F, et en première ligne celle des éléments de l'ensemble d'arrivée G. Les couples sont représentés par des croix dans les cases à l'intersection de la ligne de la première composante et de la colonne de la seconde composante.

Exemple de représentation matricielle.

.	Bernard	Antoine	Paul	Charles
Lucie	X	X	X	.
Béatrice	.	X	.	.
Delphine	.	.	.	.
Alice	X	.	X	.

On pourra déplorer le fait que Delphine n'aime personne, que Lucie ait un cœur généreux et que Charles puisse se sentir seul.

On peut aussi tenter de faire la liste des couples ainsi en relation (pour plus de commodité, on ne conservera que les deux premières lettres du prénom) :

Gr = {(Lu,Be) , (Lu, An) , (Lu, Pa) , (Bé, An) , (Al, Pa) , (Al, Be)}

En mathématiques, un « couple » est formé de deux éléments mis entre parenthèses dans un ordre particulier. La relation est définie comme un ensemble de couples, c'est-à-dire que si deux éléments sont reliés entre eux, alors le couple est un élément de l'ensemble relation. Si l'on appelle F l'ensemble des filles, et G l'ensemble des garçons, alors l'ensemble de tous les couples possibles est appelé « produit cartésien de F par G » et est noté F × G et la relation aime est alors définie par l'ensemble F, l'ensemble G et un sous-ensemble de F × G.

Définition formelle

Une relation binaire ${\mathcal {R}}$ d'un ensemble $E$ vers un ensemble $F$ est définie par une partie ${\mathcal {G}}$ de $E\times F$.

Si $(x,y)\in {\mathcal {G}}$, on dit que $x$ est en relation avec $y$ et l'on note «  $x{\mathcal {R}}y$  » (notation infixée), « ${\mathcal {R}}(x,y)$», « ${\mathcal {R}}\,x\,y$  » (notations préfixées).

On remarquera qu'il est nécessaire, pour une relation binaire, de préciser l'ensemble $E$ (appelé ensemble de départ), l'ensemble $F$ (appelé ensemble d'arrivée) et la partie ${\mathcal {G}}$ de $E\times F$ appelée le graphe de la relation. Mais pour simplifier, on identifie souvent la relation ${\mathcal {R}}$ avec son graphe ${\mathcal {G}}$.

Quand une relation binaire est définie d'un ensemble $E$ vers lui-même (autrement dit $E=F$ dans la définition précédente, donc définie par une partie ${\mathcal {G}}$ de $E^{2}$), on l'appelle aussi relation interne dans $E$, ou simplement relation dans $E$.

Exemples

• Pour tout ensemble $E$, la relation d'appartenance sur $E\times P(E)$ a pour ensemble de départ $E$ et pour ensemble d'arrivée l'ensemble P(E) des parties de E.
• La relation d'inclusion sur $P(E)$ est une relation interne (d'ordre) .

L'ensemble de définition, ou domaine de ${\mathcal {R}}$ est l'image de son graphe par la première projection $E\times F\to E$, c'est-à-dire l'ensemble : $\{x\in E\mid \exists y\in F\quad (x,y)\in {\mathcal {G}}\}.$ L'image, ou ensemble des valeurs de ${\mathcal {R}}$ est l'image de son graphe par la seconde projection $E\times F\to F$, c'est-à-dire l'ensemble : $\{y\in F\mid \exists x\in E\quad (x,y)\in {\mathcal {G}}\}.$

Si ${\mathcal {R}}$ et ${\mathcal {S}}$ sont deux relations de $E$ vers $F$, ${\mathcal {S}}$ est dite plus fine que ${\mathcal {R}}$ si son graphe est inclus dans celui de ${\mathcal {R}}$, c'est-à-dire si $x{\mathcal {S}}y\Rightarrow x{\mathcal {R}}y$.

Une relation binaire peut aussi être vue comme une « fonction multivaluée », également appelée « correspondance », et le vocabulaire dans ce contexte désigne les mêmes notions (en particulier : graphe, ensemble de définition, image, réciproque).

Composition, réciproque et complémentaire

Composition

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

${\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 ${\mathcal {R}}$ est une relation interne sur un ensemble $E$ et $n$ un entier naturel, on note ${\mathcal {R}}^{n}$ la composition de ${\mathcal {R}}$ avec elle-même $n$ fois, avec la convention que ${\mathcal {R}}^{0}$ dénote la relation d'égalité sur $E$.

Réciproque

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

${\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 ${\mathcal {R}}$⁻¹ sont respectivement l'image et le domaine de ${\mathcal {R}}$ ;
• la réciproque de la réciproque d'une relation ${\mathcal {R}}$ est la relation ${\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 ${\mathcal {R}}$ est une relation de $E$ vers $F$, on peut définir une relation de $E$ vers $F$ dite relation complémentaire, ou complément logique, par :

${\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 ${\mathcal {R}}$ se déduit simplement de celle de ${\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 ${\mathcal {R}}$ est la relation ${\mathcal {R}}$ elle-même ;
• le complémentaire de la réciproque d'une relation ${\mathcal {R}}$ est la réciproque du complémentaire de ${\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.

Relation fonctionnelle

Lorsque, pour tout élément $x$ de $E$, $x$ n'est en relation qu'avec 0 ou 1 élément $y$ de $F$, on dit que la relation est fonctionnelle. C'est une façon élémentaire de définir la notion de fonction. En langage formel, la propriété précédente s'écrit :

$\forall x\in E\quad \forall y\in F\quad \forall z\in F\quad [(x,y)\in {\mathcal {G}}_{\mathcal {R}}\land (x,z)\in {\mathcal {G}}_{\mathcal {R}}]\Rightarrow (y=z).$

Exemple important :

La diagonale de $E$ est définie par :

$\Delta _{E}=\left\{(x,x)\mid x\in E\right\}.$

C'est le graphe de la relation d'égalité sur $E$, notée $=_{E}$, ou $=$ en l'absence d'ambiguïté sur l'ensemble concerné.

Cette relation est aussi une fonction, l'identité de $E$, notée $id_{E}$.

Relation sur (ou dans) un ensemble

Dans le cas particulier où $E=F$, on dit que ${\mathcal {R}}$ est une relation binaire définie sur $E$ ou dans $E$.

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

Relation réflexive

La relation ${\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 :

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

Relation irréflexive

La relation ${\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 :

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

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

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

Relation symétrique

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

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

Relation antisymétrique

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

• antisymétrique (ou faiblement antisymétrique) si :$\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 :

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

Transitivité

La relation ${\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 :

$\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 :

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

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

${\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 ${\mathcal {R}}$.

Relation totale

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

$\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 :

${\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. La condition s'écrit :

$\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

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

où ${\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.

Dénombrements concernant les relations binaires entre des ensembles finis

Considérons un ensemble $E$ fini de cardinal $n$ et un ensemble $F$ fini de cardinal $p$.

Il y a autant de relations binaires de $E$ sur $F$ que de parties de $E\times F$ (ou d'applications de $E\times F$ dans {0, 1} ), ce qui donne $2^{np}$ relations.

En particulier, si $E=F$, on trouve $2^{n^{2}}$ relations binaires sur $E$, dont

• $2^{n(n-1)}$ relations réflexives, voir la suite A053763 de l'OEIS.
• $2^{n(n+1)/2}$ relations symétriques.
• $2^{n(n-1)/2}$ relations réflexives et symétriques, voir la suite A006125 de l'OEIS.
• $2^{n}.3^{n(n-1)/2}$ relations antisymétriques, voir la suite A083667 de l'OEIS.
• $3^{n(n-1)/2}$ relations totales.
• $2^{n(n+1)/2}$ relations de tournoi.
• $n!$ relations d'ordre totales.
• $B_{n}$ relations d'équivalences, où $B_{n}$ est le nombre de Bell.
• Pour le nombre de relations transitives, il n'y a pas actuellement de formule « fermée » ; voir la suite A006905 de l'OEIS.
• De même pour le nombre de relations d'ordre : voir la suite A001035 de l'OEIS.

La catégorie des relations binaires

Les relations binaires et la composition des relations forment une catégorie que l'on appelle la catégorie des relations et que l'on note Rel.

Liens

• N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions]
• Paul Halmos, Introduction à la théorie des ensembles [détail des éditions]
• (en) Yiannis Moschovakis, Notes on Set Theory [détail des éditions]
• Alfred Tarski & Givant, Steven, 1987. 2004, « A Formalization of Set Theory Without Variables », American Mathematical Society.
• Maddux, Roger D. (en), 2006. Relation Algebras, vol. 150 in "Studies in Logic and the Foundations of Mathematics", Elsevier Science.