Relacion d'equivaléncia

En matematicas, una relacion d'equivaléncia dins un ensemble E, relacion binària d'un tipe particular, es lo mejan de definir una classificacion completa deis elements de E segon un critèri donat.

Leis elements de E son agropats en classas d'equivaléncia : cada element x de E apartèn a una classa determinada sens ambigüitat, contenent totei leis elements de E que, segon lo critèri utilizat, se pòdon pas destriar de x : se ditz que son equivalents a x.

Es sovent interessant d'identificar (de considerar per identics) leis elements de E qu'apartènon a una meteissa classa d'equivaléncia, valent a dire de lei confondre volontariament : se definís ansin l'ensemble quocient de E per la relacion d'equivaléncia, qu'es l'ensemble dei classas d'equivaléncia.

Per exemple, dins l'ensemble $\mathbb {N}$ deis entiers naturaus, lo critèri de paritat correspònde a la relacion binària "aver la meteissa paritat que", qu'es una relacion d'equivaléncia (coma se poirà verificar aisadament, cf. la definicion çai sota). Permete d'agropar leis entiers naturaus en doas classas, que designarem aicí per lei notacions ${\mathcal {P}},\,{\mathcal {I}}$ :

${\mathcal {P}}=\{0,\,2,\,4,\dots \}$ es la classa deis entiers naturaus pars

${\mathcal {I}}=\{1,\,3,\,5,\dots \}$ es la classa deis entiers naturaus impars

L'ensemble quocient de E per aquesta relacion d'equivaléncia es l'ensemble $\{{\mathcal {P}},\,{\mathcal {I}}\}$ que seis elements son lei doas classas d'equivaléncia.

Definicion

Se sòna relacion d'equivaléncia dins un ensemble E (supausat non vuege) una relacion binària ${\mathcal {R}}$ dins E qu'es au còp reflexiva, simetrica e transitiva, valent a dire :

• reflexivitat :

$\forall \,x\in E,x{\mathcal {R}}x$

• simetria :

$\forall (x,\,y)\in E^{2},(x{\mathcal {R}}y)\Rightarrow (y{\mathcal {R}}x)$

• transitivitat :

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

Quand ${\mathcal {R}}$ es una relacion d'equivaléncia dins E e que dos elements x, y de E son taus que $x{\mathcal {R}}y$ , se ditz que :

x, y son equivalents modulo ${\mathcal {R}}$ (o "equivalents segon ${\mathcal {R}}$ ").

Remarca : es clar que l'egalitat dins un ensemble E es una relacion d'equivaléncia dins E e que per tot element x de E, x es lo solet element equivalent (valent a dire aicí : egau) a x. La nocion de relacion d'equivaléncia generaliza la nocion d'egalitat.

Notacions

• Una notacion frequenta per una relacion d'equivaléncia es " $\ \sim$ " ; s'escriu sovent : $\ x\sim y$ en plaça de : $x{\mathcal {R}}y$ .
• De còps que i a, s'escriu : $x\equiv y\mod {\mathcal {R}}$ (onte "mod" es una abreviacion de modulo).

Classas d'equivaléncia

Siá ${\mathcal {R}}$ una relacion d'equivaléncia dins un ensemble E.

Definicion

• Per tot element x de E, se definís ansin la classa d'equivaléncia (o classa) de x modulo ${\mathcal {R}}$ (o "segon ${\mathcal {R}}$ "):

