Relations d'équivalence et d'ordre

Soit $E$ un ensemble. Une relation binaire $\mathcal{R}$ sur $E$ est la donnée, pour chaque couple $(x, y) \in E^2$, du fait que $x$ est ou non en relation avec $y$. Formellement, c'est une partie $\Gamma$ de $E \times E$, appelée son graphe, et l'on note $x \mathrel{\mathcal{R}} y$ pour $(x, y) \in \Gamma$. L'ordre des deux lettres compte : $x \mathrel{\mathcal{R}} y$ et $y \mathrel{\mathcal{R}} x$ sont deux affirmations différentes. Les relations de référence du chapitre sont l'égalité sur $E$, l'inégalité $\leq$ sur $\mathbb{R}$, l'inclusion sur $\mathcal{P}(E)$ et la divisibilité sur $\mathbb{N}$. Le produit cartésien $E \times E$ et l'ensemble des parties $\mathcal{P}(E)$ sont ceux du thème Ensembles et opérations ensemblistes.

Soit $\mathcal{R}$ une relation binaire sur $E$. Elle est réflexive si $\forall x \in E,\ x \mathrel{\mathcal{R}} x$ ; symétrique si $\forall (x, y) \in E^2,\ x \mathrel{\mathcal{R}} y \implies y \mathrel{\mathcal{R}} x$ ; antisymétrique si $\forall (x, y) \in E^2,\ \big(x \mathrel{\mathcal{R}} y \text{ et } y \mathrel{\mathcal{R}} x\big) \implies x = y$ ; transitive si $\forall (x, y, z) \in E^3,\ \big(x \mathrel{\mathcal{R}} y \text{ et } y \mathrel{\mathcal{R}} z\big) \implies x \mathrel{\mathcal{R}} z$. En français : tout élément est en relation avec lui-même ; si l'un est en relation avec l'autre, l'autre l'est avec l'un ; deux éléments en relation dans les deux sens sont égaux ; la relation se propage de proche en proche. Chacune de ces quatre propriétés commence par un « pour tout » : on la démontre en fixant des éléments quelconques, et on la réfute en exhibant un couple ou un triplet (voir le thème Réfuter par un contre-exemple du bloc Fondamental).

Une relation binaire se note $\mathcal{R}$, $\sim$, $\equiv$, $\leq$ ou $\preceq$ selon ce qu'elle est, et l'on écrit toujours le symbole entre les deux éléments : $x \mathrel{\mathcal{R}} y$, jamais $\mathcal{R}(x, y)$ en cours de rédaction. Son graphe est la partie de $E \times E$ formée des couples en relation ; deux relations de même graphe sont égales. On réserve $\sim$ aux relations d'équivalence (réflexive, symétrique, transitive) et $\preceq$ aux relations d'ordre (réflexive, antisymétrique, transitive) : le symbole choisi annonce au lecteur les propriétés déjà démontrées. Une relation réflexive et transitive s'appelle un préordre : on ne lui demande rien de plus, si bien qu'une relation d'ordre en est un. La divisibilité sur $\mathbb{Z}$ est un préordre qui n'est pas un ordre, l'antisymétrie lui manquant.

Quand l'utiliser : dès qu'une des quatre propriétés semble en défaut, et systématiquement avant de se lancer dans une démonstration qui échouera. Une propriété universelle se réfute par un seul contre-exemple, et l'énoncé attend qu'il soit écrit.
1) Écrire la propriété avec ses quantificateurs, puis sa négation (voir le thème Nier une proposition du bloc Fondamental) : la négation de « $\forall (x, y) \in E^2,\ A(x,y) \implies B(x,y)$ » est « $\exists (x, y) \in E^2,\ A(x,y)$ et non $B(x,y)$ ».
2) Lire ce que doit fournir le contre-exemple : un couple pour la symétrie et l'antisymétrie, un triplet pour la transitivité, un seul élément pour la réflexivité.
3) Chercher au brouillon sur les valeurs les plus simples : $0$, $1$, $2$, l'ensemble vide, un singleton, deux éléments distincts.
4) Écrire le contre-exemple en entier, avec la vérification de chaque relation annoncée. Pour la relation définie sur $\mathbb{R}$ par « $x \mathrel{\mathcal{R}} y$ si et seulement si $|x - y| \leq 1$ », cela donne : « Prenons $x = 0$ et $y = 1$. On a $x \mathrel{\mathcal{R}} y$ car $|0 - 1| = 1 \leq 1$, et $y \mathrel{\mathcal{R}} x$ car $|1 - 0| = 1 \leq 1$, et pourtant $0 \neq 1$. »
5) Conclure par la phrase négative : « Donc $\mathcal{R}$ n'est pas antisymétrique. » Ne jamais s'arrêter sur le calcul : c'est la conclusion qui répond à la question.
6) Vérifier chaque relation annoncée avant de conclure : un contre-exemple dont une des relations est fausse ne réfute rien.

