Loading AI tools
Van Wikipedia, de vrije encyclopedie
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.
Een equivalentierelatie op een verzameling is een tweeplaatsige relatie op met de eigenschappen:
Een equivalentierelatie kan ook gedefinieerd worden als een tweeplaatsige relatie op met de eigenschappen:
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.
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 .
Zij een equivalentierelatie op .
Voor alle geldt dat . Iedere zit dus in ten minste één equivalentieklasse van .
Zij . Uit de reflexiviteit van volgt dat , wat betekent dat .
Voor alle geldt: als , dan is ; en zitten dan in dezelfde equivalentieklasse.
Zij , zodanig dat . Voor elke geldt: . Maar dan is vanwege de transitiviteit ook , dus . Kennelijk is . Op dezelfde manier is , waaruit volgt dat .
Voor alle geldt: als en , is . Iedere zit dus in ten hoogste één equivalentieklasse van .
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 .
Voor alle geldt: als en in dezelfde equivalentieklasse zitten, staan en met elkaar in -relatie.
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 .
Iedere zit in precies één equivalentieklasse van .
Dit volgt direct uit eigenschappen 1 en 3.
Voor alle geldt: , dan en slechts dan als en in dezelfde equivalentieklasse zitten.
Dit volgt direct uit eigenschappen 2 en 4.
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.
De quotiëntverzameling van een equivalentierelatie op een verzameling is een partitie van
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.
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.
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.
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 :
een equivalentierelatie.
Voor iedere partitie van is een equivalentierelatie op .
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 .
Gegeven een partitie van geldt voor iedere : als , is de equivalentieklasse van onder .
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:
Dat betekent dat
dus dat .
Iedere partitie van een verzameling is de quotiëntverzameling van een equivalentierelatie op , namelijk van .
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 .
Er is een bijectie tussen alle equivalentierelaties op een verzameling en alle partities van dezelfde verzameling .
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.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.