Relations binaires

Il est fréquent d’avoir $E=F$ pour une relation binaire. Dans ce cas on parle de relation binaire sur $E$ (plutôt que de $E$ vers $E$).

• Soit $E$ un ensemble. On considère la relation binaire sur $\mathcal{P}(E)$ donnée par son graphe $G=\{(A,B)\in \mathcal{P}(E{)}^2|A\subset B\}$. On a alors $A\mathcal{R}B⟺A\subset B$. L’inclusion est une relation binaire sur $\mathcal{P}(E)$.
• $E=F=\mathbb{N}$ et $G=\{(e,f)\in {\mathbb{N}}^2|e\equiv f[2]\}$. La relation binaire définie par $G$ est une relation sur $\mathbb{N}$ telle que seuls les entiers de même parité sont en relation.
• Soit $E$ l’ensemble des élèves d’une classe et $F$ l’ensemble des livres d’une bibliothèque. On considère la relation « a lu » : $e\mathcal{R}f$ si et seulement si l’élève $e$ a lu le livre $f$. Chaque élève peut avoir lu plusieurs livres, et chaque livre peut avoir été lu par plusieurs élèves.

On peut reformuler cela en $$\forall x,y\in E,(x\mathcal{R}y)\wedge (y\mathcal{R}x)⟹x=y$$ Cette formulation est souvent plus utile pour montrer qu’une relation est antisymétrique.

On connaît déjà beaucoup de relations d’équivalence :

• L’égalité est une relation d’équivalence.
• La colinéarité est une relation d’équivalence sur tout ensemble de vecteurs non nuls.
• La congruence modulo $n$ où $n$ est un entier naturel non nul.
• La relation de parallélisme notée $\parallel$ sur un ensemble de droites.

• Pour la relation d’égalité sur $\mathbb{R}$, la classe d’équivalence de $3$ est $\{3\}$ car le seul réel égal à $3$ est $3$.
• Pour la colinéarité sur un ensemble de vecteurs non nuls, la classe d’un vecteur est l’ensemble des vecteurs qui lui sont colinéaires.
• Pour la congruence modulo $n$, la classe d’équivalence d’un entier $k$ est l’ensemble des entiers dont le reste par la division euclidienne par $n$ est le même que celui de $k$.
• Pour le parallélisme, la classe d’équivalence d’une droite est l’ensemble des droites qui lui sont parallèles.

On appelle un élément d’une classe donnée un représentant de la classe. Grâce à lui on peut définir sans ambiguïté la classe tout entière. On désigne souvent une classe d’équivalence par son représentant.

• Pour la congruence modulo $n$ sur $\mathbb{Z}$, l’ensemble quotient est $\mathbb{Z}/n\mathbb{Z}=\{\bar{0},\bar{1},\dots ,\overline{n-1}\}$, l’ensemble des $n$ classes de restes possibles.
• Pour la colinéarité sur ${\mathbb{R}}^2\setminus \{0\}$, l’ensemble quotient est l’ensemble des directions du plan.

On passe de $E$ à $E/\mathcal{R}$ en « oubliant » les différences entre éléments équivalents. Cette construction est fondamentale en algèbre.

• La relation « inférieur ou égal » notée $⩽$ est une relation d’ordre sur $\mathbb{R}$.
• La relation d’inclusion $\subset$ est une relation d’ordre sur les parties d’un ensemble.
• La relation de divisibilité $|$ est une relation d’ordre sur ${\mathbb{N}}^{\ast }$.

On note communément $\preccurlyeq$ une relation d’ordre quelconque.

• La relation « inférieur strict » notée $<$ est une relation d’ordre strict sur $\mathbb{R}$.
• La relation d’inclusion stricte $⊊$ est une relation d’ordre strict sur les parties d’un ensemble.

La relation « supérieur ou égal » notée $⩾$ est la relation d’ordre inverse de $⩽$ sur $\mathbb{R}$.

• Pour parler d’ordre inverse il faut avoir préalablement défini une relation d’ordre.
• Une relation d’ordre inverse est elle-même une relation d’ordre.
• On peut aussi définir une relation d’ordre strict inverse (comme $>$) en combinant les deux définitions précédentes.

• La relation $⩽$ sur $\mathbb{R}$ est un ordre total : deux réels sont toujours comparables.
• La relation d’inclusion $\subset$ sur $\mathcal{P}(E)$ est un ordre partiel : $\{1\}$ et $\{2\}$ ne sont pas comparables.
• La relation de divisibilité sur ${\mathbb{N}}^{\ast }$ est un ordre partiel : $2$ et $3$ ne sont pas comparables.