Relation

Une relation entre deux ensembles $A$ et $B$ est une loi qui associe à chaque élément de $A$ zéro, un ou plusieurs éléments de $B$. Dans ce sens, c’est une généralisation du concept de Fonction.

Définition et notation

Formellement, une relation $\mathcal{R}$ entre deux ensembles $A$ et $B$ est un sous-ensemble du produit cartésien $A\times B$. Pour des ensembles finis, une relation peut être représentée à l’aide de diagrammes de Venn en reliant les éléments en relation, comme dans la figure.

Si $\mathcal{R}\subset A\times B$ est une relation et si $a\in A$ et $b\in B$ sont deux éléments, on écrit $a\mathcal{R}b$ si $a$ et $b$ sont en relation, c’est à dire si $(a,b)\in\mathcal{R}$.

Lorsque pour tout $a\in A$ il existe au plus un $b\in B$ tel que $a\mathcal{R}b$, la relation correspond au graphe d’une fonction partielle; lorsque pour tout $a\in A$ il existe exactement un $b\in B$ tel que $a\mathcal{R}b$, la relation correspond au graphe d’une fonction (totale). Dans ce cas on dit que $\mathcal{R}$ est fonctionnelle ou simplement qu’elle est une fonction.

Réciproque

La réciproque (parfois appelée inverse) d’une relation $\mathcal{R}\subset A\times B$ est la relation

$$\mathcal{R}^c = \{(b,a)\in B\times A \;\vert\; (a,b)\in A\times B\}.$$

Lorsque $\mathcal{R}$ est le graphe d’une fonction, sa réciproque est le graphe de la fonction inverse.

Relations sur un ensemble

Une relation $\mathcal{R}\subset A\times A$ est aussi appelée une relation sur $A$. On classifie les relations sur un ensemble d’après leurs propriétés. Une relation $\mathcal{R}\subset A\times A$ est dite:

Réflexive

si pour tout $a\in A$ on a $a\mathcal{R}a$; Symétrique

si pour tout $a,b\in A$ on a $a\mathcal{R}b \Leftrightarrow b\mathcal{R}a$; Transitive

si pour tout $a,b,c\in A$ on a $(a\mathcal{R}b \,\wedge\, b\mathcal{R}c) \Rightarrow a\mathcal{R}c$; Totale

si pour tout $a,b\in A$ on a $a\mathcal{R}b \,\vee\, b\mathcal{R}a$; Asymétrique

si pour tout $a,b\in A$ on a $\neg(a\mathcal{R}b \,\wedge\, b\mathcal{R}a)$; Antisymétrique

si pour tout $a,b\in A$ on a $(a\mathcal{R}b \,\wedge\, b\mathcal{R}a) \Rightarrow a=b$.

Une relation qui est à la fois réflexive, symétrique et transitive est appelée une Équivalence.

Une relation qui est à la fois réflexive, antisymétrique et transitive est appelée un Ordre (partiel); lorsque elle est aussi totale elle est appelée un ordre total.

Une relation qui est à la fois transitive et asymétrique est appelée un ordre strict.

Excercice: montrer qu’une relation transitive et non réflexive est nécessairement asymétrique.

Exemples

• La relation “est ami de” de Facebook est une relation symétrique.
• La relation d’égalité $a=b$ (aussi dite relation idéntité) est refléxive, symétrique et transitive. Elle est le graphe de la fonction identité.
• La relation sur les naturels $a|b$ ($a$ divise $b$) est réflexive, transitive et antisymètrique, mais pas totale. Elle forme donc un ordre partiel.
• La relation sur les entiers $a< b$ est transitive et asymétrique, elle forme donc un ordre strict.
• La relation sur les entiers $a\le b$ est un ordre total.
• La relation sur les entiers $a=b \,\mathrm{mod}\, n$ (i.e. le reste de la division Euclidienne de $a$ et de $b$ par $n$ est le même) est une équivalence.
• La relation $A\subset B$ sur les sous-ensembles d’un univers $U$ est un ordre partiel.

Exercice: vérifier les propriétés susmentionnées.