${\mathcal {R}}(x)=\{y\in E\mid x{\mathcal {R}}y\}$ (la classa de x es lo sosensemble de E qu'a per elements leis elements de E equivalents a x).

S'escriu sovent (se lo contèxte es clar) : ${\overline {x}}$ en luòga de : ${\mathcal {R}}(x)$ .

• Inversament, se ditz qu'un sosensemble ${\mathcal {C}}$ de E es una classa d'equivaléncia modulo ${\mathcal {R}}$ (o "segon ${\mathcal {R}}$ ") s'existís (aumens) un element x de E tau que ${\mathcal {R}}(x)={\mathcal {C}}$ .

Remarca : estent dos elements x, y de E :

$y\in {\mathcal {R}}(x)\iff x{\mathcal {R}}y\quad (1)$

$x\in {\mathcal {R}}(y)\iff x{\mathcal {R}}y\quad (2)$

La proposicion (1) es ren autre que la definicion de la classa d'equivaléncia de x.
Se'n dedutz : $x\in {\mathcal {R}}(y)\iff y{\mathcal {R}}x$ en intervertissent x, y, puei la proposicion (2) per simetria de ${\mathcal {R}}$ .

Proprietat

• Tota classa d'equivaléncia (modulo ${\mathcal {R}}$ ) es una partida non vueja de E
• Estent dos elements x, y de E :

se $y\in {\mathcal {R}}(x)$ , alora ${\mathcal {R}}(x)={\mathcal {R}}(y)$

se $y\notin {\mathcal {R}}(x$) , alora ${\mathcal {R}}(x)\cap {\mathcal {R}}(y)=\varnothing$

Autrament dich, doas classas d'equivaléncia son siá egalas siá desjonchas

• Tot element de E apartèn a una classa d'equivaléncia, e apartèn ren qu'a una classa d'equivaléncia (la sieuna)

Se pòt sintetizar tot aiçò ansin : l'ensemble dei classas d'equivaléncia modulo ${\mathcal {R}}$ es una particion de l'ensemble E.

demostracion :

• Se ${\mathcal {C}}$ es una classa d'equivaléncia, existís $x\in E$ tau que ${\mathcal {R}}(x)={\mathcal {C}}$ . Coma $x{\mathcal {R}}x$ (reflexivitat), $x\in {\mathcal {R}}(x)$ : x es element de ${\mathcal {C}}$ .

• Supausem que $y\in {\mathcal {R}}(x)$ , valent a dire : $x{\mathcal {R}}y$ . Per transitivitat de ${\mathcal {R}}$ :
  • tot element z de E qu'es equivalent a x es equivalent a y ; aiçò significa que : ${\mathcal {R}}(x)\subset {\mathcal {R}}(y)$
  • reciprocament, tot element z de E qu'es equivalent a y es equivalent a x : ${\mathcal {R}}(y)\subset {\mathcal {R}}(x)$
  • Ansin, lei doas inclusions de sens contrari pròvan l'egalitat : ${\mathcal {R}}(x)={\mathcal {R}}(y)$ .

• Supausem que $y\notin {\mathcal {R}}(x)$ : x, y son pas equivalents. Existiguèsse un element z comun a ${\mathcal {R}}(x)$ e ${\mathcal {R}}(y)$ , aquò implicariá : $x{\mathcal {R}}z$ e $y{\mathcal {R}}z$ , donc per simetria e transitivitat : $x{\mathcal {R}}y$ , còntradisent l'ipotèsi.
  Ansin lei doas classas ${\mathcal {R}}(x)$ , ${\mathcal {R}}(y)$ son desjonchas.

• S'es vist supra que $x\in {\mathcal {R}}(x)$ ; coma doas classas non desjonchas son egalas, la classa ${\mathcal {C}}={\mathcal {R}}(x)$ es la soleta que contèn x.

Ensemble quocient

Siá ${\mathcal {R}}$ una relacion d'equivaléncia dins un ensemble E.

Definicion

L'ensemble quocient de l'ensemble E per la relacion d'equivaléncia ${\mathcal {R}}$ es l'ensemble dei classas d'equivaléncia modulo ${\mathcal {R}}$ , notat : $E/{\mathcal {R}}$ .

$E/{\mathcal {R}}=\{{\mathcal {R}}(x)\mid x\in E\}$

Informalament, de passar de l'ensemble E a l'ensemble quocient $E/{\mathcal {R}}$ consistís a identificar, per cada classa ${\mathcal {C}}$ d'equivaléncia modulo ${\mathcal {R}}$ , totei leis elements d'aquesta classa : se considèra que leis elements de ${\mathcal {C}}$ ne fan plus qu'un. Es tipicament un procès d'abstraccion.

La nocion d'ensemble quocient es fondamentala en matematicas per la construccion d'ensembles novèus.

La subrejeccion canonica

Se definís l'aplicacion seguenta, qu'en tot element x de E, associa sa classa d'equivaléncia :

$\pi :E\to E/{\mathcal {R}},x\mapsto {\mathcal {R}}(x)$

L'aplicacion ansin definida es subrejectiva (se ${\mathcal {C}}$ es element de $E/{\mathcal {R}}$ , existís aumens un element x de E tau que ${\mathcal {R}}(x)={\mathcal {C}}$ , autrament dich : $\pi (x)={\mathcal {C}})$ . L'aplicacion $\ \pi$ es sonada subrejeccion canonica de E vèrs l'ensemble quocient $E/{\mathcal {R}}$ .

Proprietat

Estent dos elements x, y de E :

$\pi (x)=\pi (y)\iff x{\mathcal {R}}y$

D'efècte, $\pi (x)=\pi (y)\iff {\mathcal {R}}(x)={\mathcal {R}}(y)$ , e ${\mathcal {R}}(x)={\mathcal {R}}(y)\iff x{\mathcal {R}}y$ , car dos elements de E an la meteissa classa se e solament se son equivalents.

La proprietat universala de l'ensemble quocient

Sián E, F dos ensembles, ${\mathcal {R}}$ una relacion d'equivaléncia dins E, e $\pi :E\to E/{\mathcal {R}}$ la subrejeccion canonica.

• Se $g:E/{\mathcal {R}}\to F$ es una aplicacion e se $f=g\circ \pi :E\to F$ , alora per tot pareu (x, y) d'elements de E :

$x{\mathcal {R}}y$ implica $\ f(x)=f(y)$ : se ditz que f es constanta subre cada classa d'equivaléncia.

• Reciprocament, siá $f:E\to F$ una aplicacion tala que per tot pareu (x, y) d'elements de E :

$x{\mathcal {R}}y$ implica $\ f(x)=f(y)$ .

Alora, existís una aplicacion unica $g:E/{\mathcal {R}}\to F$ tala que $f=g\circ \pi$ .

demostracion :

A) Coma $f=g\circ \pi$ , per tot pareu (x, y) d'elements de E : $\ f(x)=g(\pi (x))$ e $f(y)=g(\pi (y))\quad (1)$ .

