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

Voorbeelden[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]

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]

Zij een equivalentierelatie op .

Eigenschap 1[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]

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

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

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

Iedere zit in precies één equivalentieklasse van

Bewijs

Dit volgt direct uit eigenschappen 1 en 3.

Gevolg 2[bewerken]

Voor alle geldt: desda en in dezelfde equivalentieklasse zitten.

Bewijs

Dit volgt direct uit eigenschappen 2 en 4.

Quotiëntverzameling[bewerken]

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

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 2[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 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.

Hoofdstelling[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 een partitie van een verzameling is de relatie op gedefinieerd door de eis dat voor alle :

desda er een is zodanig dat en

Hulpstelling 1[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]

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

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]

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.