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.

Inhoud

Definitie


Een equivalentierelatie op een verzameling \({\displaystyle X}\) is een tweeplaatsige relatie \({\displaystyle \sim }\) op \({\displaystyle X}\) waarvoor geldt dat:

reflexiviteit: voor alle \({\displaystyle x\in X}\) geldt dat \({\displaystyle x\sim x}\)
symmetrie: voor alle \({\displaystyle x,y\in X}\) geldt: als \({\displaystyle x\sim y}\) dan \({\displaystyle y\sim x}\)
transitiviteit: voor alle \({\displaystyle x,y,z\in X}\) geldt: als \({\displaystyle x\sim y}\) en \({\displaystyle y\sim z}\) dan \({\displaystyle x\sim z}\)

Een equivalentierelatie kan ook gedefinieerd worden als een tweeplaatsige relatie \({\displaystyle \sim }\) op \({\displaystyle X}\) met de eigenschap dat:

reflexiviteit: voor alle \({\displaystyle x\in X}\) geldt dat \({\displaystyle x\sim x}\) en
euclidiciteit: voor alle \({\displaystyle x,y,z\in X}\) geldt: als \({\displaystyle x\sim y}\) en \({\displaystyle x\sim z,}\) dan \({\displaystyle y\sim z}\)

De beide definities zijn equivalent. Dat wil zeggen: als \({\displaystyle \sim }\) een equivalentierelatie is volgens de eerste definitie, dan is \({\displaystyle \sim }\) ook een equivalentierelatie volgens de tweede definitie en vice versa.

Voorbeelden


Equivalentieklasse


Als \({\displaystyle \sim }\) een equivalentierelatie is op \({\displaystyle X}\), heet de deelverzameling van elementen van \({\displaystyle y\in X}\) die equivalent zijn met het element \({\displaystyle x\in X}\) de equivalentieklasse \({\displaystyle [x]_{\sim }}\) van \({\displaystyle x}\) onder \({\displaystyle \sim }\):

\({\displaystyle [x]_{\sim }=\{y\in X\mid y\sim x\}}\)

Als uit de context duidelijk is welke equivalentierelatie wordt bedoeld, wordt meestal eenvoudig \({\displaystyle [x]}\) geschreven voor de equivalentieklasse van \({\displaystyle x}\).

Eigenschappen


Zij \({\displaystyle \sim }\) een equivalentierelatie op \({\displaystyle X}\).

Eigenschap 1

Voor alle \({\displaystyle x\in X}\) geldt dat \({\displaystyle x\in [x]}\). Iedere \({\displaystyle x\in X}\) zit dus in ten minste één equivalentieklasse van \({\displaystyle X}\).

Bewijs

Zij \({\displaystyle x\in X}\). Uit de reflexiviteit van \({\displaystyle \sim }\) volgt dat \({\displaystyle x\sim x}\), wat betekent dat \({\displaystyle x\in [x]}\).

Eigenschap 2

Voor alle \({\displaystyle x,y\in X}\) geldt: als \({\displaystyle x\sim y}\), dan is \({\displaystyle [x]=[y]}\); \({\displaystyle x}\) en \({\displaystyle y}\) zitten dus in dezelfde equivalentieklasse.

Bewijs

Zij \({\displaystyle x,y\in X}\), zodanig dat \({\displaystyle x\sim y}\). Neem een willekeurig element \({\displaystyle u\in [x]}\), dan is \({\displaystyle u\in [y]}\). Want uit de definitie van equivalentieklasse en dat \({\displaystyle u\in [x]}\) volgt dat \({\displaystyle x\sim u}\). Uit de symmetrie van \({\displaystyle \sim }\) en \({\displaystyle x\sim y}\) volgt dat \({\displaystyle y\sim x}\). Dus is ook \({\displaystyle y\sim u}\), waaruit volgt dat \({\displaystyle u\in [y]}\). Dit bewijst dat \({\displaystyle [x]\subseteq [y]}\). Op dezelfde manier, maar dan zonder de symmetrie te gebruiken, is te bewijzen dat \({\displaystyle [y]\subseteq [x]}\), waaruit volgt dat \({\displaystyle [x]=[y]}\). Omdat uit eigenschap 1 volgt dat \({\displaystyle x\in [x]}\) en \({\displaystyle y\in [y]}\), betekent dit dat \({\displaystyle x}\) en \({\displaystyle y}\) in dezelfde equivalentieklasse zitten.

Eigenschap 3

