Relation d’équivalence

Une relation d’équivalence est une relation binaire sur un ensemble qui est réflexive, symétrique et transitive.

Motivation

Une relation d’équivalence est en quelque sorte un affaiblissement de la relation d’égalité. On peut toujours décider si deux éléments d’un ensemble sont identiques, c’est-à-dire si a = b. Mais il est parfois utile de savoir si deux éléments sont seulement semblables, pas forcément identiques. Autrement dit, s’ils ont en commun une propriété essentielle. Par exemple, on peut considérer que deux livres sont semblables s’ils sont du même genre, ou, avec une équivalence : deux livres sont équivalents s’ils sont du même genre.

Qu’attendrait-on d’une telle équivalence ? Prenons un autre exemple. Deux mots sont semblables/équivalents s’ils ont la même longueur.

On s’attendrait sans doute à ce que, si l’on mesure la ressemblance de deux mots identiques, on trouve qu’ils sont semblables. Donc tout mot doit être semblable/équivalent à lui-même. En langage des relations : une relation d’équivalence doit être réflexive.

Ensuite, si le mot « fleur » est semblable/équivalent au mot « lampe », alors on s’attend bien sûr à ce que le mot « lampe » soit équivalent au mot « fleur ». En d’autres termes, l’ordre n’a pas d’importance. En langage des relations : une relation d’équivalence doit être symétrique.

Enfin, si le mot « mort » est semblable/équivalent au mot « loup » et que le mot « loup » est équivalent au mot « pied », alors on s’attend à ce que les mots « mort » et « pied » soient eux aussi équivalents. Une relation d’équivalence doit donc aussi être transitive.

On n’attend rien d’autre d’une équivalence.

Exemples

Voici d’autres exemples d’équivalences :

• Habiter dans la même ville. Hugo habite sûrement dans la même ville que Hugo (réflexivité). Si Hugo habite dans la même ville que Lucas, alors Lucas habite aussi dans la même ville que Hugo (symétrie). Et si Lucas habite dans la même ville que Louis, alors Hugo habite aussi dans la même ville que Louis (transitivité).
• Être né la même année. Léa est sûrement née la même année que Léa (réflexivité). Si Léa et Emma sont nées la même année, alors Emma et Léa sont nées la même année (symétrie). Et si Emma et Chloé sont nées la même année, alors Léa et Chloé sont nées la même année (transitivité).
• (a ; b) ∈ R si et seulement si a − b est un nombre pair ; a, b sont des entiers relatifs. Réflexivité : a − a = 0, et zéro est un nombre pair. Symétrie : posons c = a − b. Alors b − a = −(a − b) = −c. Si c est pair, alors −c doit être pair aussi. Transitivité : posons p = a − b et q = b − c. Nous savons que p et q sont tous deux pairs. Nous devons maintenant démontrer que a − c est un nombre pair. Dans cette égalité, remplaçons c par c = b − q : a − (b − q), ce qui est égal à a − b + q. D’après les hypothèses, a − b est un nombre pair. Si l’on ajoute à un nombre pair un autre nombre pair q, on obtient de nouveau un nombre pair.
• L’égalité. L’égalité est une équivalence, et c’est en même temps la plus petite équivalence sur n’importe quel ensemble M.

Équivalence triviale

Prenons un ensemble non vide M. Quelle est la plus petite équivalence possible R sur l’ensemble M ? La plus petite partie possible du produit cartésien M × M est l’ensemble vide ∅. L’ensemble vide remplit-il les conditions d’une équivalence ?

Cette relation est sûrement symétrique : comme la relation R n’a aucun élément, la condition de symétrie est automatiquement et trivialement remplie. De même pour la transitivité. Le problème vient de la réflexivité. La définition dit que, pour tous les éléments x de l’ensemble M, on a (x ; x) ∈ R. Est-ce rempli ? L’ensemble M est non vide, donc il contient un élément, par exemple q. Le couple (q ; q) est-il dans la relation R ? Non. La relation R n’est donc pas réflexive.

Quelle est la plus petite relation réflexive ? La relation d’égalité. La relation R doit contenir au minimum les couples (x ; x) pour tous les éléments de M. C’est précisément la relation identité. Cette relation est-elle symétrique ? On voit facilement que oui. De même, on voit facilement qu’elle est aussi transitive. La plus petite relation d’équivalence sur l’ensemble M est donc la relation identité, que nous notons id_M, et elle contient les couples (x ; x) pour tous les x ∈ M.

Quelle est la plus grande équivalence possible sur l’ensemble M ? La plus grande partie est l’ensemble M × M tout entier. Remplit-il les conditions d’une équivalence ? On voit sans doute trivialement que oui.

Classe d’équivalence

Toute équivalence partage l’ensemble M en une famille d’ensembles disjoints, que l’on appelle les classes d’équivalence.

Prenons l’ensemble M de tous les mots et l’équivalence R « avoir la même longueur ». Donc (a ; b) ∈ R si et seulement si les mots a et b ont la même longueur. Cette équivalence partage l’ensemble des mots en plusieurs ensembles plus petits, qui contiendront toujours des mots de même longueur. On peut distinguer les différentes classes d’équivalence par un indice, qui indiquera en même temps la longueur des mots de l’ensemble considéré :

