Voir la source de Relation d'équivalence

{{Homon|Équivalence}}En [[mathématiques]], une '''relation d'équivalence''' permet, dans un [[ensemble]], de mettre en [[relation binaire|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'''.

== Exemple intuitif ==
[[Fichier:Exemplare von Büchern mit eingezeichneter Äquivalenzrelation.svg|vignette|upright=1.5|Sur cet ensemble de huit exemplaires de livres, la relation « … a le même [[ISBN]] que … » est une relation d'équivalence.]]Considérons un ensemble de huit exemplaires de livres, comme le montre la figure à droite. Par exemple : deux exemplaires du même dictionnaire Le Robert (en bleu), deux exemplaires d'un même livre de botanique (en vert), trois exemplaires du même livre de mathématiques (en rouge), et un livre de sciences-fiction (en jaune). La relation « … a le même [[ISBN]] que … » est une ''relation d'équivalence''. Par exemple, Deux exemplaires du même dictionnaire ont le même ISBN et sont donc "en relation". On peut regrouper ces exemplaires ensemble : un paquet avec les deux dictionnaires, un paquet avec les deux livres de botaniques, etc. Les paquets sont les ''classes d'équivalence''. L'ensemble de ces quatre paquets est un ''ensemble quotient''.

Comme on le verra dans la définition formelle qui suit, une relation d'équivalence est :

* ''réflexive'' : un exemplaire a le même ISBN que lui-même ;
* ''symétrique'' : si un exemplaire A a le même ISBN que l'exemplaire B alors l'exemplaire B a aussi le même ISBN que A ;
* ''transitive'' : si un exemplaire A a le même ISBN que l'exemplaire B, qui a le même ISBN qu'un exemplaire C, alors l'exemplaire A a le même ISBN que l'exemplaire C.

== Définition ==

=== Définition formelle ===
{{énoncé|
Une relation d'équivalence sur un ensemble ''E'' est une [[relation binaire]] ~ sur ''E'' qui est à la fois [[Relation réflexive|réflexive]], [[Relation symétrique|symétrique]] et [[Relation transitive|transitive]].}}

Plus explicitement :
* ~ est une ''relation binaire'' sur ''E'' : un [[Couple (mathématiques)|couple]] (''x'', ''y'') d'éléments de ''E'' appartient au [[Relation binaire#Définition formelle|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'[[Relation binaire#Définition formelle|ensemble de définition de ~]] (qui se déduit du graphe par [[Produit cartésien#Produit cartésien d'une famille d'ensembles|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<ref>{{Bourbaki-Ensembles}}, {{Google Livres|VDGifaOQogcC|page autre=SL252-PA41|{{p.|II-41}}}}.</ref>.

=== Définition équivalente ===

On peut aussi définir une relation d'équivalence comme une relation binaire ''réflexive'' et ''circulaire''<ref>{{Ouvrage|langue=en|prénom1=W. D.|nom1=Wallis|titre=A Beginner's Guide to Discrete Mathematics|éditeur=[[Springer Science+Business Media]]|année=2011|numéro d'édition=2|passage=104|isbn=|doi=10.1007/978-0-8176-8286-6|lire en ligne=https://books.google.fr/books?id=18W4_LJ5bL0C&pg=PA104}}.</ref>.

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 ==
[[Fichier:Exemplare von Bücher mit eingezeichneter Äquivalenzrelation und Äquivalenzklassen.svg|vignette|upright=1.5|Classes d'équivalence de la relation illustrée précédemment.]]
{{Redirect|Classe d'équivalence|homonymie=Liaison (mécanique)|autres=la notion de classe d'équivalence en mécanique}}

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

{{Énoncé|
On définit la '''classe d'équivalence'''<nowiki> [</nowiki>''x''<nowiki>] d'un élément </nowiki>''x'' de ''E'' comme l'ensemble des ''y'' de ''E'' tels que ''x'' ~ ''y'' :
<center><math>y\in [x]\Leftrightarrow x\sim y.</math></center>
}}