Voor alle \({\displaystyle x,y,z\in X}\) geldt: als \({\displaystyle x\in [y]}\) en \({\displaystyle x\in [z]}\), is \({\displaystyle [y]=[z]}\). Iedere \({\displaystyle x\in X}\) zit dus in ten hoogste één equivalentieklasse van \({\displaystyle X}\).

Bewijs

Zij \({\displaystyle x,y,z\in X}\) zodanig dat \({\displaystyle x\in [y]}\) en \({\displaystyle x\in [z]}\). Uit de definitie van equivalentieklasse volgt dan dat \({\displaystyle y\sim x}\) en \({\displaystyle z\sim x}\). De symmetrie van \({\displaystyle \sim }\) geeft vervolgens \({\displaystyle x\sim z}\). Nu is dus \({\displaystyle y\sim x}\) en \({\displaystyle x\sim z}\), waarmee uit de transitiviteit van \({\displaystyle \sim }\) af te leiden is dat \({\displaystyle y\sim z}\). Eigenschap 2 geeft vervolgens dat \({\displaystyle [y]=[z]}\).

Eigenschap 4

Voor alle \({\displaystyle x,y\in X}\) geldt: als \({\displaystyle x}\) en \({\displaystyle y}\) in dezelfde equivalentieklasse zitten, staan \({\displaystyle x}\) en \({\displaystyle y}\) met elkaar in \({\displaystyle \sim }\)-relatie.

Bewijs

Zij \({\displaystyle x,y\in X}\) en zowel \({\displaystyle x\in [u]}\) als \({\displaystyle y\in [u]}\) voor een zekere \({\displaystyle u\in X}\). Uit de definitie van equivalentieklasse volgt dat \({\displaystyle u\sim x}\) en \({\displaystyle u\sim y}\). Uit de symmetrie van \({\displaystyle \sim }\) volgt dat ook \({\displaystyle x\sim u}\), en uit de transitiviteit van \({\displaystyle \sim }\) blijkt vervolgens dat \({\displaystyle x\sim y}\). Op dezelfde manier is te bijwijzen dat \({\displaystyle y\sim x}\).

Gevolg 1

Iedere \({\displaystyle x\in X}\) zit in precies één equivalentieklasse van \({\displaystyle X}\).

Bewijs

Dit volgt direct uit eigenschappen 1 en 3.

Gevolg 2

Voor alle \({\displaystyle x,y\in X}\) geldt: \({\displaystyle x\sim y}\), dan en slechts dan als \({\displaystyle x}\) en \({\displaystyle y}\) in dezelfde equivalentieklasse zitten.

Bewijs

Dit volgt direct uit eigenschappen 2 en 4.

Quotiëntverzameling


Als \({\displaystyle \sim }\) een equivalentierelatie op \({\displaystyle X}\) is, dan heet de verzameling van alle equivalentieklassen van \({\displaystyle X}\)

\({\displaystyle X/\sim \ =\{[x]\mid x\in X\}}\)

de quotiëntverzameling van \({\displaystyle X}\) onder \({\displaystyle \sim }\).

Een aantal eigenschappen van quotiëntverzamelingen wordt hieronder bewezen.

Eigenschap 1

De quotiëntverzameling \({\displaystyle X/\sim }\) van een equivalentierelatie \({\displaystyle \sim }\) op een verzameling \({\displaystyle X}\) is een partitie van \({\displaystyle X.}\)

Bewijs

Zij \({\displaystyle \sim }\) een equivalentierelatie op \({\displaystyle X}\). Uit gevolg 1 in de paragraaf over equivalentieklassen volgt dat iedere \({\displaystyle x\in X}\) in precies één equivalentieklasse van \({\displaystyle X}\) zit. Daarbij zitten per definitie van quotiëntverzameling alle equivalentieklassen van \({\displaystyle X}\) in \({\displaystyle X/\sim }\) en heeft \({\displaystyle X/\sim }\) verder geen elementen. Dan volgt dus dat iedere \({\displaystyle x\in X}\) in precies één element van \({\displaystyle X/\sim }\) zit. Uit de definitie van equivalentieklasse volgt verder dat er geen elementen \({\displaystyle u\notin X}\) in enige equivalentieklasse van \({\displaystyle X}\) zitten, wat samen met het voorgaande bewijst dat de vereniging van alle elementen van \({\displaystyle X/\sim }\) gelijk aan \({\displaystyle X}\) 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 \({\displaystyle X}\) levert een unieke quotiëntverzameling op. Er zijn, met andere woorden, geen twee verschillende equivalentierelaties op \({\displaystyle X}\) die dezelfde quotiëntverzameling van \({\displaystyle X}\) opleveren.

Bewijs

