Equivalentierelatie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
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[bewerken | brontekst bewerken]

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.

Voorbeelden[bewerken | brontekst bewerken]

  • 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.

Equivalentieklasse[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

Zij een equivalentierelatie op .

Eigenschap 1[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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 3[bewerken | brontekst bewerken]

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 4[bewerken | brontekst bewerken]

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 1[bewerken | brontekst bewerken]

Iedere zit in precies één equivalentieklasse van .

Bewijs

Dit volgt direct uit eigenschappen 1 en 3.

Gevolg 2[bewerken | brontekst bewerken]

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

Bewijs

Dit volgt direct uit eigenschappen 2 en 4.

Quotiëntverzameling[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

De quotiëntverzameling van een equivalentierelatie op een verzameling is 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 2[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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 1[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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 3[bewerken | brontekst bewerken]

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 equivalentierelaties[bewerken | brontekst bewerken]

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 equivalentierelaties[bewerken | brontekst 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.