Equivalentierelatie

Schematische weergave van een equivalentierelatie

In de wiskunde is een equivalentierelatie een tweeplaatsige relatie die alle elementen uit een verzameling die in bepaalde zin aan elkaar gelijkwaardig zijn, aan elkaar koppelt. Een equivalentierelatie deelt de verzameling op in klassen van elementen die gelijkwaardig aan elkaar zijn. Op dezelfde dag geboren zijn als is bijvoorbeeld een equivalentierelatie, die de verzameling van alle mensen opdeelt in groepen van mensen die op dezelfde dag geboren zijn.

Definitie

Een equivalentierelatie op een verzameling $X$ is een tweeplaatsige relatie $\sim$ op $X$ met de eigenschappen:

reflexiviteit: voor alle $x\in X$ geldt: $x\sim x$

symmetrie: voor alle $x,y\in X$ geldt: als $x\sim y$, dan $y\sim x$

transitiviteit: voor alle $x,y,z\in X$ geldt: als $x\sim y$ en $y\sim z$, dan $x\sim z$

Een equivalentierelatie kan ook gedefinieerd worden als een tweeplaatsige relatie $\sim$ op $X$ met de eigenschappen:

reflexiviteit: voor alle $x\in X$ geldt: $x\sim x$

euclidiciteit: voor alle $x,y,z\in X$ geldt: als $x\sim y$ en $x\sim z$, dan $y\sim z$

De beide definities zijn equivalent. Dat wil zeggen: als $\sim$ een equivalentierelatie is volgens de eerste definitie, dan is $\sim$ ook een equivalentierelatie volgens de tweede definitie en omgekeerd.

Voorbeelden

• De relatie ‘heeft dezelfde absolute waarde’ is een equivalentierelatie op de gehele getallen.
• De relatie ‘is groter dan’ is geen equivalentierelatie omdat ze noch symmetrisch, noch reflexief is.
• De relatie ‘is gehuwd met’ is geen equivalentierelatie op de verzameling van alle mensen, omdat ze niet reflexief is.
• De relatie ‘is gelijkvormig met’ is een equivalentierelatie op de verzameling van alle driehoeken in een vlak.
• De relatie ‘verschilt ten hoogste met één letter van’ is geen equivalentierelatie op de verzameling der Nederlandse woorden, omdat ze niet transitief is.
• De identieke transformatie van $A$, de verzameling van alle identieke koppels van $A$, is de kleinst mogelijke equivalentierelatie op $A$.
• Het volledige cartesisch product $A\times A$ is de grootst mogelijke equivalentierelatie op $A$.
• In een pseudometrische ruimte is de relatie ‘heeft afstand 0 tot‘ een equivalentierelatie. De transitiviteit volgt uit de driehoeksongelijkheid.
• De relatie ‘maakt deel uit van hetzelfde huishouden‘ is een equivalentierelatie op de verzameling personen.

Equivalentieklasse

Als $\sim$ een equivalentierelatie is op $X$, heet de deelverzameling van elementen van $y\in X$ die equivalent zijn met het element $x\in X$, de equivalentieklasse $[x{]}_{\sim }$ van $x$ onder $\sim$:

$[x{]}_{\sim }=\{y\in X\mid y\sim x\}$

Als uit de context duidelijk is welke equivalentierelatie wordt bedoeld, wordt meestal eenvoudig $[x]$ geschreven voor de equivalentieklasse van $x$.

Eigenschappen

Zij $\sim$ een equivalentierelatie op $X$.

Eigenschap 1

Voor alle $x\in X$ geldt dat $x\in [x]$. Iedere $x\in X$ zit dus in ten minste één equivalentieklasse van $X$.

Bewijs

Zij $x\in X$. Uit de reflexiviteit van $\sim$ volgt dat $x\sim x$, wat betekent dat $x\in [x]$.

Eigenschap 2

Voor alle $x,y\in X$ geldt: als $x\sim y$, dan is $[x]=[y]$; $x$ en $y$ zitten dan in dezelfde equivalentieklasse.

Bewijs

Zij $x,y\in X$, zodanig dat $x\sim y$. Voor elke $u\in [x]$ geldt: $u\sim x$. Maar dan is vanwege de transitiviteit ook $u\sim y$, dus $u\in [y]$. Kennelijk is $[x]\subseteq [y]$. Op dezelfde manier is $[y]\subseteq [x]$, waaruit volgt dat $[x]=[y]$.

Eigenschap 3