On définit sur $\mathbb{R}$ la relation $\mathcal{R}$ par : $x \mathrel{\mathcal{R}} y$ si et seulement si $|x - y| \leq 1$. Déterminer lesquelles des quatre propriétés elle vérifie.
Réflexivité. Soit $x \in \mathbb{R}$. On a $|x - x| = 0 \leq 1$, donc $x \mathrel{\mathcal{R}} x$. La relation $\mathcal{R}$ est donc réflexive.
Symétrie. Soient $x, y \in \mathbb{R}$ tels que $x \mathrel{\mathcal{R}} y$, c'est-à-dire $|x - y| \leq 1$.
Or $|y - x| = |-(x - y)| = |x - y|$, donc $|y - x| \leq 1$, c'est-à-dire $y \mathrel{\mathcal{R}} x$. La relation $\mathcal{R}$ est donc symétrique.
Antisymétrie. Prenons $x = 0$ et $y = 1$.
On a $|0 - 1| = 1 \leq 1$, donc $x \mathrel{\mathcal{R}} y$, et $|1 - 0| = 1 \leq 1$, donc $y \mathrel{\mathcal{R}} x$, et pourtant $0 \neq 1$.
La relation $\mathcal{R}$ n'est donc pas antisymétrique.
Transitivité. Prenons $x = 0$, $y = 1$ et $z = 2$.
On a $|0 - 1| = 1 \leq 1$, donc $x \mathrel{\mathcal{R}} y$, et $|1 - 2| = 1 \leq 1$, donc $y \mathrel{\mathcal{R}} z$.
Or $|0 - 2| = 2 > 1$, donc $x \mathrel{\mathcal{R}} z$ est faux. La relation $\mathcal{R}$ n'est donc pas transitive.
Conclusion : $\mathcal{R}$ est réflexive et symétrique, mais ni antisymétrique ni transitive ; ce n'est donc ni une relation d'équivalence, ni une relation d'ordre.
À retenir : une propriété universelle se démontre en fixant des éléments quelconques par « Soient », et se réfute en exhibant des valeurs numériques dont on vérifie chaque relation annoncée.

Ligne fautive : « Soit $x \in E$. Comme $x \mathrel{\mathcal{R}} y$, la symétrie donne $y \mathrel{\mathcal{R}} x$, puis la transitivité donne $x \mathrel{\mathcal{R}} x$ : la relation est donc réflexive. »
La lettre $y$ n'a été introduite par rien : le raisonnement suppose en secret qu'il existe, pour chaque $x$, un élément $y$ en relation avec $x$, ce que rien ne garantit (voir le thème Introduire les objets du bloc Fondamental). Contre-exemple : sur $E = \{1, 2\}$, la relation de graphe $\Gamma = \{(1, 1)\}$ est symétrique (le seul couple du graphe a ses deux coordonnées égales) et transitive (le seul enchaînement possible est $1 \mathrel{\mathcal{R}} 1$ et $1 \mathrel{\mathcal{R}} 1$), mais $2 \mathrel{\mathcal{R}} 2$ est faux : elle n'est pas réflexive.
Version correcte : les trois propriétés se démontrent séparément, et la réflexivité s'écrit « Soit $x \in E$ », suivi d'une vérification qui ne fait intervenir que $x$ : « $|x - x| = 0 \leq 1$, donc $x \mathrel{\mathcal{R}} x$. »

Ligne fautive : « La relation $\leq$ n'est pas symétrique, donc elle est antisymétrique. »
Les deux mots ne sont pas les contraires l'un de l'autre : « symétrique » dit que les deux sens vont toujours ensemble, « antisymétrique » dit que, quand ils vont ensemble, les deux éléments sont égaux. Une relation peut être les deux à la fois : l'égalité sur $\mathbb{R}$ est symétrique et antisymétrique. Une relation peut n'être ni l'un ni l'autre : sur $E = \{1, 2, 3\}$, la relation de graphe $\Gamma = \{(1, 2), (2, 1), (1, 3)\}$ n'est pas symétrique, car $1 \mathrel{\mathcal{R}} 3$ et $3 \mathrel{\mathcal{R}} 1$ est faux, et n'est pas antisymétrique, car $1 \mathrel{\mathcal{R}} 2$ et $2 \mathrel{\mathcal{R}} 1$ avec $1 \neq 2$.
Version correcte : pour établir l'antisymétrie, on écrit « Soient $x, y \in E$ tels que $x \mathrel{\mathcal{R}} y$ et $y \mathrel{\mathcal{R}} x$ » et l'on démontre $x = y$ ; pour la réfuter, on exhibe deux éléments distincts en relation dans les deux sens.

