relation binaire

Prenons les nombres 1, 2 et 3 d’un côté, puis 2, 3, 4 et 6 de l’autre. On peut demander, pour chaque paire placée dans cet ordre, si le premier nombre divise le second. La réponse est toujours oui ou non. Une relation binaire rassemble exactement les paires pour lesquelles la règle choisie répond oui. L’ordre compte : la première place et la seconde n’ont pas le même rôle.

Soient E et F deux ensembles, éventuellement égaux. Une relation binaire de E vers F est le choix de certains couples ordonnés (x, y), où le premier élément x appartient à E et le second élément y appartient à F. La relation est notée R. Dire que x est en relation avec y s’écrit x R y.

Le produit cartésien E × F contient tous les couples possibles dans cet ordre. Le graphe de R est le sous-ensemble formé des seuls couples retenus :

Cette description par un sous-ensemble et la règle qui attribue vrai ou faux à chaque couple donnent la même information. Elle ne suppose ni que chaque x soit relié à un y, ni qu’il le soit à un seul.

Pour définir une relation binaire de E vers F, il faut pouvoir décider, pour tout couple (x, y) appartenant à E × F, si l’affirmation x R y est vraie. Le graphe de la relation est alors l’ensemble des couples qui rendent cette affirmation vraie. Réciproquement, tout sous-ensemble de E × F définit une relation binaire : ses éléments sont exactement les couples reliés.

Le domaine de départ E, le domaine d’arrivée F et le critère vrai ou faux doivent être fixés. Dans un couple (x, y), x doit appartenir à E et y à F ; cette appartenance se vérifie avant d’appliquer le critère. Les deux ensembles peuvent toutefois être identiques.

Avec E = {1, 2, 3} et F = {2, 3, 4, 6}, le couple (4, 6) ne peut pas appartenir au graphe, même si 4 et 6 sont des nombres : 4 n’appartient pas à E. Il faut agrandir E ou définir une autre relation sur des ensembles adaptés.

On prend E = {1, 2, 3}, F = {2, 3, 4, 6} et la relation R définie par « x divise y ». Les données sont donc deux ensembles ordonnés par leur rôle et un critère de divisibilité.

1. Pour x = 1, les quatre valeurs de F conviennent : (1, 2), (1, 3), (1, 4) et (1, 6).
2. Pour x = 2, on retient (2, 2), (2, 4) et (2, 6).
3. Pour x = 3, on retient (3, 3) et (3, 6).

Le graphe contient donc neuf couples. Le schéma relie chaque élément de E aux éléments de F qu’il divise. Pour contrôler le résultat, on compte 4 + 3 + 2 = 9 liaisons et l’on vérifie, par exemple, que (2, 3) est absent puisque 2 ne divise pas 3.

Pour comparer des nombres, une relation encode une question oui/non comme « x divise y » ou « x est inférieur à y ». On choisit la relation plutôt qu’une simple liste lorsque l’ordre des deux valeurs porte le sens.

Pour décrire des correspondances entre deux collections, le graphe de la relation conserve chaque association admise. Une fonction est préférable seulement si chaque élément du premier ensemble doit avoir exactement une image.

Pour étudier des propriétés comme la transitivité, on travaille sur un même ensemble et l’on teste des chaînes de couples. Le sous-ensemble de E × E permet alors de contrôler précisément quels enchaînements sont autorisés.

Relation binaire et fonction. Une fonction de E vers F associe exactement une image dans F à chaque élément de E. Une relation binaire n’impose rien de tel. Dans l’exemple, 1 est relié à quatre valeurs : R n’est donc pas une fonction de E vers F.

Relation et produit cartésien. E × F contient tous les couples possibles, tandis que le graphe d’une relation n’en retient qu’un sous-ensemble. Ici, E × F compte 3 × 4 = 12 couples, mais la relation de divisibilité n’en retient que neuf.

Ensemble vide. Si E ou F est vide, E × F est vide : la seule relation possible a donc un graphe vide. Il ne faut pas inventer de couple pour rendre la relation visible.

Aucun couple ou tous les couples. Le graphe vide et le graphe E × F sont deux relations parfaitement valides. L’absence totale ou l’universalité des liaisons n’empêche pas qu’il s’agisse d’une relation binaire.

Sens du couple. De x R y, on ne peut pas conclure y R x. Dans l’exemple, 2 divise 6, mais inverser les rôles exigerait d’abord que 6 appartienne à E et 2 à F, puis que 6 divise 2.

Mot « graphe ». Ici, le graphe est d’abord un ensemble de couples ordonnés. Un dessin à points et liaisons n’est qu’une représentation de ce sous-ensemble ; il faut conserver les deux ensembles et le sens des couples.

Le Produit cartésien précise comment se forme l’ensemble de tous les couples dont une relation sélectionne certains éléments.

La relation transitive introduit une propriété importante lorsque la relation porte sur un même ensemble et que deux couples peuvent s’enchaîner.