Relation binaire

Une relation binaire est un type particulier de relation, d’arité deux. Parmi les relations binaires typiques, on trouve par exemple « plus petit que », l’égalité, la divisibilité, « plus grand que », etc.

Exemples

La relation binaire est l’une des relations les plus typiques et les plus courantes. Elle a aussi quelques propriétés intéressantes, que nous allons décrire ici.

Voici des exemples de relations binaires : le lien « père — fils », le couple « moyen de transport — nombre de roues » ou, plus généralement, « objet — propriété de l’objet ». L’objet peut être un animal et la propriété le nombre de pattes, l’espérance de vie moyenne, le nombre de poils sur la tête, etc.

Une relation binaire R entre des ensembles M₁ et M₂ peut se définir ainsi : R ⊂ M₁ × M₂. Une relation binaire est donc un ensemble de couples, et cet ensemble est une partie du produit cartésien des deux ensembles entre lesquels on définit la relation. La relation « père — fils » peut donc être une relation entre l’ensemble de tous les humains, entre l’ensemble de tous les habitants de l’Europe ou de ceux de Paris. On peut aussi restreindre l’ensemble dans un autre sens : on peut dire que la relation est définie entre l’ensemble de tous les hommes, et non entre les humains en général.

Pour les relations binaires, on utilise habituellement une notation spéciale. Au lieu d’écrire (a ; b) ∈ R, on peut écrire aRb. Par exemple, au lieu de (3 ; 1) ∈ >, on peut écrire 3 > 1. Il en va de même pour les autres relations. L’écriture aSb est donc équivalente à (a ; b) ∈ S.

Relation réciproque

La relation réciproque est la relation opposée à la relation de départ. (Attention, ne la confonds pas avec le complémentaire d’une relation.) Quelle est la relation opposée à « plus petit que » ? « Plus grand que ». Si la relation « plus petit que » contient le couple (4 ; 7), c’est-à-dire 4 < 7, alors le couple réciproque sera l’inverse : 7 > 4, et dans la relation réciproque figurera le couple inversé (7 ; 4).

Si l’on a une relation R ⊂ M₁ × M₂, on construit la relation réciproque R⁻¹ en prenant tous les couples (a ; b) ∈ R et en plaçant leur inverse dans R⁻¹. Donc, si la relation R contient le couple (a ; b), la relation R⁻¹ doit contenir le couple (b ; a). Cela vaut aussi dans l’autre sens : si R⁻¹ contient le couple (b ; a), alors la relation R doit contenir le couple (a ; b).

En termes de définition, la relation R⁻¹ est la réciproque de R si et seulement si :

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a;b)\in R\iff (b;a)\in R^{-1}$$

Ainsi, 6 < 8 si et seulement si 8 > 6. Il en va de même pour les autres couples.

Composition de relations

On peut composer des relations binaires entre elles. Prenons deux relations : la première, R, sera « être le père de son fils » et la seconde, S, « être le frère de sa sœur ». La relation R contient donc des couples (père ; fils) et la seconde relation contient des couples (frère ; sœur).

Essayons maintenant de composer ces relations. Nous obtenons une nouvelle relation, que nous notons R ∘ S, et cette relation contient le couple (a ; c) si et seulement si (a ; b) ∈ R et en même temps (b ; c) ∈ S. Remarque que b apparaît dans les deux couples, une fois en deuxième position et une fois en première position. C’est l’élément de liaison de la composition.

Exemple : R = {(Hugo ; Lucas) ; (Louis ; Tom)} et S = {(Lucas ; Emma) ; (Lucas ; Jade) ; (Tom ; Lola)}. Hugo est le père de Lucas, Louis est le père de Tom. Lucas a deux sœurs, Emma et Jade, et Tom a une sœur, Lola.

Composons maintenant les relations : R ∘ S. Nous cherchons un couple de R dont le fils est quelqu’un qui figure comme frère dans la relation S. Par exemple, ces deux couples : (Hugo ; Lucas) et (Lucas ; Emma). Lucas est l’élément de liaison, nous n’en avons plus besoin, et avec les noms restants nous formons un nouveau couple : (Hugo ; Emma). La relation R ∘ S contient donc le couple (Hugo ; Emma). Lucas a encore une autre sœur, Jade, que nous ajoutons aussi à la relation composée : (Hugo ; Jade). Il reste enfin le fils Tom. Il a une sœur, Lola. Nous avons donc deux couples : (Louis ; Tom) et (Tom ; Lola). Nous en tirons un autre élément : (Louis ; Lola).

Le résultat est la relation : R ∘ S = {(Hugo ; Emma) ; (Hugo ; Jade) ; (Louis ; Lola)}. Comment pourrait-on nommer cette relation ? Sans doute « être le père de sa fille ».

Encore une fois, la définition complète :

$$(a;c)\in (R\circ S)\iff \mathrm{\exists }b(a;b)\in R\wedge (b;c)\in S$$

Remarque : on utilise parfois la notation inverse, c’est-à-dire que, pour la même définition, on écrirait S ∘ R au lieu de R ∘ S.