relation d'équivalence

Rangeons les entiers de 0 à 8 selon le reste obtenu dans la division par 3. Les nombres 0, 3 et 6 vont ensemble ; 1, 4 et 7 forment un autre groupe ; 2, 5 et 8 un troisième. Dans chaque groupe, deux nombres diffèrent d'un multiple de 3. Cette manière déclarée de les considérer comme équivalents est une relation d'équivalence. Elle ne dit pas qu'ils sont égaux : elle retient seulement un caractère commun précis.

Soit un ensemble E et une relation binaire notée R entre ses éléments. La relation R est une relation d'équivalence lorsque, pour tous éléments x, y et z de E, elle est réflexive, symétrique et transitive. Cela signifie que tout élément est en relation avec lui-même ; que x en relation avec y entraîne y en relation avec x ; et que x en relation avec y, puis y en relation avec z, entraîne x en relation avec z.

Ces trois conditions s'écrivent :

La classe d'équivalence d'un élément a est l'ensemble des éléments de E qui sont en relation avec a. Chaque élément appartient à une seule classe, et toutes les classes obtenues forment une partition de E. Inversement, toute partition de E définit une relation d'équivalence : deux éléments sont déclarés équivalents lorsqu'ils appartiennent à la même partie.

Pour décider si une relation R sur un ensemble E est une relation d'équivalence, il faut vérifier les trois propriétés, sans exception : Si une seule propriété échoue, R n'est pas une relation d'équivalence. Si les trois sont établies, les classes associées sont deux à deux disjointes et recouvrent E : elles constituent une partition de l'ensemble.

La relation doit être définie entre éléments d'un même ensemble E, et son critère doit permettre de tester chaque couple. Il faut ensuite établir la réflexivité pour tout élément, la symétrie pour tout couple et la transitivité pour tout triplet. Les trois quantificateurs portent sur l'ensemble entier, pas seulement sur quelques exemples.

Contre-cas : sur les entiers, la relation « être strictement inférieur à » n'est pas réflexive, car aucun entier n'est strictement inférieur à lui-même, et elle n'est pas symétrique. Elle ordonne certains couples, mais elle ne crée donc pas de classes d'équivalence. Pour regrouper les entiers selon un reste, on emploie plutôt la congruence modulo un entier positif.

Sur l'ensemble E = {0, 1, 2, 3, 4, 5, 6, 7, 8}, deux entiers sont déclarés équivalents lorsque leur différence est un multiple de 3. Les données sont donc l'ensemble E, le diviseur 3 et le critère « 3 divise la différence ».

1. La réflexivité est satisfaite : pour tout entier x de E, la différence x − x vaut 0, qui est un multiple de 3.

2. La symétrie est satisfaite : si x − y est un multiple de 3, alors y − x est son opposé et reste un multiple de 3.

3. La transitivité est satisfaite : si x − y et y − z sont des multiples de 3, leur somme x − z est aussi un multiple de 3. La relation est donc une relation d'équivalence.

4. Les classes sont {0, 3, 6}, {1, 4, 7} et {2, 5, 8}. Elles ne se chevauchent pas et réunissent les neuf éléments de E. Le schéma des trois groupes rend ce contrôle visible : chaque entier de 0 à 8 apparaît exactement une fois.

Pour ranger des entiers par reste, la congruence regroupe ceux qui ont le même reste dans une division. Elle est préférable à l'égalité lorsque seule cette information compte, par exemple le reste modulo 3 dans l'exemple.

Pour simplifier un ensemble d'objets, on peut remplacer chaque classe par un représentant. Ce geste est pertinent lorsque le résultat recherché ne change pas d'un élément à un autre de la même classe ; sinon, il faut conserver les éléments distincts.

Pour construire une classification, on contrôle les trois propriétés avant de nommer les groupes. Si deux groupes se recouvrent sans être identiques, le regroupement obtenu n'est pas la partition associée à une relation d'équivalence.

Égalité. L'égalité exige que deux éléments soient le même élément, tandis qu'une relation d'équivalence peut seulement les placer dans une même classe. Dans l'exemple modulo 3, 0 et 3 sont équivalents, mais 0 n'est pas égal à 3.

Relation d'ordre. Un ordre est notamment antisymétrique : si x précède y et y précède x, alors x et y sont égaux. Une relation d'équivalence est symétrique et peut relier des éléments distincts, comme 1 et 4 modulo 3.

Relation binaire quelconque. Toute relation d'équivalence est binaire, mais toute relation binaire n'est pas une équivalence. Le test décisif consiste à vérifier ensemble la réflexivité, la symétrie et la transitivité.

Quelques vérifications ne suffisent pas. Constater que plusieurs couples fonctionnent ne prouve aucune propriété universelle. Il faut raisonner pour tous les éléments concernés ou trouver un seul contre-exemple, qui suffit à invalider la propriété testée.

Deux classes ne se chevauchent jamais partiellement. Pour une relation d'équivalence, deux classes qui ont un élément commun sont nécessairement égales. Si des groupes proposés ont seulement quelques éléments communs, il faut revoir la relation ou le classement.

Le représentant n'est pas toujours canonique. Une classe peut contenir plusieurs éléments sans que l'un soit naturellement privilégié. Choisir 0 pour représenter {0, 3, 6} dans l'ensemble E est une convention pratique, pas une propriété de la relation.

Le cas de l'ensemble vide. Sur l'ensemble vide, les trois propriétés sont vraies faute de contre-exemple : l'unique relation, vide elle aussi, est donc une relation d'équivalence. La partition associée ne contient aucune classe.

La partition d'un ensemble présente l'autre face de la notion : les classes d'équivalence sont précisément les parties disjointes qui recouvrent l'ensemble.

La relation binaire fournit le cadre général dans lequel les trois propriétés d'une relation d'équivalence sont formulées.

La congruence modulo n développe une famille centrale d'exemples : les entiers y sont regroupés selon le reste de leur division par n.