Equivalentierelatie: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k recat |
-htmlentities, bestand->Bestand |
||
Regel 1:
[[
In de [[wiskunde]] is een '''equivalentierelatie''' een [[tweeplaatsige relatie]] die alle [[Element (wiskunde)|elementen]] uit een [[verzameling (wiskunde)|verzameling]] die in bepaalde zin gelijkwaardig zijn aan elkaar, 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.
Regel 37:
Zij ~ een equivalentierelatie op ''X''.
;Eigenschap 1:Voor alle ''x'' <math>\in</math> ''X'' geldt dat ''x'' <math>\in</math> [''x'']. Iedere ''x'' <math>\in</math> ''X'' zit dus in ten minste
(''Bewijs'') Zij ''x'' <math>\in</math> ''X''. Uit de reflexiviteit van ~ volgt dat ''x'' ~ ''x'', wat betekent dat ''x'' <math>\in</math> [''x''].
Regel 45:
(''Bewijs'') Zij ''x'', ''y'' <math>\in</math> ''X'' zodanig dat ''x'' ~ ''y''. We nemen een willekeurig element ''u'' <math>\in</math> [''x''] en bewijzen dat ''u'' <math>\in</math> [''y'']. Uit de definitie van ''equivalentieklasse'' en ''u'' <math>\in</math> [''x''] volgt dat ''x'' ~ ''u''. Uit de symmetrie van ~ en ''x'' ~ ''y'' volgt dat ''y'' ~ ''x''. Nu weten we dus dat ''y'' ~ ''x'' en ''x'' ~ ''u''. Omdat ~ transitief is weten we dan ook dat ''y'' ~ ''u'', waaruit per definitie volgt dat ''u'' <math>\in</math> [''y'']. Dit bewijst dat [''x''] <math>\subseteq</math> [''y'']. Op dezelfde manier, maar dan zonder symmetrie te gebruiken, is te bewijzen dat [''y''] <math>\subseteq</math> [''x''], waaruit volgt dat [''x''] = [''y'']. Omdat we uit eigenschap 1 weten dat ''x'' <math>\in</math> [''x''] en ''y'' <math>\in</math> [''y''], betekent dit dat ''x'' en ''y'' in dezelfde equivalentieklasse zitten.
;Eigenschap 3:Voor alle ''x'', ''y'', ''z'' <math>\in</math> ''X'' geldt dat als ''x'' <math>\in</math> [''y''] en ''x'' <math>\in</math> [''z''] dan [''y''] = [''z'']. Iedere ''x'' <math>\in</math> ''X'' zit dus in ten hoogste
(''Bewijs'') Zij ''x'', ''y'', ''z'' <math>\in</math> ''X'' zodanig dat ''x'' <math>\in</math> [''y''] en ''x'' <math>\in</math> [''z'']. Uit de definitie van ''equivalentieklasse'' volgt dan dat ''y'' ~ ''x'' en ''z'' ~ ''x''. Symmetrie van ~ geeft vervolgens ''x'' ~ ''z''. Nu hebben we dus ''y'' ~ ''x'' en ''x'' ~ ''z'', waarmee uit de transitiviteit van ~ af te leiden is dat ''y'' ~ ''z''. Eigenschap 2 geeft vervolgens dat [''y''] = [''z''].
Regel 53:
(''Bewijs'') Zij ''x'', ''y'' <math>\in</math> ''X'' en zowel ''x'' <math>\in</math> [''u''] als ''y'' <math>\in</math> [''u''] voor een zekere ''u'' <math>\in</math> ''X''. Uit de definitie van ''equivalentieklasse'' volgt dat ''u'' ~ ''x'' en ''u'' ~ ''y''. Uit de symmetrie van ~ volgt dat ook ''x'' ~ ''u''. Door de transitiviteit van ~ weten we vervolgens dat ''x'' ~ ''y''. Op dezelfde manier is te bijwijzen dat ''y'' ~ ''x''.
;Gevolg 1:Iedere ''x'' <math>\in</math> ''X'' zit in precies
(''Bewijs'') Dit volgt direct uit eigenschappen 1 en 3.
Regel 61:
(''Bewijs'') Dit volgt direct uit eigenschappen 2 en 4.
== Quotiëntverzameling ==
Als ~ een equivalentierelatie op ''X'' is, dan is de verzameling van alle equivalentieklassen van ''X''
:''X''/~ = { [''x''] | ''x'' <math>\in</math> ''X'' }
de '''
Een aantal eigenschappen van
;Eigenschap 1:Van iedere equivalentierelatie ~ op ''X'' is de
(''Bewijs'') Zij ~ een equivalentierelatie op ''X''. Uit gevolg 1 in de paragraaf over equivalentieklassen volgt dat iedere ''x'' <math>\in</math> ''X'' in precies
;Eigenschap 2:Iedere equivalentierelatie op ''X'' levert een unieke
(''Bewijs'') Zij ''R'' en ''S'' twee equivalentierelaties op ''X'' waarvoor geldt dat ''X''/''R'' = ''X''/''S''. We nemen twee willekeurige elementen ''x'', ''y'' <math>\in</math> ''X'' en bewijzen in twee stappen dat ''x'' ''R'' ''y'' desda ''x'' ''S'' ''y''. Stel, ten eerste, dat ''x'' ''R'' ''y''. Uit eigenschap 2 van equivalentieklassen weten we dat ''x'' en ''y'' in dezelfde equivalentieklasse ''K'' <math>\in</math> ''X''/''R'' zitten. Omdat ''X''/''R'' = ''X''/''S'' weten we dat ''K'' <math>\in</math> ''X''/''S'', wat betekent dat ''x'' en ''y'' ook onder ''S'' in dezelfde equivalentieklasse zitten. Daaruit volgt, door eigenschap 4 van equivalentieklassen, dat ''x'' ''S'' ''y''. Ten tweede is op dezelfde manier te bewijzen dat uit ''x'' ''S'' ''y'' volgt dat ''x'' ''R'' ''y''. Uit deze twee stappen volgt dat ''x'' ''R'' ''y'' desda ''x'' ''S'' ''y''. Hieruit leiden we af dat ''R'' = ''S'', waarmee bewezen is dat wanneer ze dezelfde
== Hoofdstelling ==
Regel 90:
;Hulpstelling 2:Gegeven een partitie ''P'' van ''X'' geldt voor iedere ''K'' <math>\in</math> ''P'': als ''x'' <math>\in</math> ''K'' dan is ''K'' de equivalentieklasse van ''x'' onder ~<sub>''P''</sub>.
(''Bewijs'') Zij ''P'' een partitie van ''X'' en ''K'' <math>\in</math> ''P''. Neem aan dat ''x'' <math>\in</math> ''K''. Omdat ''P'' een partitie is, is er geen andere klasse ''L'' <math>\in</math> ''P'' en ''L''
:''x'' ~<sub>''P''</sub> ''y'' desda ''y'' <math>\in</math> ''K''.
Dat betekent dat
Regel 102:
;Hoofdstelling van equivalentierelaties:Er is een [[Bijectie|één-op-één-correspondentie]] tussen alle equivalentierelaties op een verzameling ''X'' en alle partities van dezelfde verzameling ''X''.
(''Bewijs'') Gegeven een verzameling ''X'', zij ''A'' de verzameling van alle equivalentierelaties op ''X'' en ''B'' de verzameling van alle partities van ''X''. We bewijzen dat de [[
:''
:''
een één-op-één-correspondentie tussen ''A'' en ''B'' is. Uit eigenschap 1 in de paragraaf over quotiëntverzamelingen volgt dat ''
== Geconstrueerde equivalentierelaties ==
| |||