Classes d’équivalence modulo ρ
Soit un ensemble \( X \) muni d’une relation d’équivalence \( \rho \). La classe d’équivalence d’un élément \( \beta \) est l’ensemble \( [\beta] \) de tous les éléments \( x \in X \) tels que \( x\rho\beta \) : $$ [\beta]_\rho = \{ x \in X \:\: | \:\: x\rho\beta \} $$
L’élément \( a \) est appelé le représentant de la classe.
Chaque classe d’équivalence contient au moins un élément : son représentant.
Exemple
Considérons la relation d’équivalence \( \rho \) définie sur l’ensemble des entiers ℤ, selon laquelle deux éléments \( a \) et \( b \) sont liés si, et seulement si, \( a^2 = b^2 \).
$$ [a] = \{ b \in X \:\: | \:\: a^2 = b^2 \} $$
Par exemple, une classe d’équivalence est :
$$ [a] = \{ +2, -2 \} $$
puisque \( +2 \) et \( -2 \) ont tous deux pour carré le nombre 4.
De manière générale, chaque classe \( [a] \) contient deux éléments :
$$ [a] = \{ +a, -a \} $$
sauf dans le cas \( a = 0 \), où la classe est réduite à :
$$ [0] = \{ 0 \} $$
Exemple concret de classe d’équivalence
Considérons l’ensemble des parties de \( A = \{1, 2, 3\} \) :
$$ P(A) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \} $$
Les éléments de \( P(A) \) sont tous les sous-ensembles de \( A \).
On définit une relation d’équivalence \( \rho \) sur \( P(A) \) telle que deux sous-ensembles sont équivalents s’ils ont la même cardinalité, c’est-à-dire le même nombre d’éléments.
La classe d’équivalence d’un élément \( a \in P(A) \) s’écrit alors :
$$ [a]_\rho = \{ x \in P(A) \ | \ x\rho a \} $$
Dans ce contexte, les classes d’équivalence sont les suivantes :
La classe de \( a = \emptyset \) est le singleton contenant l’ensemble vide :
$$ [\emptyset]_\rho = \{ \emptyset \} $$
Remarque : Une classe n’est jamais vide. Celle-ci contient bien un élément - l’ensemble vide - qui appartient à \( P(A) \). Comme indiqué précédemment, toute classe d’équivalence contient au moins son représentant.
La classe de \( a = \{1\} \) contient tous les singletons de \( A \) :
$$ [{1}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$
Les classes de \( \{2\} \) et \( \{3\} \) sont identiques :
$$ [{2}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$
$$ [{3}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$
La classe de \( \{1,2\} \) regroupe les sous-ensembles à deux éléments :
$$ [{1,2}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
Il en va de même pour \( \{1,3\} \) et \( \{2,3\} \) :
$$ [{1,3}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
$$ [{2,3}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
Enfin, la classe de \( \{1,2,3\} \) contient uniquement cet ensemble :
$$ [{1,2,3}]_\rho = \{ \{1,2,3\} \} $$
Remarque : Comme dans l’exemple précédent, toute classe d’équivalence contient au moins son représentant.
Propriétés des classes d’équivalence
Soient \( A \) un ensemble et \( \rho \) une relation d’équivalence sur \( A \). Pour tous \( a, b \in A \), les propriétés suivantes sont vérifiées :
$$ [a] \ne \emptyset $$ $$ [a] = [b]_\rho \Leftrightarrow a\rho b $$ $$ [a] \ne [b]_\rho \Leftrightarrow [a] \cap [b] = \emptyset $$
Démonstration
Première propriété
Une classe d’équivalence n’est jamais vide :
$$ [a] \ne \emptyset $$
Cela découle de la réflexivité de la relation, puisque tout élément \( a \in A \) est relié à lui-même :
$$ \forall a \in A,\ (a\rho a) \Rightarrow [a] \ne \emptyset $$
Ainsi, chaque classe contient au moins un élément : son représentant.
Deuxième propriété
Deux classes d’équivalence sont égales si, et seulement si, leurs représentants sont équivalents :
$$ [a] = [b]_\rho \Leftrightarrow a\rho b $$
Cette équivalence logique se démontre dans les deux sens :
A] Sens direct (suffisance)
Si \( [a] = [b] \), alors \( a \in [a] \), donc \( a \in [b] \), ce qui implique \( a\rho b \).
B] Sens réciproque (nécessité)
Supposons que \( a\rho b \). Pour montrer que \( [a] = [b] \), il suffit de prouver la double inclusion :
$$ [a] \subseteq [b] \quad \text{et} \quad [b] \subseteq [a] $$
Première inclusion : Soit \( x \in [a] \), donc \( x\rho a \). Comme \( a\rho b \), la transitivité donne \( x\rho b \), donc \( x \in [b] \).
Deuxième inclusion : Soit \( x \in [b] \), donc \( x\rho b \). Comme \( a\rho b \), on a \( b\rho a \) (symétrie), et donc \( x\rho a \) par transitivité, donc \( x \in [a] \).
Conclusion :
$$ [a] = [b] $$
Troisième propriété
Deux classes d’équivalence distinctes sont disjointes :
$$ [a] \ne [b] \Leftrightarrow [a] \cap [b] = \emptyset $$
Implication directe : Si \( [a] \cap [b] \ne \emptyset \), alors il existe un élément \( c \) tel que \( c \in [a] \cap [b] \). On a donc \( c\rho a \) et \( c\rho b \), ce qui implique \( [a] = [c] = [b] \), en contradiction avec l’hypothèse \( [a] \ne [b] \).
Donc :
$$ [a] \ne [b] \Rightarrow [a] \cap [b] = \emptyset $$
Implication réciproque : Si \( [a] = [b] \), alors :
$$ [a] \cap [b] = [a] \cap [a] = [a] \ne \emptyset $$
ce qui contredit l’hypothèse \( [a] \cap [b] = \emptyset \). Par conséquent :
$$ [a] \cap [b] = \emptyset \Rightarrow [a] \ne [b] $$
