Relation binaire sur un ensemble

Par relation binaire sur un ensemble, on entend une relation binaire définie entre deux ensembles identiques.

Exemples

Une relation binaire sur un ensemble est un type particulier de relation binaire, où les deux ensembles supports sont les mêmes. Une relation binaire sur un ensemble est donc une relation R telle que R ⊂ M × M.

La relation « plus grand que » est une relation binaire sur un ensemble, car des deux côtés on travaille avec des nombres. On a donc > ⊂ ℝ × ℝ. La relation « père — nombre d’enfants » n’est pas une relation binaire sur un ensemble, car on choisit les pères dans l’ensemble de tous les humains, alors qu’on choisit le nombre d’enfants dans un ensemble de nombres.

Propriétés

Une relation binaire R sur un ensemble M peut avoir certaines propriétés intéressantes. On dit que la relation R est…

• réflexive si, pour tout a ∈ M, on a (a ; a) ∈ R.
• symétrique si, pour tous a, b ∈ M, si (a ; b) ∈ R, alors (b ; a) ∈ R aussi.
• antisymétrique si, pour tous a, b ∈ M, si (a ; b) ∈ R et en même temps (b ; a) ∈ R, alors a = b.
• transitive si, pour tous a, b, c ∈ M, si (a ; b) ∈ R et en même temps (b ; c) ∈ R, alors (a ; c) est aussi dans R.

Exemples de réflexivité

La réflexivité signifie qu’un élément est en relation avec lui-même. L’exemple typique est l’égalité. Si l’on définit l’égalité sur les entiers naturels non nuls, on a bien, pour n’importe quel élément a : a = a. La divisibilité en est un autre exemple. Là encore, le nombre a est divisible par lui-même, donc le couple (a ; a) est dans la relation de divisibilité (7 divise 7).

La relation « plus petit que », elle, n’est pas réflexive, car on n’a pas a < a. C’est impossible : 7 ne peut pas être plus petit que 7. De même pour la relation « être le père de son enfant » : je ne peux pas être mon propre père. De telles relations ne sont pas réflexives.

Il est important que la réflexivité soit vraie pour tous les éléments : il ne suffit pas d’en trouver quelques-uns. Prenons par exemple la relation « aimer bien quelqu’un ». Je peux aimer bien quelqu’un, par exemple un contrôleur, mais je peux aussi m’aimer bien moi-même. On trouvera sûrement quelqu’un qui s’aime bien. Mais on trouvera tout aussi bien quelqu’un qui ne s’aime pas. Une telle relation n’est donc pas réflexive : il faudrait que tous les humains s’aiment eux-mêmes.

Exemples de symétrie

Dans une relation symétrique, si un couple est dans la relation, alors le couple inversé y est aussi. C’est le cas par exemple de la relation « être frère ou sœur de ». Si Hugo est le frère de Jade, alors Jade est aussi la sœur de Hugo. Parmi les relations numériques, on pourrait prendre la relation « être l’opposé de ». J’entends par là les couples 2 et −2 ou −7 et 7. Ce sont deux nombres dont la somme est nulle. Une telle relation est symétrique, car l’ordre n’a tout simplement pas d’importance : (2 ; −2) et (−2 ; 2) sont toujours deux nombres opposés l’un de l’autre et leur somme vaut zéro.

Une relation qui n’est pas symétrique est « plus petit que » (sur les nombres réels). Elle n’a aucun couple symétrique, car on ne peut jamais avoir a < b et en même temps b < a. Si 5 < 15, on ne peut pas avoir 15 < 5. La relation « être le père de son fils » n’est pas symétrique non plus. Tu peux être le père de ton fils, mais alors le fils ne peut pas être le père de son père.

Cette propriété doit là encore être vraie dans tous les cas. Pour que la relation « aimer bien quelqu’un » (sur l’ensemble de tous les humains) soit symétrique, il faudrait que, si j’aime bien Chloé, Chloé m’aime bien aussi. Or elle ne me connaît même pas, donc je ne peux pas dire qu’elle m’aime bien, ce qui est dommage, et la relation n’est pas symétrique. Ce qui est dommage aussi.

Exemples d’antisymétrie

Un exemple classique de relation antisymétrique est « inférieur ou égal à ». L’antisymétrie nous dit que, si les couples (a ; b) et (b ; a) sont dans la relation, alors c’est uniquement lorsque les éléments sont égaux, a = b. La relation « inférieur ou égal à » vérifie cela. Quand a-t-on a ≤ b et en même temps b ≤ a ? Seulement si a = b. Essayons : a-t-on 3 ≤ 5 et en même temps 5 ≤ 3 ? Non. Mais on a bien 4 ≤ 4 et en même temps 4 ≤ 4.

Un exemple de relation qui n’est pas antisymétrique : les couples de mots qui ont la même longueur, par exemple (samedi ; soleil). Une telle relation n’est pas antisymétrique, car on trouve un couple de mots qui est dans la relation, dont le couple inversé est aussi dans la relation, et pourtant les deux mots sont différents. Prenons le couple (samedi ; soleil) et son inverse : (soleil ; samedi). Les deux sont manifestement dans notre relation, mais samedi ≠ soleil, donc la relation n’est pas antisymétrique.

Exemple de transitivité

La relation « plus petit que » est transitive. La transitivité nous dit que, si 3 < 4 et en même temps 4 < 5, alors on a forcément 3 < 5. Pour beaucoup de relations, c’est une propriété assez naturelle. Il en va de même pour l’exemple des mots de même longueur. Si (samedi ; soleil) est dans la relation et (soleil ; poteau) aussi, alors les mots (samedi ; poteau) sont eux aussi dans la relation.

La relation « être le père de » n’est pas transitive. Si Hugo est le père de Louis et que Louis est le père de Lucas, alors Hugo n’est pas le père de Lucas, il est son grand-père. De même, la relation « aimer bien quelqu’un » n’est pas transitive. Si j’aime bien Chloé et que Chloé aime bien son mari, cela ne veut pas dire que j’aime bien le mari de Chloé.

On s’interroge aussi sur la transitivité à propos des dés. Supposons la relation « le dé A est meilleur que le dé B » si, avec le dé A, un nombre plus élevé sort plus souvent (avec une probabilité plus grande) qu’avec le dé B. Cette relation est-elle transitive ? L’article sur les dés non transitifs y répond.

Équivalence et ordre

Certains types particuliers de relations binaires ont aussi un nom :

• Une relation d’équivalence est une relation réflexive, symétrique et transitive.
• Une relation d’ordre est une relation réflexive, antisymétrique et transitive.