Voor alle $x,y,z\in X$ geldt: als $x\in [y]$ en $x\in [z]$, is $[y]=[z]$. Iedere $x\in X$ zit dus in ten hoogste één equivalentieklasse van $X$.

Bewijs

Zij $x,y,z\in X$ zodanig dat $x\in [y]$ en $x\in [z]$. Uit de definitie van equivalentieklasse volgt dan dat $y\sim x$ en $z\sim x$. De symmetrie van $\sim$ geeft $x\sim z$, de transitiviteit dat $y\sim z$ en weer de symmetrie dat $z\sim y$. Eigenschap 2 geeft vervolgens dat $[y]=[z]$.

Eigenschap 4

Voor alle $x,y\in X$ geldt: als $x$ en $y$ in dezelfde equivalentieklasse zitten, staan $x$ en $y$ met elkaar in $\sim$-relatie.

Bewijs

Zij $x,y\in X$ en zowel $x\in [u]$ als $y\in [u]$ voor een zekere $u\in X$. Uit de definitie van equivalentieklasse volgt dat $u\sim x$ en $u\sim y$. Uit de symmetrie van $\sim$ volgt dat ook $x\sim u$, en uit de transitiviteit van $\sim$ blijkt vervolgens dat $x\sim y$. Op dezelfde manier is te bewijzen dat $y\sim x$.

Gevolg 1

Iedere $x\in X$ zit in precies één equivalentieklasse van $X$.

Bewijs

Dit volgt direct uit eigenschappen 1 en 3.

Gevolg 2

Voor alle $x,y\in X$ geldt: $x\sim y$, dan en slechts dan als $x$ en $y$ in dezelfde equivalentieklasse zitten.

Bewijs

Dit volgt direct uit eigenschappen 2 en 4.

Quotiëntverzameling

Als $\sim$ een equivalentierelatie op $X$ is, dan heet de verzameling van alle equivalentieklassen van $X$

$X/\sim =\{[x]\mid x\in X\}$

de quotiëntverzameling van $X$ onder $\sim$.

Een aantal eigenschappen van quotiëntverzamelingen wordt hieronder bewezen.

Eigenschap 1

De quotiëntverzameling $X/\sim$ van een equivalentierelatie $\sim$ op een verzameling $X$ is een partitie van $X.$

Bewijs

Zij $\sim$ een equivalentierelatie op $X$. Gevolg 1 in de paragraaf over equivalentieklassen stelt dat iedere $x\in X$ in precies een equivalentieklasse van $X$ zit, dus in precies een element van $X/\sim$. Uit de definitie van equivalentieklasse volgt verder dat er geen elementen $u\notin X$ in enige equivalentieklasse van $X$ zitten, wat samen met het voorgaande bewijst dat de vereniging van alle elementen van $X/\sim$ gelijk aan $X$ is. De lege verzameling, ten slotte, is geen element van de quotiëntverzameling. In de quotiëntverzameling zitten immers enkel equivalentieklassen en uit eigenschap 1 van equivalentieklassen volgt dat die altijd ten minste één element hebben.

Eigenschap 2

Iedere equivalentierelatie op $X$ levert een unieke quotiëntverzameling op. Er zijn, met andere woorden, geen twee verschillende equivalentierelaties op $X$ die dezelfde quotiëntverzameling van $X$ opleveren.

Bewijs

Zij $R$ en $S$ twee equivalentierelaties op $X$ waarvoor geldt dat $X/R=X/S$. Voor twee willekeurige elementen $x,y\in X$ volgt in twee stappen dat $xRy$ dan en slechts dan, als $xSy$. Stel, ten eerste, dat $xRy$. Uit eigenschap 2 van de equivalentieklassen blijkt dat $x$ en $y$ in dezelfde equivalentieklasse $K\in X/R$ zitten. Omdat $X/R=X/S$ is $K\in X/S$, wat betekent dat $x$ en $y$ ook onder $S$ in dezelfde equivalentieklasse zitten. Daaruit volgt, m.b.v. eigenschap 4 van equivalentieklassen, dat $xSy$. Ten tweede is op dezelfde manier te bewijzen dat uit $xSy$ volgt dat $xRy$. Uit deze twee stappen blijkt dat $xRy$ dan en slechts dan, als $xSy$. Hieruit volgt dat $R=S$, waarmee bewezen is dat als $R$ en $S$ dezelfde quotiëntverzameling hebben, ze dezelfde equivalentierelatie zijn.

Hoofdstelling