Une relation d'équivalence sur $E$ est une relation binaire réflexive, symétrique et transitive. On la note en général $\sim$, et $x \sim y$ se lit « $x$ est équivalent à $y$ ». En français, une telle relation dit que deux éléments partagent un même caractère : même reste, même image, même direction, même valeur d'un invariant. Les trois propriétés se démontrent séparément, dans cet ordre, et aucune ne se déduit des autres.

Les relations d'équivalence rencontrées en première année se ramènent presque toutes à « avoir même quelque chose ». L'égalité sur $E$ est la plus fine : chaque classe est un singleton. La relation pleine, pour laquelle tous les éléments sont équivalents, est la plus grossière : il n'y a qu'une classe, $E$ tout entier. Entre les deux : la congruence modulo $n$ sur $\mathbb{Z}$, la congruence modulo un réel $a$ sur $\mathbb{R}$, la relation « même image par $f$ » pour une application $f$ de source $E$, le parallélisme des droites du plan, et « même signe » sur $\mathbb{R}^*$.

Soient $\sim$ une relation d'équivalence sur $E$ et $x \in E$. La classe d'équivalence de $x$ est la partie de $E$ définie par $\mathrm{cl}(x) = \{\, y \in E \mid x \sim y \,\}$ : c'est l'ensemble des éléments équivalents à $x$. Tout élément $y$ de $\mathrm{cl}(x)$ en est un représentant, et la symétrie assure que $\{\, y \in E \mid x \sim y \,\} = \{\, y \in E \mid y \sim x \,\}$, si bien que le sens dans lequel on écrit la relation est sans importance. On rencontre aussi les notations $[x]$, $\overline{x}$ et $\dot{x}$ ; le site écrit $\mathrm{cl}(x)$. Une classe est une partie de $E$ : elle appartient à $\mathcal{P}(E)$, et ses éléments, eux, appartiennent à $E$.

Propriété : soit $\sim$ une relation d'équivalence sur $E$. Pour tous $x, y \in E$ : (i) $x \in \mathrm{cl}(x)$, donc $\mathrm{cl}(x) \neq \varnothing$ ; (ii) $x \sim y \iff \mathrm{cl}(x) = \mathrm{cl}(y)$ ; (iii) si $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \varnothing$, alors $\mathrm{cl}(x) = \mathrm{cl}(y)$, autrement dit deux classes sont égales ou disjointes. Les trois hypothèses servent : la réflexivité pour (i) et pour le sens réciproque de (ii), la symétrie et la transitivité pour le sens direct de (ii). Le point (ii) est le plus utilisé : il permet de remplacer partout une égalité de classes par une relation entre représentants, et inversement.

Soit $\sim$ une relation d'équivalence sur un ensemble $E$. Montrer que pour tous $x, y \in E$ : $x \sim y$ si et seulement si $\mathrm{cl}(x) = \mathrm{cl}(y)$. En déduire que deux classes qui ont un élément commun sont égales.
Soient $x, y \in E$.
Supposons $x \sim y$. Montrons $\mathrm{cl}(x) \subset \mathrm{cl}(y)$.
Soit $z \in \mathrm{cl}(x)$, c'est-à-dire $x \sim z$.
Comme $x \sim y$, la symétrie donne $y \sim x$, puis la transitivité appliquée à $y \sim x$ et $x \sim z$ donne $y \sim z$, c'est-à-dire $z \in \mathrm{cl}(y)$.
Ceci valant pour tout $z \in \mathrm{cl}(x)$, on a $\mathrm{cl}(x) \subset \mathrm{cl}(y)$.
Comme $x \sim y$ entraîne $y \sim x$ par symétrie, le raisonnement précédent, appliqué au couple $(y, x)$, donne $\mathrm{cl}(y) \subset \mathrm{cl}(x)$.
Par double inclusion, $\mathrm{cl}(x) = \mathrm{cl}(y)$.
Réciproquement, supposons $\mathrm{cl}(x) = \mathrm{cl}(y)$.
Par réflexivité, $y \sim y$, donc $y \in \mathrm{cl}(y) = \mathrm{cl}(x)$, c'est-à-dire $x \sim y$.
Les deux implications sont établies, donc $x \sim y$ si et seulement si $\mathrm{cl}(x) = \mathrm{cl}(y)$.
Soient enfin $x, y \in E$ tels que $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \varnothing$, et soit $z$ un élément de cette intersection.
De $z \in \mathrm{cl}(x)$ on tire $x \sim z$, et de $z \in \mathrm{cl}(y)$ on tire $y \sim z$, donc $z \sim y$ par symétrie.
La transitivité appliquée à $x \sim z$ et $z \sim y$ donne $x \sim y$, donc $\mathrm{cl}(x) = \mathrm{cl}(y)$ d'après ce qui précède.
À retenir : une égalité d'ensembles se démontre par double inclusion, en fixant un élément quelconque du premier ; et la symétrie de la relation permet d'échanger les rôles de $x$ et de $y$ plutôt que de recopier le raisonnement.