Zij \({\displaystyle R}\) en \({\displaystyle S}\) twee equivalentierelaties op \({\displaystyle X}\) waarvoor geldt dat \({\displaystyle X/R=X/S}\). Voor twee willekeurige elementen \({\displaystyle x,y\in X}\) volgt in twee stappen dat \({\displaystyle xRy}\) dan en slechts dan, als \({\displaystyle xSy}\). Stel, ten eerste, dat \({\displaystyle xRy}\). Uit eigenschap 2 van de equivalentieklassen blijkt dat \({\displaystyle x}\) en \({\displaystyle y}\) in dezelfde equivalentieklasse \({\displaystyle K\in X/R}\) zitten. Omdat \({\displaystyle X/R=X/S}\) is \({\displaystyle K\in X/S}\), wat betekent dat \({\displaystyle x}\) en \({\displaystyle y}\) ook onder \({\displaystyle S}\) in dezelfde equivalentieklasse zitten. Daaruit volgt, m.b.v. eigenschap 4 van equivalentieklassen, dat \({\displaystyle xSy}\). Ten tweede is op dezelfde manier te bewijzen dat uit \({\displaystyle xSy}\) volgt dat \({\displaystyle xRy}\). Uit deze twee stappen blijkt dat \({\displaystyle xRy}\) dan en slechts dan, als \({\displaystyle xSy}\). Hieruit volgt dat \({\displaystyle R=S}\), waarmee bewezen is dat als \({\displaystyle R}\) en \({\displaystyle S}\) dezelfde quotiëntverzameling hebben, ze dezelfde equivalentierelatie zijn.

Hoofdstelling


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 \({\displaystyle P}\) van een verzameling \({\displaystyle X}\) is de relatie \({\displaystyle \sim _{P}}\) op \({\displaystyle X}\), gedefinieerd door de eis dat voor alle \({\displaystyle x,y\in X}\):

\({\displaystyle x\sim _{P}y}\) dan en slechts dan, als er een \({\displaystyle K\in P}\) waarvoor \({\displaystyle x\in K}\) en \({\displaystyle y\in K}\),

een equivalentierelatie.

Hulpstelling 1

Voor iedere partitie \({\displaystyle P}\) van \({\displaystyle X}\) is \({\displaystyle \sim _{P}}\) een equivalentierelatie op \({\displaystyle X}\).

Bewijs

Zij \({\displaystyle P}\) een partitie van \({\displaystyle X}\). We bewijzen dat \({\displaystyle \sim _{P}}\) reflexief, symmetrisch en transitief is. Zij \({\displaystyle x,y,z\in X}\). Reflexiviteit en symmetrie volgen direct uit de definitie van \({\displaystyle \sim _{P}}\). Neem, om transitiviteit te bewijzen, aan dat \({\displaystyle x\sim _{P}y}\) en \({\displaystyle y\sim _{P}z}\). Dat betekent dat er een \({\displaystyle K\in P}\) is zodanig dat \({\displaystyle x,y\in K}\) en een \({\displaystyle L\in P}\) zodanig dat \({\displaystyle y,z\in L}\). Omdat de klassen van een partitie disjunct zijn en \({\displaystyle y}\) in zowel \({\displaystyle K}\) als \({\displaystyle L}\) zit, volgt dat \({\displaystyle K=L}\). Hieruit volgt per definitie van \({\displaystyle \sim _{P}}\) dat \({\displaystyle x\sim _{P}z}\).

Hulpstelling 2

Gegeven een partitie \({\displaystyle P}\) van \({\displaystyle X}\) geldt voor iedere \({\displaystyle K\in P}\): als \({\displaystyle x\in K}\), is \({\displaystyle K}\) de equivalentieklasse van \({\displaystyle x}\) onder \({\displaystyle \sim _{P}}\).

Bewijs

Zij \({\displaystyle P}\) een partitie van \({\displaystyle X}\) en \({\displaystyle K\in P}\). Neem aan dat \({\displaystyle x\in K}\). Omdat \({\displaystyle P}\) een partitie is, is er geen andere klasse \({\displaystyle L\in P}\) en \({\displaystyle L\neq K}\) waar \({\displaystyle X}\) in zit. Per definitie van \({\displaystyle \sim _{P}}\) volgt daarom dat voor alle \({\displaystyle y\in X}\) geldt:

\({\displaystyle x\sim _{P}y}\) dan en slechts dan, als \({\displaystyle y\in K}\).

Dat betekent dat

\({\displaystyle K=\{y\in X\mid x\sim _{P}y\}}\)

en dus dat \({\displaystyle K=[x]}\).

Stelling 3

