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

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

appartienne au graphe $\Gamma$ est noté $x{\cal R} y$ (

est en relation avec

). Considérons par exemple la relation «divise» sur l'ensemble $E=\{1,2,3,4,5,6\}$ . Son graphe est :

$\begin{displaymath} \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}\end{displaymath}$

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\}$ .
$\includegraphics[width=7cm]{divise}$

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 est :

réflexive si tout élément est relié à lui-même

$\displaystyle \forall x\in E ,\;x{\cal R} x\;;$
symétrique si relié à entraîne que est relié à

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

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

$\displaystyle \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$: a le même ... que (la même valeur, la même image par une fonction...) : c'est une relation d'équivalence.
$\bullet$: est plus ... que (plus petit, plus grand, plus tôt...) : c'est une relation d'ordre.

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

On dit que ${\cal R}$ est une relation d'équivalence si elle est à la fois réflexive, symétrique et transitive.
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

un entier strictement positif fixé. Définissons la relation ${\cal R}$ sur $\mathbb{N}$ par :

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

On dit que

sont congrus modulo

et on note « $m \equiv n$ modulo

». Il est facile de vérifier que la congruence modulo

est réflexive, symétrique et transitive. Les nombres pairs sont tous congrus à 0 modulo

, les nombres impairs sont congrus à

. 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 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 et s'il existe une bijection de vers . Cette relation est :

$\bullet$: réflexive : l'application identique est une bijection de vers lui-même,
$\bullet$: symétrique : si est une bijection de vers alors l'application réciproque $f^{-1}$ est une bijection de vers ,
$\bullet$: transitive : si est une bijection de vers et est une bijection de vers , alors $g\circ f$ est une bijection de vers .

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 un ensemble et ${\cal R}$ une relation d'équivalence sur . Pour tout élément de , la classe d'équivalence de pour ${\cal R}$ est l'ensemble, noté $\mathfrak{cl}_{\cal R}(x)$ de tous les éléments de auxquels est relié.

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

L'ensemble des classes d'équivalence s'appelle ensemble quotient de 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

deux éléments de

. Ces deux éléments sont reliés ou ils ne le sont pas : nous distinguons les deux cas.

Si est relié à .
Nous allons démontrer que les deux classes sont égales. Soit 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, est relié à . Donc ce qui précède s'applique en permutant et . Donc $\mathfrak{cl}_{\cal R}(x)\subset \mathfrak{cl}_{\cal R}(y)$ . Comme les deux inclusions sont vraies, les deux classes sont égales.
Si n'est pas relié à .
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.

$\displaystyle \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 de 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 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 (figure 5).

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

**Figure 5:** Représentation graphique d'une relation d'équivalence. Partition en classes d'équivalence.
$\includegraphics[width=8cm, height=5cm]{relequiv}$

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

$\displaystyle \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

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 é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 est un ensemble, l'inclusion est une relation d'ordre partiel sur ${\cal P}(E)$ .

Voici un autre exemple. Supposons que 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 sont des -uplets de lettres, donc des mots de longueur . Comment les ranger ? On peut bien sûr définir une relation d'ordre coordonnée par coordonnée :

$\displaystyle (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{displaymath} \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}\end{displaymath}$

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.