Rappel du thème Ensembles et opérations ensemblistes : une partition de $E$ est un ensemble $\mathcal{A}$ de parties de $E$ toutes non vides, deux à deux disjointes, et dont la réunion vaut $E$ ; ses éléments s'appellent ses parts, et ce sont des parties de $E$, jamais des parties de $\mathcal{A}$. Théorème : si $\sim$ est une relation d'équivalence sur $E$, alors l'ensemble de ses classes $\{\, \mathrm{cl}(x) \mid x \in E \,\}$ est une partition de $E$. Autrement dit, chaque élément de $E$ appartient à une classe et à une seule : celle-ci range les éléments de $E$ en paquets sans reste ni recouvrement. C'est le théorème central du thème : il transforme une relation en un découpage.

Soit $\sim$ une relation d'équivalence sur un ensemble $E$. Montrer que l'ensemble $\mathcal{A} = \{\, \mathrm{cl}(x) \mid x \in E \,\}$ de ses classes est une partition de $E$.
Les parts de $\mathcal{A}$ sont non vides. Soit $C \in \mathcal{A}$ : il existe $x \in E$ tel que $C = \mathrm{cl}(x)$.
Par réflexivité, $x \sim x$, donc $x \in \mathrm{cl}(x) = C$, et $C$ est non vide.
Les parts de $\mathcal{A}$ sont deux à deux disjointes. Soient $C, C' \in \mathcal{A}$ telles que $C \cap C' \neq \varnothing$, et montrons $C = C'$.
Il existe $x, y \in E$ tels que $C = \mathrm{cl}(x)$ et $C' = \mathrm{cl}(y)$.
Comme $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \varnothing$, la propriété des classes donne $\mathrm{cl}(x) = \mathrm{cl}(y)$, c'est-à-dire $C = C'$.
Deux parts de $\mathcal{A}$ sont donc égales ou disjointes.
La réunion des parts de $\mathcal{A}$ vaut $E$. Chaque classe est une partie de $E$, donc cette réunion est incluse dans $E$.
Réciproquement, soit $x \in E$. On a $x \in \mathrm{cl}(x)$ et $\mathrm{cl}(x) \in \mathcal{A}$, donc $x$ appartient à la réunion.
Par double inclusion, la réunion des parts de $\mathcal{A}$ vaut $E$.
Les trois conditions sont vérifiées, donc $\mathcal{A}$ est une partition de $E$.
À retenir : les trois points à vérifier sont exactement les trois conditions de la définition d'une partition, et chacun d'eux consomme une propriété de la relation, la réflexivité pour le recouvrement, la symétrie et la transitivité pour la disjonction.

Propriété : soit $\mathcal{A}$ une partition de $E$. La relation $\sim$ définie par « $x \sim y$ si et seulement s'il existe $A \in \mathcal{A}$ telle que $x \in A$ et $y \in A$ » est une relation d'équivalence sur $E$, et ses classes sont exactement les parts de $\mathcal{A}$. Jointe au théorème précédent, cette propriété établit une bijection entre les relations d'équivalence sur $E$ et les partitions de $E$ : ce sont deux façons de décrire le même objet. En pratique, on passe librement de l'une à l'autre, selon que l'énoncé parle d'un critère (« avoir même reste ») ou d'un découpage (« les paquets »).

