Relations

Dans ce cours, une relation ${\cal R}$ établit une correspondance entre deux éléments d'un même ensemble. Elle est définie par l'ensemble $E$ sur lequel elle opère, et par son graphe $\Gamma$, qui est un sous-ensemble du produit cartésien $E\times E$. Le fait qu'un couple $(x,y)$ appartienne au graphe $\Gamma$ est noté $x{\cal R} y$ ($x$ est en relation avec $y$). Considérons par exemple la relation «divise»  sur l'ensemble $E=\{1,2,3,4,5,6\}$. Son graphe est :

$$\begin{array}{l} \Gamma = \{ (1,1),(1,2),(1,3),(1,4),(1,5),... ...),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6) \}\;. \end{array}$$

Ses éléments sont visualisés par des flèches sur la figure 4.

Figure: Représentation graphique de la relation «divise»  sur $\{1,2,3,4,5,6\}$.

Les propriétés intéressantes que l'on attend d'une relation sont les suivantes.

Définition 8   On dit qu'une relation ${\cal R}$ sur un ensemble $E$ est :

1. réflexive si tout élément est relié à lui-même
   $$\forall x\in E ,\;x{\cal R} x\;;$$

2. symétrique si $x$ relié à $y$ entraîne que $y$ est relié à $x$
   $$\forall x,y \in E ,\; (x{\cal R} y) \Longrightarrow (y{\cal R}x)\;;$$

3. anti-symétrique si $x$ relié à $y$ et $y$ relié à $x$ entraînent $x=y$
   $$\forall x,y \in E ,\; \Big((x{\cal R} y)\wedge(y{\cal R}x)\Big) \Longrightarrow x=y\;;$$

4. transitive si quand $x$ est relié à $y$ et $y$ à $z$ alors $x$ est relié à $z$
   $$\forall x,y,z\in E ,\;\Big((x{\cal R}y)\wedge(y{\cal R}z)\Big) \Longrightarrow x{\cal R}z\;.$$

Les relations servent à traduire mathématiquement des comparaisons entre éléments d'un même ensemble. Ces comparaisons peuvent être de deux types.

$\bullet$

$x$ a le même ...  que $y$ (la même valeur, la même image par une fonction...) : c'est une relation d'équivalence.

$\bullet$

$x$ est plus ...  que $y$ (plus petit, plus grand, plus tôt...) : c'est une relation d'ordre.

Définition 9   Soit ${\cal R}$ une relation sur un ensemble $E$.

1. On dit que ${\cal R}$ est une relation d'équivalence si elle est à la fois réflexive, symétrique et transitive.
2. On dit que ${\cal R}$ est une relation d'ordre si elle est à la fois réflexive, anti-symétrique et transitive.

Voici des exemples de chacun des deux types de relations. Notre premier exemple de relation d'équivalence est la congruence des entiers. Soit $p$ un entier strictement positif fixé. Définissons la relation ${\cal R}$ sur $\mathbb{N}$ par :

$$\forall m,n\in\mathbb{N}\;,\quad \Big(m{\cal R} n\Big)\;\Longleftrightarrow\; \Big(p \vert (m-n)\Big)$$

On dit que $m$ et $n$ sont congrus modulo $p$ et on note « $m \equiv n$    modulo $p$». Il est facile de vérifier que la congruence modulo $p$ est réflexive, symétrique et transitive. Les nombres pairs sont tous congrus à 0 modulo $2$, les nombres impairs sont congrus à $1$. Vérifiez sur votre agenda, où les jours de l'année sont numérotés, que tous les lundis sont congrus entre eux modulo 7.

Pour notre deuxième exemple de relation d'équivalence, nous allons revenir sur la notion de cardinal d'un ensemble. Soit $E$ un ensemble et ${\cal P}(E)$ l'ensemble de ses parties. Définissons la relation ${\cal R}$ sur ${\cal P}(E)$ qui relie deux parties $A$ et $B$ s'il existe une bijection de $A$ vers $B$. Cette relation est :

$\bullet$

réflexive : l'application identique est une bijection de $E$ vers lui-même,

$\bullet$

symétrique : si $f$ est une bijection de $A$ vers $B$ alors l'application réciproque $f^{-1}$ est une bijection de $B$ vers $A$,

$\bullet$

transitive : si $f$ est une bijection de $A$ vers $B$ et $g$ est une bijection de $B$ vers $C$, alors $g\circ f$ est une bijection de $A$ vers $C$.

Le cardinal est la propriété commune que possèdent deux parties reliées par cette relation d'équivalence. Il caractérise leur classe d'équivalence.

Définition 10   Soit $E$ un ensemble et ${\cal R}$ une relation d'équivalence sur $E$. Pour tout élément $x$ de $E$, la classe d'équivalence de $x$ pour ${\cal R}$ est l'ensemble, noté $\mathfrak{cl}_{\cal R}(x)$ de tous les éléments de $E$ auxquels $x$ est relié.

$$\mathfrak{cl}_{\cal R}(x) = \{ y\in E\;, x{\cal R} y \}\;.$$

L'ensemble des classes d'équivalence s'appelle ensemble quotient de $E$ par ${\cal R}$, et il est noté $E/{\cal R}$.

Théorème 3   Deux classes d'équivalence sont égales ou bien disjointes.

Démonstration : Soient $x$ et $y$ deux éléments de $E$. Ces deux éléments sont reliés ou ils ne le sont pas : nous distinguons les deux cas.

