Relation.md

layout	title
post	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.