Soit $\mathcal{A}$ une partition d'un ensemble $E$. On définit sur $E$ la relation $\sim$ par : $x \sim y$ si et seulement s'il existe $A \in \mathcal{A}$ telle que $x \in A$ et $y \in A$. Montrer que $\sim$ est une relation d'équivalence dont les classes sont les parts de $\mathcal{A}$.
Réflexivité. Soit $x \in E$. Comme la réunion des parts de $\mathcal{A}$ vaut $E$, il existe $A \in \mathcal{A}$ telle que $x \in A$. Cette partie $A$ contient $x$ et $x$, donc $x \sim x$.
Symétrie. Soient $x, y \in E$ tels que $x \sim y$ : il existe $A \in \mathcal{A}$ telle que $x \in A$ et $y \in A$. La même partie $A$ convient pour le couple $(y, x)$, donc $y \sim x$.
Transitivité. Soient $x, y, z \in E$ tels que $x \sim y$ et $y \sim z$.
Il existe $A \in \mathcal{A}$ telle que $x \in A$ et $y \in A$, et $B \in \mathcal{A}$ telle que $y \in B$ et $z \in B$.
Alors $y \in A \cap B$, donc $A \cap B \neq \varnothing$ ; or deux parts distinctes d'une partition sont disjointes, donc $A = B$.
Ainsi $x \in A$ et $z \in A$, donc $x \sim z$.
La relation $\sim$ est donc une relation d'équivalence.
Classes. Soit $x \in E$, et soit $A$ la part de $\mathcal{A}$ qui contient $x$ : elle existe car la réunion vaut $E$, et elle est unique car deux parts distinctes sont disjointes.
Montrons $\mathrm{cl}(x) = A$ par double inclusion.
Soit $y \in \mathrm{cl}(x)$, c'est-à-dire $x \sim y$ : il existe $B \in \mathcal{A}$ telle que $x \in B$ et $y \in B$. Comme $x \in A \cap B$, on a $A = B$, donc $y \in A$.
Réciproquement, soit $y \in A$. La partie $A$ contient $x$ et $y$, donc $x \sim y$, c'est-à-dire $y \in \mathrm{cl}(x)$.
Donc $\mathrm{cl}(x) = A$. Toute classe est ainsi une part de $\mathcal{A}$, et toute part $A$ de $\mathcal{A}$ est une classe : elle est non vide, donc contient un élément $x$, et $A = \mathrm{cl}(x)$.
À retenir : une partition et une relation d'équivalence sont le même objet vu de deux côtés, et c'est la disjonction des parts qui fournit la transitivité.

Quand l'utiliser : l'énoncé définit une relation par une égalité, une différence, une divisibilité ou une condition symétrique en $x$ et $y$, et demande de l'étudier, puis souvent de décrire l'ensemble de ses classes.
1) Annoncer les trois vérifications, et les mener séparément, chacune avec sa phrase d'ouverture : « Soit $x \in E$. » pour la réflexivité, « Soient $x, y \in E$ tels que $x \sim y$. » pour la symétrie, « Soient $x, y, z \in E$ tels que $x \sim y$ et $y \sim z$. » pour la transitivité.
2) Dans chaque cas, traduire la relation par sa définition, calculer, puis retraduire pour conclure : c'est l'aller-retour entre la relation et la condition qui la définit.
3) Si la relation s'écrit $f(x) = f(y)$ pour une application $f$ que l'on reconnaît, citer la propriété générale : elle donne les trois points d'un coup, et les classes sans calcul.
4) Conclure : « La relation $\sim$ est réflexive, symétrique et transitive : c'est une relation d'équivalence. »
5) Pour les classes, fixer $x \in E$ et raisonner par équivalences sur la condition $y \in \mathrm{cl}(x)$ : « Soit $y \in E$. On a $y \in \mathrm{cl}(x)$ si et seulement si … si et seulement si … », jusqu'à une description explicite de l'ensemble.
6) Écrire la classe en extension ou avec un paramètre, par exemple $\mathrm{cl}(x) = \{x,\ 1 - x\}$ ou $\mathrm{cl}(x) = x + a\mathbb{Z}$, et signaler les classes exceptionnelles (celles qui ont un seul élément).
7) Si l'énoncé le demande, donner un système de représentants : une partie de $E$ qui rencontre chaque classe en exactement un point ; on la décrit, puis on prouve l'existence et l'unicité du représentant.

