Relations binaires et leurs propriétés

Une relation binaire d'un ensemble E vers un ensemble F est une partie du produit cartésien E × F : elle dit quels éléments de E sont liés à quels éléments de F. On écrit x R y quand le couple (x ; y) fait partie de la relation. Ce chapitre montre comment représenter une relation (liste de couples, diagramme, matrice, graphe) et comment vérifier ses quatre propriétés : réflexivité, symétrie, antisymétrie et transitivité.

C'est quoi une relation binaire ?

Le mot « binaire » veut dire que la relation lie les éléments deux à deux. Quelques exemples :

• « a accès à » lie des utilisateurs à des ressources ;
• « est le responsable direct de » lie des salariés entre eux ;
• « divise » lie des entiers entre eux ;
• « est connecté à » lie les équipements d'un réseau ;
• « dépend de » lie les paquets d'un logiciel.

Formellement, une relation R de E vers F est un ensemble de couples, une partie de E × F. E est l'ensemble de départ, F l'ensemble d'arrivée. Quand E = F, on parle de relation sur E, partie de E².

Exemple : une matrice d'habilitations. Trois utilisateurs U = {ana ; bilal ; chloé} et trois ressources partagées F = {compta ; rh ; intranet}. Ana accède à la comptabilité et à l'intranet, Bilal aux ressources humaines et à l'intranet, Chloé seulement à l'intranet. La relation « a accès à » est la partie de U × F :

R = {(ana ; compta) ; (ana ; intranet) ; (bilal ; rh) ; (bilal ; intranet) ; (chloé ; intranet)}

Sur les 3 × 3 = 9 couples de U × F, 5 sont en relation. On écrit ana R compta, mais pas chloé R rh.

C'est exactement la matrice d'habilitations qu'on te demande d'établir en cybersécurité, et une table d'association SQL comme acces(id_utilisateur, id_ressource) : chaque ligne est un couple de la relation.

Représenter une relation

La même relation peut s'écrire de quatre façons. Il faut savoir passer de l'une à l'autre, car les sujets choisissent souvent la représentation qui n'est pas la plus pratique pour la question.

1. La liste des couples, comme ci-dessus.

2. Le diagramme sagittal (du latin sagitta, la flèche) : les éléments de E à gauche, ceux de F à droite, une flèche de x vers y chaque fois que x R y.

3. La matrice (ou tableau booléen) : une ligne par élément de E, une colonne par élément de F, 1 dans la case (x ; y) si x R y, 0 sinon.

4. Le graphe orienté, pour une relation sur un seul ensemble E : un point (un sommet) par élément de E, une flèche (un arc) de x vers y si x R y. Quand x R x, l'arc revient sur son sommet : c'est une boucle. Un graphe orienté et une relation binaire sur un ensemble fini, c'est la même chose ; tout le vocabulaire du cours sur les graphes s'applique.

Exemple : la relation « divise » sur E = {1 ; 2 ; 3 ; 4}. x R y si x divise y, c'est-à-dire si y est un multiple de x.

R = {(1 ; 1) ; (1 ; 2) ; (1 ; 3) ; (1 ; 4) ; (2 ; 2) ; (2 ; 4) ; (3 ; 3) ; (4 ; 4)}

Relation réciproque

La réciproque de R, notée R⁻¹, est la relation obtenue en retournant tous les couples : y R⁻¹ x si et seulement si x R y. La réciproque de « est le responsable direct de » est « a pour responsable direct » ; celle de « divise » est « est un multiple de ».

Sa matrice est la transposée de celle de R (les lignes deviennent les colonnes) ; dans son graphe, toutes les flèches changent de sens.

Les quatre propriétés d'une relation sur E

Pour une relation R sur un ensemble E, on étudie quatre propriétés. Chacune a une traduction sur le graphe et sur la matrice, souvent plus rapide à vérifier que la définition.

Réflexive

R est réflexive si tout élément est en relation avec lui-même :

pour tout x ∈ E, x R x.

• Graphe : une boucle sur chaque sommet.
• Matrice : que des 1 sur la diagonale.

« Divise » est réflexive (tout nombre se divise lui-même). « Est strictement inférieur à » ne l'est pas (on n'a jamais x < x).

Symétrique

R est symétrique si, chaque fois que x est en relation avec y, y est en relation avec x :

pour tous x, y ∈ E, si x R y, alors y R x.

• Graphe : chaque arc entre deux sommets différents a son arc retour.
• Matrice : symétrique par rapport à la diagonale (la case (x ; y) est égale à la case (y ; x)).

« Est dans le même VLAN que » est symétrique. « Divise » ne l'est pas : 1 divise 2, mais 2 ne divise pas 1.

Antisymétrique

R est antisymétrique si deux éléments différents ne sont jamais en relation dans les deux sens :

pour tous x, y ∈ E, si x R y et y R x, alors x = y.