On appelle ''représentant'' de [''x''] n'importe quel élément de [''x''], et ''système de représentants des classes'' toute [[Inclusion (mathématiques)|partie]] de ''E'' qui contient ''exactement un'' représentant par classe<ref>{{Harvsp|Bourbaki|texte=Bourbaki, ''Théorie des ensembles''|p=II-42}}.</ref>.

{{Énoncé|
|*<math>x\sim y\Leftrightarrow[x]=[y].</math>
*L'ensemble des classes d'équivalence forme une [[Partition (mathématiques)|partition]] de ''E'', appelé l''''ensemble quotient''' de ''E'' par la relation ~, noté ''E''/~.
}}

{{Démonstration/début}}
* Par réflexivité de ~, tout élément de ''E'' appartient à sa classe, donc :
** les classes sont non [[Ensemble vide|vides]] et [[Recouvrement (mathématiques)|recouvrent]] ''E'' ;
** [''x''] = [''y''] ⇒ ''x'' ~ ''y''.
* Par transitivité, ''x'' ~ ''y'' ⇒ [''y''] ⊂ [''x''] donc par symétrie, ''x'' ~ ''y'' ⇒ [''x''] = [''y''].
* D'après cette dernière implication, (''x'' ~ ''z'' et ''y'' ~ ''z'') ⇒ [''x''] = [''y''] donc par [[contraposition]], deux classes distinctes sont [[Ensembles disjoints|disjointes]].
{{Démonstration/fin}}

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]] ''B{{ind|n}}'', qui peut se [[Suite définie par récurrence|calculer par récurrence]].

== Exemples ==

