Relation d'équivalence

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Équivalence.

La notion ensembliste de relation d'équivalence est omniprésente en mathématiques. Elle permet, dans un ensemble, de mettre en relation des éléments qui sont similaires par une certaine propriété.

On pourra ainsi regrouper ces éléments par « paquets » d'éléments qui se ressemblent, définissant ainsi la notion de classe d'équivalence, pour enfin construire de nouveaux ensembles en « assimilant » les éléments similaires à un seul et même élément. On aboutit alors à la notion d'ensemble quotient.

Sur cet ensemble de huit exemplaires de livres, la relation « … a le même ISBN que … » est une relation d'équivalence.

Définition[modifier | modifier le code]

Définition formelle[modifier | modifier le code]

Une relation d'équivalence sur un ensemble E est une relation binaire ~ sur E qui est à la fois réflexive, symétrique et transitive.

Plus explicitement :

  • ~ est une relation binaire sur E : un couple (x, y) d'éléments de E appartient au graphe de cette relation si et seulement si x ~ y.
  • ~ est réflexive : pour tout élément x de E, on a x ~ x.
  • ~ est symétrique : chaque fois que deux éléments x et y de E vérifient x ~ y, ils vérifient aussi y ~ x
  • ~ est transitive : chaque fois que trois éléments x, y et z de E vérifient x ~ y et y ~ z, ils vérifient aussi x ~ z.

Par réflexivité, E coïncide alors avec l'ensemble de définition de ~ (qui se déduit du graphe par projection). Inversement, pour qu'une relation binaire sur E symétrique et transitive soit réflexive, il suffit que son ensemble de définition soit E tout entier[1].

Définition équivalente[modifier | modifier le code]

On peut aussi définir une relation d'équivalence comme une relation binaire réflexive et circulaire[2].

Une relation binaire ~ est dite circulaire si chaque fois qu'on a x ~ y et y ~ z, on a aussi z ~ x.

Classe d'équivalence[modifier | modifier le code]

Classes d'équivalence de la relation illustrée précédemment.
Page d'aide sur l'homonymie Pour les articles homonymes, voir Classe d'équivalence.

Fixons un ensemble E et une relation d'équivalence ~ sur E.

On définit la classe d'équivalence [x] d'un élément x de E comme l'ensemble des y de tels que x ~ y :

y\in [x]\Leftrightarrow x\sim y.

On appelle représentant de [x] n'importe quel élément de [x], et système de représentants des classes toute partie de E qui contient exactement un représentant par classe[3].

  • x\sim y\Leftrightarrow[x]=[y].
  • L'ensemble des classes d'équivalence forme une partition de E.

Inversement, toute partition d'un ensemble E définit une relation d'équivalence sur E. Ceci établit une bijection naturelle entre les partitions d'un ensemble et les relations d'équivalence sur cet ensemble. Le nombre de relations d'équivalence sur un ensemble à n éléments est donc égal au nombre de Bell Bn, qui peut se calculer par récurrence.

Exemples[modifier | modifier le code]

Contre-exemples

Beaucoup de relations sont réflexives, symétriques ou transitives, sans être les trois à la fois :

  • un préordre est réflexif et transitif par définition, mais pas symétrique en général (exemple : un ordre sur une paire) ;
  • une relation d'équivalence partielle (en) est symétrique et transitive par définition, mais pas réflexive en général (exemple trivial : sur un ensemble non vide, la relation de graphe vide) ;
  • une relation de tolérance (en) est réflexive et symétrique par définition, mais pas transitive en général (exemple : sur les entiers, la relation ~ définie par : m ~ n ⇔ |m – n| ≤ 1).
Remarque

On peut munir une classe propre d'une relation d'équivalence. On peut même y définir des classes d'équivalence, mais elles peuvent être elles-mêmes des classes propres, et ne forment généralement pas un ensemble (exemple : la relation d'équipotence dans la classe des ensembles).

Ensemble quotient[modifier | modifier le code]

