Equivalentierelatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Schematische weergave van een equivalentierelatie

In de wiskunde is een equivalentierelatie een tweeplaatsige relatie die alle elementen uit een verzameling die in bepaalde zin gelijkwaardig zijn aan elkaar, aan elkaar koppelt. Aldus deelt een equivalentierelatie 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[bewerken]

Een equivalentierelatie op een verzameling X is een tweeplaatsige relatie ~ op X waarvoor geldt dat:

(reflexiviteit) voor alle x \in X geldt dat x ~ x,
(symmetrie) voor alle xy \in X geldt: als x ~ y dan y ~ x,
(transitiviteit) voor alle xyz \in X geldt: als x ~ y en y ~ z dan x ~ z.

Een equivalentierelatie kan ook gedefinieerd worden als een tweeplaatsige relatie ~ op X waarvoor geldt dat:

(reflexiviteit) voor alle x \in X geldt dat x ~ x en
(Euclidiciteit) voor alle xyz \in X geldt: als x ~ y en x ~ z, dan y ~ z.

De beide definities zijn equivalent. Dat wil zeggen: als ~ een equivalentierelatie is volgens de eerste definitie, dan is ~ ook een equivalentierelatie volgens de tweede definitie en vice versa.

Voorbeelden[bewerken]

  • De relatie ‘heeft dezelfde absolute waarde’ is een equivalentierelatie op de gehele getallen.
  • De relatie ‘is groter dan’ is géén equivalentierelatie omdat ze niet symmetrisch en reflexief is.
  • De relatie ‘is gehuwd met’ is géén 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 géén 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 × 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[bewerken]

Als ~ een equivalentierelatie op X is en x \in X, dan is

[x]~ = { y \in X | x ~ y }

de equivalentieklasse van x onder ~. Er wordt ook gezegd dat [x]~ een equivalentieklasse van X is onder ~. Als uit de context duidelijk is welke equivalentierelatie bedoeld wordt, dan wordt meestal [x] in plaats van [x]~ geschreven.

Een aantal eigenschappen van equivalentieklassen wordt hieronder bewezen.

Zij ~ 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 ~ volgt dat x ~ x, wat betekent dat x \in [x].

Eigenschap 2
Voor alle xy \in X geldt: als x ~ y dan [x] = [y] en zitten x en y dus in dezelfde equivalentieklasse.

