Hoofdmenu openen
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. 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.

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   waarvoor geldt 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   en zitten   en   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 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 dat als   en   dan is   Iedere   zit dus in ten hoogste één equivalentieklasse van  

Bewijs

Zij   zodanig dat   en   Uit de definitie van equivalentieklasse volgt dan dat   en   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, dan 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   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:   desda   en   in dezelfde equivalentieklasse zitten.

Bewijs

Dit volgt direct uit eigenschappen 2 en 4.

QuotiëntverzamelingBewerken

Als   een equivalentierelatie op   is, dan is 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   desda   Stel, ten eerste, dat   Uit eigenschap 2 van equivalentieklassen blijkt dat   en   in dezelfde equivalentieklasse   zitten. Omdat   ie   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   desda   Hieruit volgt dat   waarmee bewezen is dat als ze dezelfde quotiëntverzameling hebben,   en   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 een partitie   van een verzameling   is de relatie   op   gedefinieerd door de eis dat voor alle  :

  desda er een   is zodanig dat   en  

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   dan 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:

  desda  

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.