Relation d'équivalence

Relation d'équivalence

En théorie des ensembles, la notion de relation d'équivalence sur un ensemble permet 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.

Sommaire

Définition

Définition formelle

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

  • C'est une relation binaire : c'est donc une somme disjointe (E, E, G_{\mathcal R}), où G_{\mathcal R} , le graphe de \mathcal R\, , est une partie de E2 caractérisant la relation. En pratique , sauf ambiguïté sur l'ensemble dans lequel la relation est placée, on peut confondre celle-ci avec son graphe. Si x et y sont deux éléments de E, on dit que « y est image de x par \mathcal R\, » ou que « y est associé à x par \mathcal R\, » ou que « y correspond à x par \mathcal R\, » si le couple (x,y) appartient à G_{\mathcal R} ; on note cela « x\mathcal R\,y » .
  • \mathcal R\, est réflexive : tout élément de E est associé à lui-même :   \forall\ x \in E , x \mathcal R x \,
  • \mathcal R\, est symétrique : tout élément de E est image de ses images :
\forall\ ( x , y ) \in E^{\, 2} , ( x \mathcal R y ) \Rightarrow ( y \mathcal R x ) \,
  • \mathcal R\, est transitive : toute image d'une image d'un élément de E est directement image de cet élément :
\forall\ ( x , y , z ) \in E^{\, 3} , ( x \mathcal R y \wedge y \mathcal R z ) \Rightarrow ( x \mathcal R z ) \,

Définition équivalente

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

Une relation binaire est dite circulaire si toute image d'une image d'un élément de E est antécédent de cet élément, c'est-à-dire si :

\forall\ ( x , y , z ) \in E^{\, 3} , ( x \mathcal R y \wedge y \mathcal R z ) \Rightarrow ( z \mathcal R x )~.

Classe d'équivalence

Considérons un ensemble non vide E muni d'une relation d'équivalence \mathcal R\,. La classe d'équivalence d'un élément x de E , notée « \mathcal R( x ) » , est alors l'ensemble des images de x par \mathcal R\, :

\mathcal R ( x ) = \{ y \in E \,|\ x \mathcal R y \} \, .
  • Si y \in \mathcal R ( x ) alors y est appelé un représentant de \mathcal R ( x ).
  • \mathcal R( x ) n'est jamais vide, car elle contient toujours au moins x lui-même ( \mathcal R\, est réflexive ).
  • Inversement, tout élément de E appartient à au moins une classe d'équivalence : la sienne ( x \in \mathcal R ( x ) ).
  • \mathcal R( y ) = \mathcal R( x ) \Leftrightarrow y \in \mathcal R( x ).
  • Inversement, si y est un élément de E n'appartenant pas à \mathcal R( x ) , alors l'intersection de \mathcal R( x ) et de \mathcal R( y ) est vide.

On déduit de ce qui précède que l'ensemble des classes d'équivalence de E forme une partition de E. Inversement, toute partition d'un ensemble y définit une relation d'équivalence. Ceci établit une bijection naturelle entre les partitions d'un ensemble et les relations d'équivalence dans cet ensemble.

Enfin, la restriction d'une relation d'équivalence à l'une de ses classes d'équivalence est une relation pleine.

Ensemble quotient

C'est l'ensemble des classes d'équivalence de E suivant \mathcal R.

Définition

L' ensemble quotient de E par la relation d'équivalence \mathcal R , noté «  E / \mathcal R » , est l'ensemble des classes d'équivalence de E suivant \mathcal R :

E / \mathcal R = \{ \mathcal R ( x ) \,|\ x \in E \} \,

L'ensemble quotient est donc un nouvel ensemble construit à partir de E et de \mathcal R. C'est un sous-ensemble de \mathfrak P ( E ) , ensemble des parties de E.

Remarque : on peut munir une classe propre d'une relation d'équivalence. On peut même y définir des classes d'équivalence, mais comme elles peuvent être elles-mêmes des classes propres, cela interdit l'existence d'un ensemble quotient dans ce cas. Par exemple, si l'on considère la relation d'équipotence dans la classe des ensembles, cette relation est une relation d'équivalence, et on peut y définir des classes d'équivalence dites « classes d'équipotence » :

  • la classe d'équipotence de l'ensemble vide est ainsi le singleton formé par l'ensemble vide, puisqu'il ne peut être mis en bijection qu'avec lui-même;
  • les singletons forment une autre classe d'équipotence; mais il s'agit d'une classe propre, ce qui interdit de former un ensemble ( ou une classe ) à partir des classes d'équipotence ( et, accessoirement, d'identifier les classes d'équipotence aux cardinaux ).

L'ensemble quotient peut aussi être désigné comme « l'ensemble E quotienté par \mathcal R » ou « l'ensemble E considéré modulo \mathcal R ». 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 {\mathcal R}.

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 \mathbb Z_+^* des entiers strictement positifs,
  2. l'ensemble \mathbb Z_-^* des entiers strictement négatifs,
  3. le singleton {0}.

On peut noter ces trois classes par, respectivement, (+), (-) et (0).

On connaît la « règle des signes » pour le produit de deux entiers relatifs : elle montre que si on sait dans quelle classe d'équivalence se trouvent x et y, le produit xy se trouve dans une classe bien déterminée. 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 (-) ? Pour savoir si les lois et les propriétés de structure sont compatibles avec le passage au quotient, il est utile d'introduire le concept de surjection canonique.