(Bewijs) Zij xy \in X zodanig dat x ~ y. We nemen een willekeurig element u \in [x] en bewijzen dat u \in [y]. Uit de definitie van equivalentieklasse en u \in [x] volgt dat x ~ u. Uit de symmetrie van ~ en x ~ y volgt dat y ~ x. Nu weten we dus dat y ~ x en x ~ u. Omdat ~ transitief is weten we dan ook dat y ~ u, waaruit per definitie volgt dat u \in [y]. Dit bewijst dat [x\subseteq [y]. Op dezelfde manier, maar dan zonder symmetrie te gebruiken, is te bewijzen dat [y\subseteq [x], waaruit volgt dat [x] = [y]. Omdat we uit eigenschap 1 weten dat x \in [x] en y \in [y], betekent dit dat x en y in dezelfde equivalentieklasse zitten.

Eigenschap 3
Voor alle xyz \in X geldt dat als x \in [y] en x \in [z] dan [y] = [z]. Iedere x \in X zit dus in ten hoogste één equivalentieklasse van X.

(Bewijs) Zij xyz \in X zodanig dat x \in [y] en x \in [z]. Uit de definitie van equivalentieklasse volgt dan dat y ~ x en z ~ x. Symmetrie van ~ geeft vervolgens x ~ z. Nu hebben we dus y ~ x en x ~ z, waarmee uit de transitiviteit van ~ af te leiden is dat y ~ z. Eigenschap 2 geeft vervolgens dat [y] = [z].

Eigenschap 4
Voor alle xy \in X geldt: als x en y in dezelfde equivalentieklasse zitten dan staan x en y met elkaar in ~-relatie.

(Bewijs) Zij xy \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 ~ x en u ~ y. Uit de symmetrie van ~ volgt dat ook x ~ u. Door de transitiviteit van ~ weten we vervolgens dat x ~ y. Op dezelfde manier is te bijwijzen dat y ~ 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 xy \in X geldt: x ~ y desda x en y in dezelfde equivalentieklasse zitten.

(Bewijs) Dit volgt direct uit eigenschappen 2 en 4.

Quotiëntverzameling[bewerken]

Als ~ een equivalentierelatie op X is, dan is de verzameling van alle equivalentieklassen van X

X/~ = { [x] | x \in X }

de quotiëntverzameling van X onder ~.

Een aantal eigenschappen van quotiëntverzamelingen wordt hieronder bewezen.

Eigenschap 1
Van iedere equivalentierelatie ~ op X is de quotiëntverzameling X/~ een partitie van X.

(Bewijs) Zij ~ een equivalentierelatie op X. Uit gevolg 1 in de paragraaf over equivalentieklassen volgt dat iedere x \in X in precies één equivalentieklasse van X zit. Daarbij zitten per definitie van quotiëntverzameling alle equivalentieklassen van X in X/~ en heeft X/~ verder geen elementen. Dan volgt dus dat iedere x \in X in precies één element van X/~ zit. 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/~ 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. We nemen twee willekeurige elementen x, y \in X en bewijzen in twee stappen dat xRy desda xSy. Stel, ten eerste, dat xRy. Uit eigenschap 2 van equivalentieklassen weten we dat x en y in dezelfde equivalentieklasse K \in X/R zitten. Omdat X/R = X/S weten we dat K \in X/S, wat betekent dat x en y ook onder S in dezelfde equivalentieklasse zitten. Daaruit volgt, door eigenschap 4 van equivalentieklassen, dat xSy. Ten tweede is op dezelfde manier te bewijzen dat uit xSy volgt dat xRy. Uit deze twee stappen volgt dat xRy desda xSy. Hieruit leiden we af dat R = S, waarmee bewezen is dat wanneer ze dezelfde quotiëntverzameling hebben, R en S dezelfde equivalentierelatie zijn.

Hoofdstelling[bewerken]

Er is een diepe overeenkomst tussen equivalentierelaties op en partities van een verzameling. Deze wordt uitgedrukt in de hoofdstelling van equivalentierelaties.

Gegeven een partitie P van een verzameling X definiëren we de relatie ~P op X, waarvoor geldt dat voor alle xy \in X:

x ~Py desda er een K \in P is zodanig dat x \in K en y \in K.
Hulpstelling 1
Voor iedere partitie P van X is ~P een equivalentierelatie op X.

(Bewijs) Zij P een partitie van X. We bewijzen dat ~P reflexief, symmetrisch en transitief is. Zij xyz \in X. Reflexiviteit en symmetrie volgen direct uit de definitie van ~P. Neem, om transitiviteit te bewijzen, aan dat x ~Py en y ~Pz. Dat betekent dat er een K \in P is zodanig dat xy \in K en een L \in P zodanig dat yz \in L. Omdat de klassen van een partitie disjunct zijn en y in zowel K als L zit, weten we dat K = L. Hieruit volgt per definitie van ~P dat x ~Pz.

Hulpstelling 2
Gegeven een partitie P van X geldt voor iedere K \in P: als x \in K dan is K de equivalentieklasse van x onder ~P.

(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 ≠ K waar x in zit. Per definitie van ~P volgt daarom dat voor alle y \in X geldt:

x ~Py desda y \in K.

Dat betekent dat

K = { y \in X | x ~Py }

en dus dat K = [x].

Stelling 3
Iedere partitie P van een verzameling X is de quotiëntverzameling van een equivalentierelatie op X, namelijk van ~P.

(Bewijs) Zij P een partitie van X. Uit hulpstelling 1 volgt dat ~P een equivalentierelatie is. We bewijzen in twee stappen dat X/~P = 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/~P en dus dat P \subseteq X/~P. Neem ten tweede een willekeurige [x\in X/~P. Omdat P een partitie is weten we dat er precies één K \in P is waarvoor geldt dat x \in K. Uit hulpstelling 2 volgt dan wederom dat K = [x] en dus dat [x\in P. Dit betekent dat X/~P \subseteq P, waarmee bewezen is dat X/~P = P.

Hoofdstelling van equivalentierelaties
Er is een één-op-één-correspondentie tussen alle equivalentierelaties op een verzameling X en alle partities van dezelfde verzameling X.

(Bewijs) Gegeven een verzameling X, zij A de verzameling van alle equivalentierelaties op X en B de verzameling van alle partities van X. We bewijzen dat de afbeelding

α : A → B
α : R \mapsto X/R

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

Geconstrueerde equivalentierelaties[bewerken]

De doorsnede van een willekeurige familie equivalentierelaties op dezelfde verzameling, is opnieuw een equivalentierelatie. Hierdoor bestaat voor elke relatie een unieke kleinste equivalentierelatie die de gegeven relatie omvat.