• Graphe : jamais deux arcs opposés entre deux sommets différents (les boucles sont permises).
• Matrice : en dehors de la diagonale, deux cases symétriques ne valent jamais 1 toutes les deux.

« Divise » sur ℕ* est antisymétrique : si x divise y et y divise x, alors x = y. « ≤ » aussi.

Transitive

R est transitive si, chaque fois que x est en relation avec y et y avec z, x est en relation avec z :

pour tous x, y, z ∈ E, si x R y et y R z, alors x R z.

• Graphe : chaque chemin de deux arcs x → y → z a son raccourci x → z.
• Matrice : chaque 1 du produit booléen M × M est déjà un 1 de M (produit booléen : on calcule M × M comme un produit de matrices, en remplaçant + par OU et × par ET ; voir le produit de matrices).

« Divise » est transitive : si x divise y et y divise z, alors x divise z. « Est le responsable direct de » ne l'est pas : le responsable de mon responsable n'est pas mon responsable direct.

Méthode : étudier une relation donnée par une liste de couples

Sur un ensemble fini, on vérifie les propriétés dans cet ordre.

1. Réflexive ? Pour chaque élément x de E, cherche (x ; x). Un seul manque, et la relation n'est pas réflexive.
2. Symétrique ? Pour chaque couple (x ; y) avec x ≠ y, cherche (y ; x).
3. Antisymétrique ? Cherche une paire (x ; y) et (y ; x) avec x ≠ y. Si tu en trouves une, la relation n'est pas antisymétrique.
4. Transitive ? Pour chaque couple (x ; y), regarde tous les couples qui partent de y, (y ; z), et vérifie que (x ; z) est présent. C'est la vérification la plus longue : procède élément par élément pour ne rien sauter.

Exemple corrigé : la relation « divise » sur E = {1 ; 2 ; 3 ; 4}.

1. Réflexive : (1 ; 1), (2 ; 2), (3 ; 3), (4 ; 4) sont présents. Oui.
2. Symétrique : (1 ; 2) est présent mais pas (2 ; 1). Non.
3. Antisymétrique : les couples hors diagonale sont (1 ; 2), (1 ; 3), (1 ; 4) et (2 ; 4) ; aucun n'a son couple retourné dans R. Oui.
4. Transitive : les seuls enchaînements de deux couples distincts hors diagonale sont (1 ; 2) puis (2 ; 4) ; on vérifie que (1 ; 4) est présent. Les enchaînements avec une boucle, comme (1 ; 2) puis (2 ; 2), redonnent un couple déjà présent. Oui.

Réflexive, antisymétrique et transitive : c'est une relation d'ordre, l'objet du chapitre 5.

Les propriétés des relations courantes

Deux remarques sur ce tableau :

• « x < y » est antisymétrique parce que la condition « x < y et y < x » n'est jamais remplie : la propriété est vraie « par défaut ».
• « x ≠ y » n'est pas transitive : 1 ≠ 2 et 2 ≠ 1, mais 1 ≠ 1 est faux.

La fermeture transitive

Quand une relation n'est pas transitive, on peut lui ajouter les couples qui manquent jusqu'à ce qu'elle le devienne : la plus petite relation transitive qui contient R s'appelle sa fermeture transitive. Sur le graphe, on ajoute un arc x → z chaque fois qu'il existe un chemin de x à z.

Exemple : les dépendances d'un logiciel. Une application app dépend de lib1 et de lib4 ; lib1 dépend de lib2, qui dépend de lib3. La relation « dépend directement de » vaut :

D = {(app ; lib1) ; (app ; lib4) ; (lib1 ; lib2) ; (lib2 ; lib3)}

Sa fermeture transitive, « dépend directement ou indirectement de », ajoute trois couples : (app ; lib2), (app ; lib3) et (lib1 ; lib3). L'ensemble des paquets à installer avec app est donc {lib1 ; lib2 ; lib3 ; lib4}. C'est ce que calcule un gestionnaire de paquets comme apt ou npm. Le sujet E3 de 2026 demandait justement de compter les arcs à ajouter à un graphe pour obtenir sa fermeture transitive (corrigé du sujet 2026) ; la méthode systématique, par les puissances de la matrice d'adjacence, est dans le cours sur les graphes.

Exercices

Exercice 1 sur 4 Étudier une relation donnée en liste Réussi À revoir

Sur E = {1 ; 2 ; 3}, on définit R = {(1 ; 1) ; (2 ; 2) ; (3 ; 3) ; (1 ; 2) ; (2 ; 1) ; (2 ; 3) ; (3 ; 2)}.