• M₁ = {a ; y ; …}
• M₂ = {le ; de ; un ; tu ; …}
• M₃ = {les ; mer ; sur ; pas ; …}
• M₄ = {mort ; parc ; lent ; nuit ; …}
• …

Remarque deux choses : 1) les ensembles sont deux à deux disjoints, ils n’ont aucun élément commun. 2) tous les éléments de chaque ensemble sont équivalents entre eux. Tous les mots de l’ensemble M₃ sont équivalents entre eux, car tous les mots ont une longueur de trois, donc la même longueur, ce qui est la condition de l’équivalence.

Chaque élément définit d’ailleurs de façon unique sa classe d’équivalence. On le note habituellement M[x], où x ∈ M. Si nous écrivons M[les], nous définissons sans ambiguïté la classe d’équivalence que nous avons déjà notée M₃.

Comment trouve-t-on la classe d’équivalence d’un élément x ∈ M donné ? On parcourt tous les éléments de M et on regarde lesquels sont équivalents à l’élément x. Ce seront tous les éléments de la classe d’équivalence M[x].

Pour M[les], nous parcourrions tous les mots de M et nous garderions dans M₃ les mots de longueur trois.

Définition et propriétés de la classe d’équivalence

On pourrait définir la classe d’équivalence ainsi. Prenons un ensemble M muni d’une équivalence R. On appelle alors classe de la partition qui contient l’élément x ∈ M :

$$M[x]=\{y\in M\mid (x;y)\in R\}$$

La définition dit que ce sont tous les y équivalents à l’élément donné x. Comme la relation d’équivalence est réflexive, l’élément x lui-même s’y trouve aussi, car x est équivalent à lui-même.

On appelle partition associée à l’équivalence l’ensemble de toutes les classes d’équivalence. La partition de l’ensemble de tous les mots serait donc l’ensemble {M₁ ; M₂ ; M₃ ; …}.

Propriétés fondamentales des classes d’équivalence :

• (a ; b) ∈ R si et seulement si M[a] = M[b]. Si deux éléments a, b sont équivalents, leurs classes d’équivalence doivent être égales.
• Réciproquement, si (a ; b) ∈ R n’est pas vrai, alors M[a] ≠ M[b] aussi, plus précisément M[a] ∩ M[b] = ∅. Si deux éléments ne sont pas équivalents, leurs classes sont disjointes.
• La réunion de toutes les classes d’équivalence doit redonner l’ensemble M de départ : M₁ ∪ M₂ ∪ … ∪ M_n = M. (Cette écriture ne vaut que pour un nombre fini de classes d’équivalence, mais en général il peut y en avoir une infinité.)

Exemples de partitions associées à une équivalence

Premier exemple, les nombres impairs et pairs :

Prenons une équivalence simple R définie sur les entiers naturels non nuls N = ℕ^*. (a ; b) ∈ R si et seulement si a et b sont tous deux impairs, ou a et b sont tous deux pairs. Exemples de couples : (1 ; 7) ; (13 ; 9) ; (4 ; 6) ; (8 ; 136). Déterminons maintenant la partition associée à cette équivalence, en classes d’équivalence.

Procédons pas à pas. À quoi sera égale la classe N[1] ? Il faut trouver tous les nombres équivalents au nombre un. D’après la condition de l’équivalence, ce sont tous les nombres impairs, donc N[1] = {1 ; 3 ; 5 ; 7 ; 9 ; …}.

À quoi sera égale la classe N[2] ? Trouvons tous les nombres équivalents à deux. Ce sont tous les nombres pairs : N[2] = {2 ; 4 ; 6 ; 8 ; 10 ; …}.

Passons à N[3]. Quels nombres sont équivalents à trois ? Tous les nombres impairs. Mais on obtient ainsi l’ensemble N[1], que nous avons calculé deux paragraphes plus haut. De même pour N[4], où l’on retrouve l’ensemble des nombres pairs.

On voit que, par la suite, les mêmes ensembles se répéteraient sans cesse. On le voit aussi au fait que, quel que soit l’entier naturel non nul n que l’on prenne, on aura n ∈ N[1] ou n ∈ N[2]. Nous n’avons pas d’autres entiers naturels non nuls que les impairs et les pairs, donc ces deux ensembles forment la partition de l’équivalence.

C’est comparable à ce qu’on obtiendrait avec une équivalence sur un ensemble de personnes : a et b sont tous deux des hommes, ou a et b sont tous deux des femmes. La partition serait alors l’ensemble des femmes et l’ensemble des hommes.

Deuxième exemple, la valeur absolue :

Prenons l’équivalence R sur l’ensemble des entiers relatifs Z = ℤ définie ainsi : (a ; b) ∈ R si et seulement si |a| = |b|. (Les barres verticales désignent la valeur absolue.) Là encore, procédons pas à pas :

• Z[0] = {0}. Zéro n’est en relation qu’avec zéro.
• Z[1] = {−1 ; 1}. Un est en relation avec un et avec moins un, car |1| = |−1|.
• Z[2] = {−2 ; 2}. Deux est en relation avec deux et avec moins deux.
• Z[3] = {−3 ; 3}.
• …

On voit sans doute comment cela continue. La partition complète serait donc l’ensemble des classes :

$$\{\{a;-a\}\mid a\in \mathbb{N}\}$$

(C’est-à-dire tous les couples a, −a, où a est un entier naturel.) Tu vois qu’il y a une infinité de classes.