Se $x{\mathcal {R}}y$ , alora $\ \pi (x)=\pi (y)$ : resulta de la relacion (1) que : $\ f(x)=f(y)$ .

B) Recipròca.

• Demostrem premier l'unicitat de l'aplicacion g. S'existís $g:E/{\mathcal {R}}\to F$ tala que $f=g\circ \pi$ , e se ${\mathcal {C}}$ es un element de $E/{\mathcal {R}}$ , se pòt trobar (aumens) un element x de E tau que $\pi (x)={\mathcal {C}}$ . Alora, necessariament :

$g({\mathcal {C}})=g(\pi (x))=(g\circ \pi )(x)=f(x)$ : la soleta valor possibla de g en ${\mathcal {C}}$ es f(x), çò que pròva l'unicitat de g.

• Demostrem ara l'existéncia de l'aplicacion g. Venèm de veire que necessariament, per tot element ${\mathcal {C}}$ de $E/{\mathcal {R}}$ :

$g({\mathcal {C}})=f(x)$ , se x es un element de E chausit tau que $\pi (x)={\mathcal {C}}$ ;

sufís de mostrar qu'aiçò definís $g({\mathcal {C}})$ sens ambigüitat, valent a dire que lo segond membre f(x) de l'egalitat depende pas de l'element x qu'es estat chausit.

D'efècte, se remplaçam l'element x de E tau que $\pi (x)={\mathcal {C}}$ per un autre element y de E, tau que $\pi (y)={\mathcal {C}}$ , alora $\ \pi (x)=\pi (y)$, valent a dire $x{\mathcal {R}}y$ , donc per ipotèsi, $\ f(x)=f(y)$ . Aiçò pròva qu'una aplicacion $g:E/{\mathcal {R}}\to F$ es estada definida.

Enfin, còmpte tengut de la definicion de g, per tot element x de E, $(g\circ \pi )(x)=g(\pi (x))=g({\mathcal {C}})$ , onte ${\mathcal {C}}=\pi (x)$ , donc $(g\circ \pi )(x)=f(x)$ (vejatz supra : $g({\mathcal {C}})=f(x)$ ), çò que pròva l'egalitat $g\circ \pi =f$ , e acaba la demostracion.

Exemples

• La congruéncia modulo 3 (se pòt remplaçar 3 per tot autre entier naturau estrictament positiu). Se ditz qu'un element a de l'ensemble $\mathbb {Z}$ deis entiers es multiple de 3 s'existís un element b de $\mathbb {Z}$ tau que a = 3 b (per exemple, −6, 0, +15 son de multiples de 3). Se definís dins l'ensemble $\mathbb {Z}$ una relacion binària (sonada congruéncia modulo 3): estent dos entiers n, p, escriurem :

$n\equiv p\;[3]$ (legir : n es congru a p modulo 3) se e solament se $\ n-p$ es multiple de 3, valent a dire :

