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.

DefinitieBewerken

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

reflexiviteit: voor alle   geldt dat  
symmetrie: voor alle   geldt: als   dan  
transitiviteit: voor alle   geldt: als   en   dan  

Een equivalentierelatie kan ook gedefinieerd worden als een tweeplaatsige relatie   op   met de eigenschap dat:

reflexiviteit: voor alle   geldt dat   en
euclidiciteit: voor alle   geldt: als   en   dan  

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.

VoorbeeldenBewerken

  • De relatie ‘heeft dezelfde absolute waarde’ is een equivalentierelatie op de gehele getallen.
  • De relatie ‘is groter dan’ is geen equivalentierelatie omdat ze niet symmetrisch en 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   (de verzameling van alle identieke koppels van  ) is de kleinst mogelijke equivalentierelatie op  .
  • Het volledige cartesisch product   is de grootst mogelijke equivalentierelatie op  .
  • 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.

EquivalentieklasseBewerken

Als   een equivalentierelatie is op  , heet de deelverzameling van elementen van   die equivalent zijn met het element   de equivalentieklasse   van   onder  :

 

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

EigenschappenBewerken

Zij   een equivalentierelatie op  .

Eigenschap 1Bewerken

Voor alle   geldt dat  . Iedere   zit dus in ten minste één equivalentieklasse van  .

Bewijs

Zij  . Uit de reflexiviteit van   volgt dat  , wat betekent dat  .

Eigenschap 2Bewerken

Voor alle   geldt: als  , dan is  ;   en   zitten dus in dezelfde equivalentieklasse.

Bewijs

Zij  , zodanig dat  . Neem een willekeurig element  , dan is  . Want uit de definitie van equivalentieklasse en dat   volgt dat  . Uit de symmetrie van   en   volgt dat  . Dus is ook  , waaruit volgt dat  . Dit bewijst dat  . Op dezelfde manier, maar dan zonder de symmetrie te gebruiken, is te bewijzen dat  , waaruit volgt dat  . Omdat uit eigenschap 1 volgt dat   en  , betekent dit dat   en   in dezelfde equivalentieklasse zitten.

Eigenschap 3Bewerken

Voor alle   geldt: als   en  , is  . Iedere   zit dus in ten hoogste één equivalentieklasse van  .

Bewijs

Zij   zodanig dat   en  . Uit de definitie van equivalentieklasse volgt dan dat   en  . De symmetrie van   geeft vervolgens  . Nu is dus   en  , waarmee uit de transitiviteit van   af te leiden is dat  . Eigenschap 2 geeft vervolgens dat  .

Eigenschap 4Bewerken

Voor alle   geldt: als   en   in dezelfde equivalentieklasse zitten, staan   en   met elkaar in  -relatie.

Bewijs

Zij   en zowel   als   voor een zekere  . Uit de definitie van equivalentieklasse volgt dat   en  . Uit de symmetrie van   volgt dat ook  , en uit de transitiviteit van   blijkt vervolgens dat  . Op dezelfde manier is te bijwijzen dat  .

Gevolg 1Bewerken

Iedere   zit in precies één equivalentieklasse van  .

Bewijs

Dit volgt direct uit eigenschappen 1 en 3.

Gevolg 2Bewerken

Voor alle   geldt:  , dan en slechts dan als   en   in dezelfde equivalentieklasse zitten.

Bewijs

Dit volgt direct uit eigenschappen 2 en 4.

QuotiëntverzamelingBewerken

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

 

de quotiëntverzameling van   onder  .

Een aantal eigenschappen van quotiëntverzamelingen wordt hieronder bewezen.

Eigenschap 1Bewerken

Van iedere equivalentierelatie   op   is de quotiëntverzameling   een partitie van  

Bewijs

Zij   een equivalentierelatie op  . Uit gevolg 1 in de paragraaf over equivalentieklassen volgt dat iedere   in precies één equivalentieklasse van   zit. Daarbij zitten per definitie van quotiëntverzameling alle equivalentieklassen van   in   en heeft   verder geen elementen. Dan volgt dus dat iedere   in precies één element van   zit. Uit de definitie van equivalentieklasse volgt verder dat er geen elementen   in enige equivalentieklasse van   zitten, wat samen met het voorgaande bewijst dat de vereniging van alle elementen van   gelijk aan   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 2Bewerken

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

Bewijs

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

HoofdstellingBewerken

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

Voor een gegeven partitie   van een verzameling   is de relatie   op  , gedefinieerd door de eis dat voor alle  :

  dan en slechts dan, als er een   waarvoor   en  ,

een equivalentierelatie.

Hulpstelling 1Bewerken

Voor iedere partitie   van   is   een equivalentierelatie op  .

Bewijs

Zij   een partitie van  . We bewijzen dat   reflexief, symmetrisch en transitief is. Zij  . Reflexiviteit en symmetrie volgen direct uit de definitie van  . Neem, om transitiviteit te bewijzen, aan dat   en  . Dat betekent dat er een   is zodanig dat   en een   zodanig dat  . Omdat de klassen van een partitie disjunct zijn en   in zowel   als   zit, volgt dat  . Hieruit volgt per definitie van   dat  .

Hulpstelling 2Bewerken

Gegeven een partitie   van   geldt voor iedere  : als  , is   de equivalentieklasse van   onder  .

Bewijs

Zij   een partitie van   en  . Neem aan dat  . Omdat   een partitie is, is er geen andere klasse   en   waar   in zit. Per definitie van   volgt daarom dat voor alle   geldt:

  dan en slechts dan, als  .

Dat betekent dat

 

en dus dat  .

Stelling 3Bewerken

Iedere partitie   van een verzameling   is de quotiëntverzameling van een equivalentierelatie op  , namelijk van  .

Bewijs

Zij   een partitie van  . Uit hulpstelling 1 volgt dat   een equivalentierelatie is. We bewijzen in twee stappen dat  . Neem ten eerste een willekeurige  . Omdat   een partitie is, is er een  . Uit hulpstelling 2 volgt dan dat  , wat bewijst dat   en dus dat  . Neem ten tweede een willekeurige  . Omdat   een partitie is, volgt dat er precies één   is waarvoor geldt dat  . Uit hulpstelling 2 volgt dan weer dat  , en dus dat  . Dit betekent dat  , waarmee bewezen is dat  .

Hoofdstelling van equivalentierelatiesBewerken

Er is een een-op-een-correspondentie tussen alle equivalentierelaties op een verzameling   en alle partities van dezelfde verzameling  .

Bewijs

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

 
 

een een-op-een-correspondentie tussen   en   is. Uit eigenschap 1 in de paragraaf over quotiëntverzamelingen volgt dat   alle equivalentierelaties in   op een partitie in   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   een equivalentierelatie   is zodanig dat  , oftewel dat   surjectief is. Dit bewijst dat   een een-op-een-correspondentie is.

Geconstrueerde equivalentierelatiesBewerken

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.