On définit sur $\mathbb{R}$ la relation $\mathcal{R}$ par : $x \mathrel{\mathcal{R}} y$ si et seulement si $x^2 - x = y^2 - y$. Montrer que $\mathcal{R}$ est une relation d'équivalence, décrire ses classes, et donner un système de représentants.
Réflexivité. Soit $x \in \mathbb{R}$. On a $x^2 - x = x^2 - x$, donc $x \mathrel{\mathcal{R}} x$.
Symétrie. Soient $x, y \in \mathbb{R}$ tels que $x \mathrel{\mathcal{R}} y$, c'est-à-dire $x^2 - x = y^2 - y$. Cette égalité de réels se lit aussi $y^2 - y = x^2 - x$, donc $y \mathrel{\mathcal{R}} x$.
Transitivité. Soient $x, y, z \in \mathbb{R}$ tels que $x \mathrel{\mathcal{R}} y$ et $y \mathrel{\mathcal{R}} z$, c'est-à-dire $x^2 - x = y^2 - y$ et $y^2 - y = z^2 - z$. Par transitivité de l'égalité, $x^2 - x = z^2 - z$, donc $x \mathrel{\mathcal{R}} z$.
La relation $\mathcal{R}$ est réflexive, symétrique et transitive : c'est une relation d'équivalence.
Classes. Soit $x \in \mathbb{R}$. Soit $y \in \mathbb{R}$. On a les équivalences suivantes :
$y \in \mathrm{cl}(x) \iff x^2 - x = y^2 - y \iff y^2 - x^2 - (y - x) = 0$
$\iff (y - x)(y + x) - (y - x) = 0 \iff (y - x)(y + x - 1) = 0$
$\iff y = x \text{ ou } y = 1 - x$.
Donc $\mathrm{cl}(x) = \{\, x,\ 1 - x \,\}$.
Cette classe a deux éléments lorsque $x \neq 1 - x$, c'est-à-dire lorsque $x \neq \frac{1}{2}$, et un seul lorsque $x = \frac{1}{2}$, auquel cas $\mathrm{cl}\left(\frac{1}{2}\right) = \left\{\frac{1}{2}\right\}$.
Système de représentants. Montrons que l'intervalle $I = \left[\frac{1}{2},\, +\infty\right[$ rencontre chaque classe en exactement un point.
Existence : soit $x \in \mathbb{R}$. Comme $x + (1 - x) = 1$, l'un au moins des deux réels $x$ et $1 - x$ est supérieur ou égal à $\frac{1}{2}$, et il appartient à $\mathrm{cl}(x) \cap I$.
Unicité : soient $u$ et $v$ deux éléments de $\mathrm{cl}(x) \cap I$ et supposons $u \neq v$. D'après la description des classes, $\{u, v\} = \{x, 1 - x\}$ avec $v = 1 - u$. De $u \geq \frac{1}{2}$ et $1 - u \geq \frac{1}{2}$ on tire $u \geq \frac{1}{2}$ et $u \leq \frac{1}{2}$, donc $u = \frac{1}{2}$, puis $v = 1 - u = \frac{1}{2} = u$, ce qui contredit $u \neq v$.
Donc $\mathrm{cl}(x) \cap I$ a exactement un élément : $I$ est un système de représentants de $\mathcal{R}$.
À retenir : on décrit une classe en raisonnant par équivalences sur $y \in \mathrm{cl}(x)$, et une factorisation suffit souvent à lire les classes ; un système de représentants se justifie par une existence et une unicité, jamais par un dessin.

Propriété : soient $E$ et $F$ deux ensembles et $f : E \to F$ une application. La relation $\mathcal{R}_f$ définie sur $E$ par « $x \mathrel{\mathcal{R}_f} y$ si et seulement si $f(x) = f(y)$ » est une relation d'équivalence, et pour tout $x \in E$, $\mathrm{cl}(x) = f^{-1}\big(\{f(x)\}\big)$. Rappel du thème Applications : $f^{-1}(B) = \{\, x \in E \mid f(x) \in B \,\}$ est l'ensemble des antécédents des éléments de $B$, et cette écriture ne suppose pas $f$ bijective. Les classes de $\mathcal{R}_f$ sont donc les images réciproques des singletons atteints, c'est-à-dire les $f^{-1}(\{b\})$ pour $b \in f(E)$.