$n\equiv p\;[3]\;\iff \exists k\in \mathbb {Z}$ tau que $\ n-p=3k$ .

Aquesta relacion binària es una relacion d'equivaléncia dins $\mathbb {Z}$ :

per tot $n\in \mathbb {Z}$ , $n-n=0=3\cdot 0$ , e $0\in \mathbb {Z}$ :

donc $n\equiv n\;[3]$ (reflexivitat)

se $(n,\,p)\in \mathbb {Z} ^{2}$ e $n\equiv p\;[3]$ , $\exists k\in \mathbb {Z}$ tau que $\ n-p=3k$ ; alora $p-n=3\cdot (-k)$ , e $-k\in \mathbb {Z}$ :

donc $p\equiv n\;[3]$ (simetria)

se $(n,\,p,\,q)\in \mathbb {Z} ^{3}$ e $n\equiv p\;[3]$ , $p\equiv q\;[3]$ : $\exists k\in \mathbb {Z}$ tau que $\ n-p=3k$ , $\exists \ell \in \mathbb {Z}$ tau que $\ p-q=3\ell$ . Alora, $\ n-q=(n-p)+(p-q)=3k+3\ell =3(k+\ell )$ , e $k+\ell \in \mathbb {Z}$  :

donc $n\equiv q\;[3]$ (transitivitat)

Tot entier n se pòt escriure d'un solet biais sota la forma : $\ n=3q+r$ , onte q es un entier e $r\in \{0,\,1,\,2\}$ : se ditz que q (respectivament r) es lo quocient (respectivament la rèsta) de la division euclidiana de n per 3 ; per exemple, se n = 17 : q = 5 e r = 2.

Alora, $\ n-r=3q$ , donc $n\equiv r\;[3]$ : estent dos entiers n, p : $n\equiv p\;[3]$ se e solament se n, p an la meteissa rèsta dins la division euclidiana per 3.

Ansin, i a exactament tres possibilitats :

1. se r = 0, $n\equiv 0\;[3]$
2. se r = 1, $n\equiv 1\;[3]$
3. se r = 2, $n\equiv 2\;[3]$

Existisson exactament 3 classas d'equivaléncia modulo 3 dins $\mathbb {Z}$ , aquelei de 0, 1, 2, que poirem notar respectivament ${\overline {0}},\,{\overline {1}},\,{\overline {2}}$ :

${\overline {0}}=\{\dots -6,\,-3,\,0,\,3,6\dots \}$ (classa modulo 3 de 0 ; es tanben la classa de 3...)

${\overline {1}}=\{\dots -5,\,-2,\,1,\,4,7\dots \}$ (classa modulo 3 de 1 ; es tanben la classa de 4...)

${\overline {2}}=\{\dots -4,\,-1,\,2,\,5,8\dots \}$ (classa modulo 3 de 2 ; es tanben la classa de 5...)

L'ensemble quocient de $\mathbb {Z}$ per la congruéncia modulo 3, notat abitualament $\mathbb {Z} /3\,\mathbb {Z}$ , es : $\{{\overline {0}},{\overline {1}},{\overline {2}}\}$ .

• Dins l'ensemble E dei drechas dau plan, la relacion binària "aver la meteissa direccion" es una relacion d'equivaléncia. La classa d'equivaléncia d'una drecha d es l'ensemble dei drechas que li son parallèlas (comprés d).

• Un exemple "generic". Sián dos ensembles E, F e una aplicacion $f:E\to F$ . Se definís ansin una relacion binària ${\mathcal {R}}_{f}$ dins E : per tot pareu (x, y) d'elements de E :

$x{\mathcal {R}}_{f}\,y\iff f(x)=f(y)$

Es de bòn veire que ${\mathcal {R}}_{f}$ es una relacion d'equivaléncia dins E ; la classa d'un element x de E es l'ensemble deis elements de E onte f a la meteissa valor qu'en x.

Lo qualificatiu de generic vòu dire que tota relacion d'equivaléncia dins E se pòt definir ansin. D'efècte, se ${\mathcal {R}}$ es una relacion d'equivaléncia dins E, e se $\pi :E\to E/{\mathcal {R}}$ es la subrejeccion canonica, es estat vist que per tot pareu (x, y) d'elements de E :

$x{\mathcal {R}}y\iff \pi (x)=\pi (y)$ . Autrament dich : ${\mathcal {R}}={\mathcal {R}}_{\pi }$

Vejatz tanben

• Aplicacion
• Particion
• Relacion binària