1. Écris la matrice de R (éléments dans l'ordre 1, 2, 3).
2. R est-elle réflexive ? symétrique ? antisymétrique ? transitive ? Justifie chaque réponse.

Voir la réponseMasquer la réponse de l'exercice 1

1. Matrice (ligne x, colonne y) :

R	1	2	3
1	1	1	0
2	1	1	1
3	0	1	1

2. Réflexive : la diagonale ne contient que des 1. Oui.

   Symétrique : la matrice est symétrique par rapport à la diagonale ; (1 ; 2) et (2 ; 1) sont présents, (2 ; 3) et (3 ; 2) aussi. Oui.

   Antisymétrique : 1 R 2 et 2 R 1 avec 1 ≠ 2. Non.

   Transitive : 1 R 2 et 2 R 3, mais (1 ; 3) n'est pas dans R. Non.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 4 Lire les propriétés sur une matrice Réussi À revoir

Une relation R sur E = {a ; b ; c ; d} a pour matrice (lignes et colonnes dans l'ordre a, b, c, d) :

R	a	b	c	d
a	1	1	1	1
b	0	1	0	1
c	0	0	1	1
d	0	0	0	1

1. Écris R sous forme de liste de couples.
2. Étudie ses quatre propriétés.
3. Écris la matrice de la relation réciproque R⁻¹.

Voir la réponseMasquer la réponse de l'exercice 2

1. R = {(a ; a) ; (a ; b) ; (a ; c) ; (a ; d) ; (b ; b) ; (b ; d) ; (c ; c) ; (c ; d) ; (d ; d)}.
2. Réflexive : diagonale pleine de 1. Oui. Symétrique : a R b mais pas b R a. Non. Antisymétrique : tous les 1 hors diagonale sont au-dessus d'elle, et toutes les cases sous la diagonale valent 0, donc jamais deux cases symétriques à 1. Oui. Transitive : les enchaînements hors diagonale sont a → b → d, a → c → d ; (a ; d) est présent dans les deux cas. Oui. R est donc une relation d'ordre (b et c ne sont pas comparables : ni b R c, ni c R b).
3. C'est la transposée :

R⁻¹	a	b	c	d
a	1	0	0	0
b	1	1	0	0
c	1	0	1	0
d	1	1	1	1

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 4 Relations sur des nombres Réussi À revoir

Étudie la réflexivité, la symétrie, l'antisymétrie et la transitivité des relations suivantes, en justifiant.

1. Sur ℤ : x R y si et seulement si x − y est pair.
2. Sur ℝ : x S y si et seulement si |x − y| ≤ 1.

Voir la réponseMasquer la réponse de l'exercice 3

1. Réflexive : x − x = 0, qui est pair. Oui.

Symétrique : si x − y est pair, alors y − x = −(x − y) est pair aussi. Oui.

Antisymétrique : 0 R 2 (0 − 2 = −2 est pair) et 2 R 0, avec 0 ≠ 2. Non.

Transitive : si x − y = 2k et y − z = 2k′, alors x − z = (x − y) + (y − z) = 2(k + k′), qui est pair. Oui.

R est réflexive, symétrique et transitive : c'est une relation d'équivalence (chapitre 5).

2. Réflexive : |x − x| = 0 ≤ 1. Oui.

Symétrique : |y − x| = |x − y|. Oui.

Antisymétrique : 0 S 0,5 et 0,5 S 0, avec 0 ≠ 0,5. Non.

Transitive : 0 S 1 (|0 − 1| = 1) et 1 S 2, mais |0 − 2| = 2 > 1, donc 0 S 2 est faux. Non. « Être proche de » n'est pas transitif : c'est pour cela qu'on ne peut pas regrouper des valeurs « proches » en classes bien séparées.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 4 Fermeture transitive d'un réseau de dépendances Réussi À revoir

Un service web W appelle une API A et un service d'authentification S. L'API A interroge une base de données B. Le service S interroge un annuaire LDAP L, qui s'appuie sur le serveur DNS D.

1. Écris la relation « appelle directement » sous forme de liste de couples sur E = {W ; A ; S ; B ; L ; D}.
2. Quels couples faut-il ajouter pour obtenir sa fermeture transitive ?
3. Le serveur DNS D tombe en panne. Quels services sont touchés, directement ou non ?

Voir la réponseMasquer la réponse de l'exercice 4

1. R = {(W ; A) ; (W ; S) ; (A ; B) ; (S ; L) ; (L ; D)}.
2. On suit chaque chemin de longueur 2 ou plus : W → A → B donne (W ; B) ; W → S → L donne (W ; L) ; W → S → L → D donne (W ; D) ; S → L → D donne (S ; D). Il faut ajouter 4 couples : (W ; B), (W ; L), (W ; D) et (S ; D).
3. Les éléments x tels que (x ; D) est dans la fermeture transitive : L, S et W. La panne du DNS touche l'annuaire, le service d'authentification et le service web ; l'API et la base de données ne dépendent pas du DNS dans ce modèle.

Tu avais trouvé ?

Oui, j'avais bonPas encore