Soient $E$ et $F$ deux ensembles et $f : E \to F$. On définit sur $E$ la relation $\mathcal{R}_f$ par : $x \mathrel{\mathcal{R}_f} y$ si et seulement si $f(x) = f(y)$. Montrer que $\mathcal{R}_f$ est une relation d'équivalence et décrire ses classes. Traiter le cas $E = F = \mathbb{R}$ et $f(x) = x^2$.
Réflexivité. Soit $x \in E$. On a $f(x) = f(x)$, donc $x \mathrel{\mathcal{R}_f} x$.
Symétrie. Soient $x, y \in E$ tels que $f(x) = f(y)$. Alors $f(y) = f(x)$, donc $y \mathrel{\mathcal{R}_f} x$.
Transitivité. Soient $x, y, z \in E$ tels que $f(x) = f(y)$ et $f(y) = f(z)$. Par transitivité de l'égalité, $f(x) = f(z)$, donc $x \mathrel{\mathcal{R}_f} z$.
La relation $\mathcal{R}_f$ est donc une relation d'équivalence.
Classes. Soit $x \in E$. Soit $y \in E$. On a :
$y \in \mathrm{cl}(x) \iff f(x) = f(y) \iff f(y) \in \{f(x)\} \iff y \in f^{-1}\big(\{f(x)\}\big)$.
Donc $\mathrm{cl}(x) = f^{-1}\big(\{f(x)\}\big)$.
Cas particulier. Prenons $E = F = \mathbb{R}$ et $f(x) = x^2$. Soient $x, y \in \mathbb{R}$ :
$y \in \mathrm{cl}(x) \iff y^2 = x^2 \iff y^2 - x^2 = 0 \iff (y - x)(y + x) = 0 \iff y = x \text{ ou } y = -x$.
Donc $\mathrm{cl}(x) = \{\, x,\ -x \,\}$, classe à deux éléments si $x \neq 0$, et $\mathrm{cl}(0) = \{0\}$.
Les classes sont donc les paires $\{x, -x\}$, et $\mathbb{R}_+$ est un système de représentants : tout réel $x$ vérifie $|x| \in \mathrm{cl}(x) \cap \mathbb{R}_+$, et si $u$ et $-u$ sont tous deux positifs, alors $u = 0$.
À retenir : « avoir même image » est l'exemple universel de relation d'équivalence, et sa classe s'écrit sans calcul comme une image réciproque de singleton ; le calcul ne sert qu'à rendre cette image réciproque explicite.

Ligne fautive : « Les classes de la relation « même image par $f$ » sont les $f^{-1}(\{b\})$ pour $b \in F$, donc l'ensemble des classes est en bijection avec $F$. »
C'est faux dès que $f$ n'est pas surjective : une classe contient toujours son représentant, donc n'est jamais vide, alors que $f^{-1}(\{b\})$ est vide pour tout $b$ non atteint. Contre-exemple : pour $f : \mathbb{R} \to \mathbb{R}$, $x \mapsto x^2$, on a $f^{-1}(\{-1\}) = \varnothing$, et aucun réel $x$ ne vérifie $\mathrm{cl}(x) = \varnothing$ : la description des classes est donc fausse. La conclusion l'est aussi, et un exemple fini suffit à le voir : pour $E = \{1, 2\}$, $F = \{a, b, c\}$ et $f$ constante égale à $a$, les deux éléments de $E$ ont même image, il n'y a donc qu'une seule classe, alors que $F$ compte trois éléments ; aucune bijection ne va de l'ensemble des classes sur $F$.
Version correcte : « Les classes de $\mathcal{R}_f$ sont les $f^{-1}(\{b\})$ pour $b \in f(E)$, et l'ensemble de ces classes est en bijection avec l'image $f(E)$. » La même vigilance vaut pour les partitions : aucune part d'une partition n'est vide, et l'ensemble vide n'est jamais une classe.

Soit $a \in \mathbb{R}$. La congruence modulo $a$ est la relation définie sur $\mathbb{R}$ par : $x \equiv y \ [a]$ si et seulement s'il existe $k \in \mathbb{Z}$ tel que $x - y = ka$. On lit « $x$ est congru à $y$ modulo $a$ », et l'on note aussi $x \equiv y \pmod a$. C'est l'exemple type de relation d'équivalence : ses classes sont les ensembles $x + a\mathbb{Z} = \{\, x + ka \mid k \in \mathbb{Z} \,\}$, obtenus en translatant $x$ par tous les multiples entiers de $a$. Pour $a = 0$ elle se réduit à l'égalité ; pour $a$ entier et $x, y$ entiers, c'est la congruence des entiers ; pour $a = 2\pi$, c'est la relation qui identifie deux mesures d'un même angle.