Er is een overeenkomst, een bijectie tussen de equivalentierelaties op en de partities van een verzameling. Dit verband wordt uitgedrukt door de hoofdstelling van equivalentierelaties.

Voor een gegeven partitie $P$ van een verzameling $X$ is de relatie $\sim$ op $X$, gedefinieerd door de eis dat voor alle $x,y\in X$:

$x\sim y$ dan en slechts dan, als er een $K\in P$ waarvoor $x\in K$ en $y\in K$,

een equivalentierelatie.

Hulpstelling 1

Voor iedere partitie $P$ van $X$ is $\sim$ een equivalentierelatie op $X$.

Bewijs

Zij $P$ een partitie van $X$. We bewijzen dat $\sim$ reflexief, symmetrisch en transitief is. Zij $x,y,z\in X$. Reflexiviteit en symmetrie volgen direct uit de definitie van $\sim$. Neem, om transitiviteit te bewijzen, aan dat $x\sim y$ en $y\sim z$. Dat betekent dat er een $K\in P$ is zodanig dat $x,y\in K$ en een $L\in P$ zodanig dat $y,z\in L$. Omdat de klassen van een partitie disjunct zijn en $y$ in zowel $K$ als $L$ zit, volgt dat $K=L$. Hieruit volgt per definitie van $\sim$ dat $x\sim z$.

Hulpstelling 2

Gegeven een partitie $P$ van $X$ geldt voor iedere $K\in P$: als $x\in K$, is $K$ de equivalentieklasse van $x$ onder $\sim$.

Bewijs

Zij $P$ een partitie van $X$ en $K\in P$. Neem aan dat $x\in K$. Omdat $P$ een partitie is, is er geen andere klasse $L\in P$ en $L\ne K$ waar $X$ in zit. Per definitie van $\sim$ volgt daarom dat voor alle $y\in X$ geldt:

$x\sim y$ dan en slechts dan, als $y\in K$.

Dat betekent dat

$K=\{y\in X\mid x\sim y\}$

dus dat $K=[x]$.

Stelling 3

Iedere partitie $P$ van een verzameling $X$ is de quotiëntverzameling van een equivalentierelatie op $X$, namelijk van $\sim$.

Bewijs

Zij $P$ een partitie van $X$. Uit hulpstelling 1 volgt dat $\sim$ een equivalentierelatie is. We bewijzen in twee stappen dat $X/\sim =P$. Neem ten eerste een willekeurige $K\in P$. Omdat $P$ een partitie is, is er een $x\in K$. Uit hulpstelling 2 volgt dan dat $K=[x]$, wat bewijst dat $K\in X/\sim$, dus dat $P\subseteq X/\sim$. Neem ten tweede een willekeurige $[x]\in X/\sim$. Omdat $P$ een partitie is, volgt dat er precies een $K\in P$ is waarvoor geldt dat $x\in K$. Uit hulpstelling 2 volgt dan weer dat $K=[x]$, dus dat $[x]\in P$. Dit betekent dat $X/\sim \subseteq P$, waarmee bewezen is dat $X/\sim =P$.

Hoofdstelling van equivalentierelaties

Er is een bijectie tussen alle equivalentierelaties op een verzameling $X$ en alle partities van dezelfde verzameling $X$.

Bewijs

Gegeven een verzameling $X$, laat $A$ de verzameling zijn van alle equivalentierelaties op $X$ en $B$ de verzameling van alle partities van $X$. We bewijzen dat de afbeelding

$\alpha :A\to B$

$\alpha :R\mapsto X/R$

een bijectie tussen $A$ en $B$ is. Uit eigenschap 1 in de paragraaf over quotiëntverzamelingen volgt dat $\alpha$ alle equivalentierelaties in $A$ op een partitie in $B$ afbeeldt. Met andere woorden: $\alpha$ is een volledige afbeelding. Uit eigenschap 2 in dezelfde paragraaf volgt dat $\alpha$ injectief is. Stelling 3 bewijst dat er voor iedere partitie $P\in B$ een equivalentierelatie $R\in A$ is zodanig dat $\alpha (R)=P$, oftewel dat $\alpha$ surjectief is. Dit bewijst dat $\alpha$ een bijectie is.

Geconstrueerde equivalentierelaties

De doorsnede van een willekeurige familie equivalentierelaties op dezelfde verzameling, is opnieuw een equivalentierelatie. Dat kan niet anders, omdat iedere equivalentierelatie reflexief is. Hierdoor bestaat voor elke relatie een unieke kleinste equivalentierelatie die de gegeven relatie omvat.