1. Si $x$ est relié à $y$.
   Nous allons démontrer que les deux classes sont égales. Soit $z$ un élément de $\mathfrak{cl}_{\cal R}(y)$. Par définition d'une classe d'équivalence, $y{\cal R} z$. Comme $x{\cal R} y$ et $y{\cal R} z$, d'après la transitivité, $x{\cal R} z$. Nous venons de montrer que tout élément de $\mathfrak{cl}_{\cal R}(y)$ appartient aussi à $\mathfrak{cl}_{\cal R}(x)$. Donc $\mathfrak{cl}_{\cal R}(y)\subset \mathfrak{cl}_{\cal R}(x)$. Comme la relation est symétrique, $y$ est relié à $x$. Donc ce qui précède s'applique en permutant $x$ et $y$. Donc $\mathfrak{cl}_{\cal R}(x)\subset \mathfrak{cl}_{\cal R}(y)$. Comme les deux inclusions sont vraies, les deux classes sont égales.
2. Si $x$ n'est pas relié à $y$.
   Nous allons démontrer que l'intersection des deux classes est vide. D'après la transitivité, pour tout $z\in E$, l'implication suivante est vraie.
   $$\Big( (x{\cal R}z)\wedge(z{\cal R}y)\Big)\Longrightarrow (x{\cal R} y)\;.$$
   Donc si $x{\cal R} y$ est fausse, alors l'une des deux relations $x{\cal R} z$, $z{\cal R} y$ est fausse. Donc un élément $z$ de $E$ ne peut pas appartenir à la fois à $\mathfrak{cl}_{\cal R}(x)$ et à $\mathfrak{cl}_{\cal R}(y)$ : leur intersection est vide.

$\square$

Tout élément de $E$ appartient à sa propre classe d'équivalence car la relation est réflexive, et à aucune autre d'après le théorème précédent. On dit que l'ensemble des classes d'équivalences constitue une partition de $E$ (figure 5).

Définition 11   Soit $E$ un ensemble et $P\subset {\cal P}(E)$ un ensemble de parties de $E$. On dit que $P$ est une partition de $E$ si tout élément de $E$ appartient à un et un seul des éléments de $P$.

Figure 5: Représentation graphique d'une relation d'équivalence. Partition en classes d'équivalence.

Considérons la relation de congruence modulo $p$ sur $\mathbb{Z}$. La classe d'équivalence de 0 est l'ensemble des multiples de $p$, la classe d'équivalence de $1$ est l'ensemble de tous les entiers $n$ tels que $n-1$ est un multiple de $p$... :

$$\forall i\in\{0,\ldots,p-1\}\;,\quad \mathfrak{cl}_{\cal R}(i) = \{i+np\,,\;n\in\mathbb{Z}\}\;.$$

L'ensemble quotient est formé de ces $p$ classes d'équivalence.

Considérons maintenant la relation d'équivalence ${\cal R}$ sur ${\cal P}(\mathbb{N})$ qui relie deux ensembles d'entiers s'il existe une bijection de l'un vers l'autre. La classe d'équivalence de $\{1,\ldots,n\}$ contient toutes les parties de $\mathbb{N}$ qui ont $n$ éléments. Pour $m\neq n$ les classes de $\{1,\ldots,m\}$ et $\{1,\ldots,n\}$ sont disjointes, car il n'existe pas de bijection entre $\{1,\ldots,m\}$ et $\{1,\ldots,n\}$. L'ensemble quotient de ${\cal P}(\mathbb{N})$ par la relation ${\cal R}$ est en bijection avec $\mathbb{N}$.Passons maintenant aux relations d'ordre. L'ordre le plus naturel est celui des nombres entre eux. Observons que «$<$»  et «$>$»  ne sont pas réflexives. Par contre «$\leqslant$»  et «$\geqslant$»  sont bien des relations d'ordre. Si deux éléments sont reliés par une relation d'ordre, on dit qu'ils sont comparables. Si tous les éléments sont comparables deux à deux, on dit que l'ordre est total. C'est le cas pour «$\leqslant$»  et «$\geqslant$»  mais pas pour la relation «divise»  sur $\mathbb{N}$, qui est une relation d'ordre partiel. Si $E$ est un ensemble, l'inclusion est une relation d'ordre partiel sur ${\cal P}(E)$.

Voici un autre exemple. Supposons que $E$ soit un alphabet, pour lequel on a choisi un ordre total, noté $\leqslant$ : l'alphabet latin dont les lettres sont rangées de «A»  à «Z», $E=\{0,1\}$ avec $0\leqslant 1$, etc...  Les éléments de $E^n$ sont des $n$-uplets de lettres, donc des mots de longueur $n$. Comment les ranger ? On peut bien sûr définir une relation d'ordre coordonnée par coordonnée :

$$(x_1,\ldots,x_n){\cal R} (y_1,\ldots,y_n)\;\Longleftrightarrow\; \Big((x_1\leqslant y_1)\wedge \ldots \wedge(x_n\leqslant y_n) \Big)\;.$$

C'est bien une relation d'ordre, mais il n'est que partiel. On obtient un ordre total en donnant la précédence à la première coordonnée, puis à la seconde en cas d'égalité sur la première, etc...

$$\begin{array}{l} (x_1,\ldots,x_n){\cal R} (y_1,\ldots,y_n)\;... ...((x_1=y_1)\wedge\ldots\wedge(x_{n}=y_{n})) \Big)\;. \end{array}$$

L'ordre est maintenant total. Compliqué ? Pas tellement : c'est l'ordre dans lequel les mots sont rangés dans un dictionnaire : on l'appelle ordre lexicographique.