Surjection canonique

Il existe une surjection canonique s de E dans l'ensemble quotient, qui à chaque élément de E associe sa classe d'équivalence :

s   :   E \longrightarrow E / \mathcal R \,
x \longmapsto \ A = \mathcal R ( x ) \,

s est une application puisque tout élément de E appartient à une et une seule classe d'équivalence; s est surjective puisqu'aucune classe d'équivalence n'est vide.

s n'est pas en général injective, mais on a :

\forall x \in E , \forall y \in E , \, [ s ( x ) = s ( y ) ] \Leftrightarrow [ \mathcal R ( x ) = \mathcal R ( y ) ] \Leftrightarrow [ x \mathcal R y ] \,

Cette surjection est ainsi une bijection si et seulement si la relation d'équivalence concernée n'est autre que la relation d'égalité.

Structure quotient

Grâce à la surjection s , 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 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 / \mathcal R.

Exemples

  • L'égalité sur un ensemble quelconque de nombres (entiers, rationnels, réels, complexes) est une relation d'équivalence.
  • Le parallélisme sur un ensemble de droites (dans un plan) est une relation d'équivalence.
  • Si f \, est une application d'un ensemble E dans un ensemble F, alors la relation \mathcal R définie par :
\forall\ ( x , y ) \in E^{\, 2} , [ x \mathcal R y ] \Leftrightarrow [ f( x) = f( y) ] \,
est une relation d'équivalence sur E. Ainsi toute application induit une relation d'équivalence sur son ensemble de départ.
f \, est une injection ssi la relation induite dans l'ensemble de départ est la relation d'égalité. Nous avons alors :
\forall\ ( x , y ) \in E^{\, 2} , [ f( x) = f( y) ] \Leftrightarrow [ x = y ] \,
  • Le fait d'être égales presque partout pour des fonctions sur un espace mesuré est une relation d'équivalence qui joue un rôle important dans la théorie de l'intégration de Lebesgue. En effet deux fonctions égales presque partout ont le même comportement dans cette théorie.
  • La relation d'un 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.
Contre-exemples

Plusieurs relations exhibent la réflexivité, la symétrie ou la transitivité, mais pas toutes :

  • Réflexive et transitive : \forall\ ( x , y ) \in \mathbb N^{\, 2} , [ x \mathcal R y ] \Leftrightarrow [ x \leq y ] \,
  • Symétrique et transitive : \forall\ ( x , y ) \in \mathbb N^{\, 2} , [ x \mathcal R y ] \Leftrightarrow [ x y \neq 0 ] \,
  • Réflexive et symétrique : \forall\ ( x , y ) \in \mathbb Z^{\, 2} , [ x \mathcal R y ] \Leftrightarrow [ (2 \mid (x - y)) \vee (3 \mid (x - y)) ] \, (« x-y est divisible par 2 ou par 3 »)

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Relation d'équivalence de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Relation d'equivalence — Relation d équivalence La notion de relation d équivalence sur un ensemble permet 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… …   Wikipédia en Français

  • équivalence — [ ekivalɑ̃s ] n. f. • 1361; bas lat. æquivalentia, de æquivalere 1 ♦ Qualité de ce qui est équivalent. ⇒ adéquation, égalité, homologie, identité. Les jacqueries « mettent en avant un principe d équivalence, vie contre vie » (Camus). ♢ (1864)… …   Encyclopédie Universelle

  • Relation antisymétrique — Relation binaire Une relation binaire est un concept mathématique qui systématise des notions comme « ... est supérieur ou égal à ... » en arithmétique, ou « ... est élément de l’ensemble ... » en théorie des ensembles. C’est… …   Wikipédia en Français

  • RELATION — Le concept de relation apparaît comme l’un des concepts fondamentaux du discours rationnel. Il semble lié à la pratique de l’analyse, qui constitue elle même l’un des aspects essentiels de la démarche discursive. L’analyse décompose les unités… …   Encyclopédie Universelle

  • Equivalence — Équivalence Voir « équivalence » sur le Wiktionnaire …   Wikipédia en Français

  • Equivalence logique — Équivalence logique En logique classique, deux propositions P et Q sont logiquement équivalentes ou équivalentes si P et Q ont simultanément même valeur de vérité; c est à dire que P et Q sont vraies (resp. fausses), dans exactement les mêmes… …   Wikipédia en Français

  • Relation masse-portee — Relation masse portée La relation masse portée est une expression majeure de la compréhension que les physiciens associent aux champs de forces. Elle est obtenue par l intermédiaire de formules simples associant la mécanique quantique, via les… …   Wikipédia en Français

  • Relation de congruence modulo un entier — ● Relation de congruence modulo un entier relation définie sur l ensemble Z des entiers relatifs par x congru à y modulo n (noté x ≡ y mod n) si et seulement si x − y est multiple de n. (Cette relation est u …   Encyclopédie Universelle

  • Equivalence relation — In mathematics, an equivalence relation is a binary relation between two elements of a set which groups them together as being equivalent in some way. Let a , b , and c be arbitrary elements of some set X . Then a b or a ≡ b denotes that a is… …   Wikipedia

  • Relation binaire — En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est caractérisée par un sous ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”