* Le [[parallélisme (géométrie)|parallélisme]], sur l'ensemble des droites d'un [[espace affine]], est une relation d'équivalence, dont les classes sont les [[Direction (géométrie)|directions]].
* Toute [[Application (mathématiques)|application]] ''f'' : ''E'' → ''F'' induit sur ''E'' la relation d'équivalence « avoir même [[Image (mathématiques)|image]] par ''f'' ».
* Lorsque cette application est [[Injection (mathématiques)|injective]], la relation d'équivalence qu'elle induit sur ''E'' est l'[[Égalité (mathématiques)|égalité]], dont les classes sont les [[Singleton (mathématiques)|singletons]].
* Sur l'ensemble ℤ des [[entiers relatifs]], la [[Congruence sur les entiers|congruence modulo ''n'']] (pour un entier ''n'' fixé) est une relation d'équivalence, dont les classes forment le [[groupe cyclique]] [[Z/nZ|ℤ/''n''ℤ]].
* Sur l'ensemble <math>\R</math> des réels, la congruence modulo un réel fixé <math>r</math>, définie par <math>(x\equiv y\mod r\Leftrightarrow y-x\in r\Z)</math> est une relation d'équivalence dont les classes sont utilisées pour la mesure d'[[Angle orienté|angles orientés]], pour <math>r=2\pi</math> ou <math>r=\pi</math>.
* Plus généralement, si ''G'' est un [[Groupe (mathématiques)|groupe]] et ''H'' un [[sous-groupe]] de ''G'' alors la relation ~ sur ''G'' définie par (''x'' ~ ''y'' ⇔ ''y''{{-1}}''x'' ∈ ''H'') est une relation d'équivalence, dont les classes sont appelées les [[Classe suivant un sous-groupe|classes à gauche suivant ''H'']].
* Dans l'ensemble des couples de vecteurs non nuls d'un [[Plan euclidien|plan vectoriel euclidien]], la relation définie par : <math>(\vec u,\vec v)\sim (\vec u',\vec v')\Leftrightarrow</math> il existe une [[Rotation vectorielle|rotation]] envoyant <math>\frac{\vec u}{\lVert \vec u \rVert}</math> sur <math>\frac{\vec v}{\lVert \vec v \rVert}</math> et <math>\frac{\vec u'}{\lVert \vec u' \rVert}</math> sur <math>\frac{\vec v'}{\lVert \vec v' \rVert}</math>, est une relation d'équivalence dont les classes, notées <math>\widehat{(\vec u,\vec v)}</math>, sont les [[Angle orienté|angles orientés de vecteurs]], en bijection naturelle avec les classes de réels modulo <math>2\pi.</math>
* Dans l'ensemble des couples de droites  d'un [[Plan euclidien|plan affine euclidien]], la relation définie par : <math>(D_1,D_2)\sim (D'_1,D'_2)\Leftrightarrow</math> il existe un [[Déplacement (géométrie)|déplacement]] envoyant <math>D_1</math> sur <math>D_2</math> et <math>D'_1</math> sur <math>D'_2</math>, est une relation d'équivalence dont les classes, notées <math>\widehat{(D_1,D_2)}</math>, sont les [[Angle orienté|angles orientés de droites]], en bijection naturelle avec les classes de réels modulo <math>\pi.</math>
* L'égalité [[ensemble négligeable|presque partout]], pour des fonctions sur un [[espace mesuré]], est une relation d'équivalence qui joue un rôle important dans la [[Intégrale de Lebesgue|théorie de l'intégration de Lebesgue]]. En effet, deux fonctions égales presque partout ont le même comportement dans cette théorie.
<!--exemple trop exotique àma pour cet article, masqué le 6/9/2014
* La relation d'un [[Sémantique de Kripke|modèle de Kripke]] de la [[logique modale]] S5 est une relation d'équivalence. En particulier, si l'on modélise la connaissance avec la logique modale S5, la relation épistémique d'un agent est une relation d'équivalence.
-->
* On trouve d'autres exemples dans les articles suivants :
** [[Équipollence (mathématiques)|Équipollence]],
** [[Préordre]],
** [[Action de groupe (mathématiques)|Action de groupe]],
*** [[Espace projectif]],
*** [[Matrices congruentes]], [[Matrices équivalentes]], [[Matrices semblables]],
*** [[Triangles isométriques]], [[Triangles semblables]],
** [[Construction des entiers relatifs]], [[Corps des fractions]], [[Espace complet#Complété d'un espace métrique|Complété d'un espace métrique]],
** [[Topologie quotient]],
** [[Équivalence d'homotopie]],
** [[Germe (mathématiques)|Germe]].
;[[Contre-exemple]]s
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 [[Relation d'ordre|ordre]] sur une [[paire]]) ;
* une {{Lien|langue=en|trad=Partial equivalence relation|fr=relation d'équivalence partielle}} est ''symétrique et transitive'' par définition, mais pas réflexive en général (exemple [[trivial]] : sur un ensemble non [[Ensemble vide|vide]], la relation de graphe vide) ;
* une [[relation de tolérance]] 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 (mathématiques)|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 ==
On donne ce nom à la partition de ''E'' mise en évidence ci-dessus.
=== Définition ===
{{Énoncé|Étant donné une relation d'équivalence ~ sur ''E'', l''''ensemble quotient''' de ''E'' par la relation ~, noté ''E''/~, est le sous-ensemble de <math>\mathcal{P}(E)</math> des classes d'équivalence :
<center><math>{E/\sim}~=~\{[x]\in\mathcal{P}(E)\mid x\in E\}.</math></center>
}}

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 ===

L'application [[Canonique (mathématiques)|canonique]] ''p'', de ''E'' dans l'ensemble quotient, qui à chaque élément de ''E'' associe sa classe d'équivalence :
<center><math>\begin{matrix}p:&E&\rightarrow&{E/\sim}\\&x&\mapsto&[x]\end{matrix}</math></center>
* est [[Surjection|surjective]] par construction car <math>E/\sim</math> est l'image de l'application <math>x \mapsto [x]</math> de <math>E</math> dans <math>\mathcal{P}(E)</math>;
* n'est en général pas [[Injection (mathématiques)|injective]] (sauf si ~ est l'[[Égalité (mathématiques)|égalité]]), puisqu'on a seulement <center><math>p(x)=p(y)\Leftrightarrow x\sim y.</math></center>

Une telle application ''p'' est appelée une ''projection''. Elle vérifie la [[propriété universelle]] suivante, qui exprime que toute application définie sur ''E'' dont la [[#Exemples|relation d'équivalence associée]] est [[Relation binaire#Définition formelle|moins fine]] que ~ « passe au quotient » ''E''/~ de façon unique :

{{Théorème|[[Théorème de factorisation#Le cas des ensembles|Théorème de factorisation]]|2=Pour toute application ''f'' : ''E'' → ''F'' vérifiant [''x'' ~ ''y'' ⇒ ''f''(''x'') = ''f''(''y'')], il existe une unique application ''g'' : ''E''/~ → ''F'' telle que [[Composition de fonctions|''f = g''∘''p'']].}}
Cette application ''g'' — qui a donc même [[Image d'une application|image]] que ''f'' — est injective si et seulement si ''x'' ~ ''y'' ⇔ ''f''(''x'') = ''f''(''y'').

=== Structure quotient ===
{{Article détaillé|Magma quotient}}
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 {{Lien|langue=en|trad=Congruence relation|fr=Relation de congruence|texte=compatible}} 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 {{Page h'|Quotient|structure quotient}} de la structure initiale par la relation d'équivalence.

Par exemple si ⊤ est une [[loi interne]] sur ''E'' compatible avec ~, c'est-à-dire vérifiant

{{Retrait|1=(''x'' ~ ''x{{'}}'' et ''y'' ~ ''y{{'}}'') ⇒ ''x''⊤''y'' ~ ''x{{'}}''⊤''y{{'}}'',}}

la {{Citation|''loi quotient'' de la loi ⊤ par ~}} est définie comme {{Citation|la loi de composition sur l'ensemble quotient ''E''/~ qui, aux classes d'équivalence de ''x'' et de ''y'', fait correspondre la classe d'équivalence de ''x'' ⊤ ''y''.}}<ref>{{Ouvrage|auteur1=N. Bourbaki|titre=Éléments de mathématique, Algèbre, chapitres 1 à 3|éditeur=|année=|passage=I-11|isbn=}}.</ref>

(Plus formellement : en notant ''p'' la surjection ''E'' × ''E'' → ''E''/~ × ''E''/~, (''x'', ''y'') ↦ ([''x''], [''y'']) et ''f'' l'application ''E'' × ''E'' → ''E''/~, (''x'', ''y'') ↦ [''x''⊤''y''], l'hypothèse de compatibilité se réécrit ''p''(''x'', ''y'') = ''p''(''x{{'}}'', ''y{{'}}'') ⇒ ''f''(''x'', ''y'') = ''f''(''x{{'}}'', ''y{{'}}''). En appliquant le théorème de factorisation [[#Surjection canonique|ci-dessus]], on peut donc définir la loi quotient comme l'unique application ''g'' : ''E''/~ × ''E''/~ → ''E''/~ telle que ''f'' = ''g''∘''p''.)

; Exemples
:* Sur le [[corps ordonné]] des [[Nombre réel|réels]], la relation « a le même signe que » (comprise au sens strict) a trois classes d'équivalence :
:** l'ensemble des entiers strictement positifs ;
:** l'ensemble des entiers strictement négatifs ;
:** le [[Singleton (mathématiques)|singleton]] {0}.
:: La multiplication est compatible avec cette relation d'équivalence et la [[Signe_(arithmétique)#Règle_des_signes|règle des signes]] est l'expression de la loi quotient.
:* Si ''E'' est muni d'une structure de groupe, on associe à tout [[sous-groupe normal]] une relation d'équivalence compatible, ce qui permet de définir un [[groupe quotient]].

== Relation d'équivalence engendrée ==
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''<ref>{{Ouvrage|prénom1=Jean-Pierre|nom1=Ramis|lien auteur1=Jean-Pierre Ramis|prénom2=André|nom2=Warusfel|lien auteur2=André Warusfel|nom3=al.|lien auteur3=et al.|titre=Mathématiques. Tout-en-un pour la Licence. Niveau 1|éditeur=[[Dunod]]|année=2013|numéro d'édition=2|pages totales=896|passage=31|isbn=978-2-10-060013-7|lire en ligne=https://books.google.fr/books?id=K3gcey1WUXMC&pg=PA31}}.</ref>. Elle est égale à la [[clôture réflexive transitive]] de {{nobr|''R'' ∪ [[Relation binaire#Réciproque|''R''{{-1}}]]}}.

== Notes et références ==
{{Références}}

{{Portail|mathématiques}}

[[Catégorie:Préordre]]
[[Catégorie:Algèbre générale]]