Iedere partitie \({\displaystyle P}\) van een verzameling \({\displaystyle X}\) is de quotiëntverzameling van een equivalentierelatie op \({\displaystyle X}\), namelijk van \({\displaystyle \sim _{P}}\).

Bewijs

Zij \({\displaystyle P}\) een partitie van \({\displaystyle X}\). Uit hulpstelling 1 volgt dat \({\displaystyle \sim _{P}}\) een equivalentierelatie is. We bewijzen in twee stappen dat \({\displaystyle X/\sim _{P}=P}\). Neem ten eerste een willekeurige \({\displaystyle K\in P}\). Omdat \({\displaystyle P}\) een partitie is, is er een \({\displaystyle x\in K}\). Uit hulpstelling 2 volgt dan dat \({\displaystyle K=[x]}\), wat bewijst dat \({\displaystyle K\in X/\sim _{P}}\) en dus dat \({\displaystyle P\subseteq X/\sim _{P}}\). Neem ten tweede een willekeurige \({\displaystyle [x]\in X/\sim _{P}}\). Omdat \({\displaystyle P}\) een partitie is, volgt dat er precies één \({\displaystyle K\in P}\) is waarvoor geldt dat \({\displaystyle x\in K}\). Uit hulpstelling 2 volgt dan weer dat \({\displaystyle K=[x]}\), en dus dat \({\displaystyle [x]\in P}\). Dit betekent dat \({\displaystyle X/\sim _{P}\subseteq P}\), waarmee bewezen is dat \({\displaystyle X/\sim _{P}=P}\).

Hoofdstelling van equivalentierelaties

Er is een een-op-een-correspondentie tussen alle equivalentierelaties op een verzameling \({\displaystyle X}\) en alle partities van dezelfde verzameling \({\displaystyle X}\).

Bewijs

Gegeven een verzameling \({\displaystyle X}\), laat \({\displaystyle A}\) de verzameling zijn van alle equivalentierelaties op \({\displaystyle X}\) en \({\displaystyle B}\) de verzameling van alle partities van \({\displaystyle X}\). We bewijzen dat de afbeelding

\({\displaystyle \alpha :A\to B}\)
\({\displaystyle \alpha :R\mapsto X/R}\)

een een-op-een-correspondentie tussen \({\displaystyle A}\) en \({\displaystyle B}\) is. Uit eigenschap 1 in de paragraaf over quotiëntverzamelingen volgt dat \({\displaystyle \alpha }\) alle equivalentierelaties in \({\displaystyle A}\) op een partitie in \({\displaystyle B}\) afbeeldt. Met andere woorden: \({\displaystyle \alpha }\) is een volledige afbeelding. Uit eigenschap 2 in dezelfde paragraaf volgt dat \({\displaystyle \alpha }\) injectief is. Stelling 3 bewijst dat er voor iedere partitie \({\displaystyle P\in B}\) een equivalentierelatie \({\displaystyle R\in A}\) is zodanig dat \({\displaystyle \alpha (R)=P}\), oftewel dat \({\displaystyle \alpha }\) surjectief is. Dit bewijst dat \({\displaystyle \alpha }\) een een-op-een-correspondentie is.

Geconstrueerde equivalentierelaties


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.










Categorieën: Relaties op verzamelingen




Staat van informatie: 28.09.2021 01:21:15 CEST

oorsprong: Wikipedia (Auteurs [Geschiedenis])    Licentie: CC-BY-SA-3.0

Veranderingen: Alle afbeeldingen en de meeste ontwerpelementen die daarmee verband houden, zijn verwijderd. Sommige pictogrammen werden vervangen door FontAwesome-Icons. Sommige sjablonen zijn verwijderd (zoals 'artikel heeft uitbreiding nodig') of toegewezen (zoals 'hatnotes'). CSS-klassen zijn verwijderd of geharmoniseerd.
Specifieke Wikipedia-links die niet naar een artikel of categorie leiden (zoals 'Redlinks', 'links naar de bewerkpagina', 'links naar portals') zijn verwijderd. Elke externe link heeft een extra FontAwesome-Icon. Naast enkele kleine wijzigingen in het ontwerp, werden mediacontainer, kaarten, navigatiedozen, gesproken versies en Geo-microformats verwijderd.

Belangrijke opmerking Omdat de gegeven inhoud op het gegeven moment automatisch van Wikipedia wordt gehaald, was en is een handmatige verificatie niet mogelijk. Daarom garandeert LinkFang.org niet de juistheid en actualiteit van de verkregen inhoud. Als er informatie is die momenteel verkeerd is of een onjuiste weergave heeft, aarzel dan niet om Neem contact op: E-mail.
Zie ook: Afdruk & Privacy policy.