title: Equivalentierelatie
text: 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  is een tweeplaatsige relatie  op  met de eigenschappen:
  reflexiviteit: voor alle  geldt: 
  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 eigenschappen:
  reflexiviteit: voor alle  geldt: 
  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 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 , 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.
  
  Equivalentieklasse 
  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 .
  
  Eigenschappen
  Zij  een equivalentierelatie op .
  
  Eigenschap 1
  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 2
  Voor alle  geldt: als , dan is ;  en  zitten dan in dezelfde equivalentieklasse.
  
  Bewijs
  Zij , zodanig dat . Voor elke  geldt: . Maar dan is vanwege de transitiviteit ook , dus . Kennelijk is . Op dezelfde manier is , waaruit volgt dat .
  
  Eigenschap 3
  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 , de transitiviteit dat  en weer de symmetrie dat . Eigenschap 2 geeft vervolgens dat .
  
  Eigenschap 4
  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 bewijzen dat .
  
  Gevolg 1
  Iedere  zit in precies één equivalentieklasse van .
  
  Bewijs 
  Dit volgt direct uit eigenschappen 1 en 3.
  
  Gevolg 2
  Voor alle  geldt: , dan en slechts dan als  en  in dezelfde equivalentieklasse zitten.
  
  Bewijs 
  Dit volgt direct uit eigenschappen 2 en 4.
  
  Quotiëntverzameling 
  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 1
  De quotiëntverzameling  van een equivalentierelatie  op een verzameling  is een partitie van 
  
  Bewijs 
  Zij  een equivalentierelatie op . Gevolg 1 in de paragraaf over equivalentieklassen stelt dat iedere  in precies een equivalentieklasse van  zit, dus in precies een element van . 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 2
  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.
  
  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  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 1
  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 2
  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
   
  dus dat .
  
  Stelling 3
  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 , dus dat . Neem ten tweede een willekeurige . Omdat  een partitie is, volgt dat er precies een  is waarvoor geldt dat . Uit hulpstelling 2 volgt dan weer dat , dus dat . Dit betekent dat , waarmee bewezen is dat .
  
  Hoofdstelling van equivalentierelaties
  Er is een bijectie 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 bijectie 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 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.
  
  Relaties op verzamelingen