Equivalentierelatie: verschil tussen versies

Zij <math>R</math> en <math>S</math> twee equivalentierelaties op <math>X</math> waarvoor geldt dat <math>X/R = X/S.</math> We nemenVoor twee willekeurige elementen <math>X</math>x, <math>y</math> <math>\in X</math> en bewijzenvolgt in twee stappen dat <math>xRy</math> desda <math>xSy.</math> Stel, ten eerste, dat <math>xRy.</math> Uit eigenschap 2 van equivalentieklassen weten weblijkt dat <math>x</math> en <math>y</math> in dezelfde equivalentieklasse <math>K \in X/R</math> zitten. Omdat <math>X/R=X/S</math> weten we datie <math>K \in X/S,</math> wat betekent dat <math>x</math> en <math>y</math> ook onder <math>S</math> in dezelfde equivalentieklasse zitten. Daaruit volgt, doorm.b.v. eigenschap 4 van equivalentieklassen, dat <math>xSy.</math>. Ten tweede is op dezelfde manier te bewijzen dat uit <math>xSy</math> volgt dat <math>xRy.</math> Uit deze twee stappen volgtblijkt dat <math>xRy</math> desda <math>xSy.</math> Hieruit leiden we afvolgt dat <math>R=S,</math> waarmee bewezen is dat wanneerals ze dezelfde quotiëntverzameling hebben, <math>R</math> en <math>S</math> dezelfde equivalentierelatie zijn.

Er is een diepe overeenkomst tussen equivalentierelaties op en [[partitie (verzamelingenleer)|partities]] van een verzameling. DezeDit verband wordt uitgedrukt indoor de hoofdstelling van equivalentierelaties.

GegevenVoor een gegeven een partitie <math>P</math> van een verzameling <math>X</math> definiëren weis de relatie <math>\sim _P</math> op <math>X,</math> waarvoorgedefinieerd door de geldteis dat voor alle <math>x,y \in X</math>:

Zij <math>P</math> een partitie van <math>X.</math> We bewijzen dat <math>\sim_P</math> reflexief, symmetrisch en transitief is. Zij <math>x,y,z \in X.</math> Reflexiviteit en symmetrie volgen direct uit de definitie van <math>\sim_P.</math> Neem, om transitiviteit te bewijzen, aan dat <math>x \sim_P y</math> en <math>y \sim_P z.</math> Dat betekent dat er een <math>K \in P</math> is zodanig dat <math>x,y \in K</math> en een <math>L \in P</math> zodanig dat <math>y,z \in L.</math> Omdat de klassen van een partitie [[disjuncte verzamelingen|disjunct]] zijn en <math>y</math> in zowel <math>K</math> als <math>L</math> zit, weten wevolgt dat <math>K=L.</math> Hieruit volgt per definitie van <math>\sim_P</math> dat <math>x \sim_P z.</math>

Zij <math>P</math> een partitie van <math>X</math>. Uit hulpstelling 1 volgt dat <math>\sim_P</math> een equivalentierelatie is. We bewijzen in twee stappen dat <math>X/\sim_P = P.</math> Neem ten eerste een willekeurige <math>K \in P.</math> Omdat <math>P</math> een partitie is, is er een <math>x \in K.</math> Uit hulpstelling 2 volgt dan dat <math>K=[x],</math> wat bewijst dat <math>K \in X/\sim_P</math> en dus dat <math>P \subseteq X/\sim_P.</math> Neem ten tweede een willekeurige <math>[x] \in X/\sim_P.</math> Omdat <math>P</math> een partitie is, weten wevolgt dat er precies één <math>K \in P</math> is waarvoor geldt dat <math>x \in K.</math> Uit hulpstelling 2 volgt dan wederomweer dat <math>K=[x],</math> en dus dat [<math>X</math>[x] <math>\in P</math>. Dit betekent dat <math>X/\sim_P \subseteq P,</math> waarmee bewezen is dat <math>X/\sim_P = P.</math>