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 \mathcal{R}\}.\]

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

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

Fork me on GitHub