Soit $a$ un réel strictement positif. On définit sur $\mathbb{R}$ la relation $\equiv$ par : $x \equiv y \ [a]$ si et seulement s'il existe $k \in \mathbb{Z}$ tel que $x - y = ka$. Montrer que c'est une relation d'équivalence, décrire ses classes, et montrer que $[0, a[$ est un système de représentants.
Réflexivité. Soit $x \in \mathbb{R}$. On a $x - x = 0 = 0 \times a$ avec $0 \in \mathbb{Z}$, donc $x \equiv x \ [a]$.
Symétrie. Soient $x, y \in \mathbb{R}$ tels que $x \equiv y \ [a]$ : il existe $k \in \mathbb{Z}$ tel que $x - y = ka$.
Alors $y - x = (-k)a$, et $-k \in \mathbb{Z}$, donc $y \equiv x \ [a]$.
Transitivité. Soient $x, y, z \in \mathbb{R}$ tels que $x \equiv y \ [a]$ et $y \equiv z \ [a]$ : il existe $k, k' \in \mathbb{Z}$ tels que $x - y = ka$ et $y - z = k'a$.
Alors $x - z = (x - y) + (y - z) = (k + k')a$, et $k + k' \in \mathbb{Z}$, donc $x \equiv z \ [a]$.
La relation $\equiv$ est donc une relation d'équivalence.
Classes. Soient $x \in \mathbb{R}$ et $y \in \mathbb{R}$. On a :
$y \in \mathrm{cl}(x) \iff \exists k \in \mathbb{Z},\ x - y = ka \iff \exists k \in \mathbb{Z},\ y = x - ka$.
Lorsque $k$ parcourt $\mathbb{Z}$, l'entier $-k$ parcourt aussi $\mathbb{Z}$, donc $\mathrm{cl}(x) = \{\, x + ka \mid k \in \mathbb{Z} \,\} = x + a\mathbb{Z}$.
Système de représentants. Soit $x \in \mathbb{R}$.
Existence : posons $q = \left\lfloor \frac{x}{a} \right\rfloor$ et $r = x - qa$. Par définition de la partie entière, $q \leq \frac{x}{a} < q + 1$, et comme $a > 0$, en multipliant par $a$ on obtient $qa \leq x < qa + a$, donc $0 \leq r < a$.
De plus $x - r = qa$ avec $q \in \mathbb{Z}$, donc $x \equiv r \ [a]$ et $r \in \mathrm{cl}(x) \cap [0, a[$.
Unicité : soient $r, r' \in \mathrm{cl}(x) \cap [0, a[$. Alors $r \equiv r' \ [a]$ par symétrie et transitivité, donc il existe $k \in \mathbb{Z}$ tel que $r - r' = ka$.
Or $0 \leq r < a$ et $0 \leq r' < a$ donnent $-a < r - r' < a$, donc $-1 < k < 1$, et $k \in \mathbb{Z}$ entraîne $k = 0$, c'est-à-dire $r = r'$.
Chaque classe rencontre donc $[0, a[$ en exactement un point : $[0, a[$ est un système de représentants de la congruence modulo $a$.
À retenir : les trois vérifications d'une congruence se font en produisant l'entier $k$ voulu ($0$, $-k$, $k + k'$), et le représentant privilégié s'obtient par une partie entière, dont l'encadrement fournit à la fois l'existence et l'unicité.

Soit $\sim$ une relation d'équivalence sur $E$. L'ensemble quotient de $E$ par $\sim$, noté $E / \sim$, est l'ensemble des classes d'équivalence : $E / \sim \; = \{\, \mathrm{cl}(x) \mid x \in E \,\}$. C'est une partie de $\mathcal{P}(E)$ : ses éléments sont des parties de $E$, pas des éléments de $E$. La surjection canonique (ou projection canonique) est l'application $\pi : E \to E / \sim$ qui à $x$ associe sa classe $\mathrm{cl}(x)$. Passer au quotient, c'est décider de ne plus distinguer deux éléments équivalents : dans $E / \sim$, $x$ et $y$ équivalents deviennent un seul et même objet.

Propriété : soit $\sim$ une relation d'équivalence sur $E$, et $\pi : E \to E / \sim$ la surjection canonique. Alors $\pi$ est surjective, et pour tous $x, y \in E$, $\pi(x) = \pi(y) \iff x \sim y$. Autrement dit, la relation « avoir même image par $\pi$ » est exactement $\sim$ : toute relation d'équivalence est donc de la forme $\mathcal{R}_f$ pour une application $f$ bien choisie. La surjectivité est immédiate, puisque toute classe s'écrit $\mathrm{cl}(x) = \pi(x)$ ; l'équivalence, elle, est la propriété des classes. Un système de représentants est une partie $S$ de $E$ telle que la restriction de $\pi$ à $S$ soit bijective : choisir un représentant par classe, c'est construire un inverse à droite de $\pi$ (thème Applications).