On donne ce nom à la partition de E mise en évidence ci-dessus, qui est donc un sous-ensemble de l'ensemble P(E) des parties de E.

Définition[modifier | modifier le code]

Étant donnée une relation d'équivalence ~ sur E, l'ensemble quotient de E par la relation ~, noté E/~, est l'ensemble des classes d'équivalence :

{E/\sim}~=~\{[x]\mid x\in E\}.

L'ensemble quotient peut aussi être appelé « l'ensemble E quotienté par ~ » ou « l'ensemble E considéré modulo ~ ». L'idée derrière ces appellations est de travailler dans l'ensemble quotient comme dans E, mais sans distinguer entre eux les éléments équivalents selon ~.

Surjection canonique[modifier | modifier le code]

L'application canonique p, de E dans l'ensemble quotient, qui à chaque élément de E associe sa classe d'équivalence :

\begin{matrix}p:&E&\rightarrow&{E/\sim}\\&x&\mapsto&[x]\end{matrix}

Elle vérifie la propriété universelle suivante[4] : toute application f : EF dont la relation d'équivalence associée est « moins fine » que ~, c'est-à-dire vérifiant [x ~ yf(x) = f(y)], « passe au quotient » E/~ de façon unique, c'est-à-dire se factorise sous la forme f = gp pour une unique application g. Cette application g : E/~ → F — qui a donc même image que f — est injective si et seulement si les deux relations d'équivalence coïncident.

Structure quotient[modifier | modifier le code]

Exemple
L'ensemble des entiers relatifs peut être muni de la relation « a le même signe que » (comprise au sens strict). Il y a trois classes d'équivalence :
  1. l'ensemble des entiers strictement positifs,
  2. l'ensemble des entiers strictement négatifs,
  3. le singleton {0}.
On peut noter ces trois classes par, respectivement, (+), (-) et (0).
D'après la règle des signes, la classe du produit de deux entiers relatifs x et y ne dépend que de la classe de x et de celle de y. Par exemple, si x est dans (+) et y dans (0), alors xy est dans (0). Formellement, on peut le noter (+)·(0)=(0). De même (+)·(-)=(-), ou encore (+)·(+)=(+), (-)·(-)=(+), etc. Ceci est un exemple simple de « loi-quotient ».
Mais avec cet exemple on ne peut pas « faire passer au quotient » la loi + : que dire de la somme d'un élément de (+) et d'un élément de (-) ?

Si E est muni d'une structure algébrique, il est possible de transférer cette dernière à l'ensemble quotient, sous réserve que la structure soit compatible (en) avec la relation d'équivalence, c'est-à-dire que deux éléments de E se comportent de la même manière vis-à-vis de la structure s'ils appartiennent à la même classe d'équivalence. L'ensemble quotient est alors muni de la structure quotient de la structure initiale par la relation d'équivalence.

Par exemple, si E est muni d'une structure de groupe, il est possible, dans certains cas, de parler du groupe quotient E/~.

Relation d'équivalence engendrée[modifier | modifier le code]

Sur un ensemble E, soit R une relation binaire, identifiée à son graphe. L'intersection de toutes les relations d'équivalence sur E qui contiennent R est appelée la relation d'équivalence (sur E) engendrée par R[5]. Elle est égale à la fermeture transitive de RR−1ΔE.

Notes et références[modifier | modifier le code]

  1. N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], p. II.41.
  2. (en) W. D. Wallis, A Beginner's Guide to Discrete Mathematics, Springer Science+Business Media,‎ 2011, 2e éd. (DOI 10.1007/978-0-8176-8286-6, lire en ligne), p. 104.
  3. Bourbaki, p. II.42.
  4. Saunders Mac Lane et Garrett Birkhoff, Algèbre [détail des éditions] , p. 35 de l'éd. de 1999 en anglais.
  5. Jean-Pierre Ramis, André Warusfel et al., Mathématiques. Tout-en-un pour la Licence. Niveau 1, Dunod,‎ 2013, 2e éd. (ISBN 978-2-10-060013-7, lire en ligne), p. 31.