[Harshit Shah]

 

Equivalence relation -> Partition

Constrtuct partitions from the relation as follows,

1) pick an element from set S, take all y in S such that x~y and put them all in a new partition

2) repeat step 1 until all elements of S are exhausted

step 1 guarantees disjointedness and step 2 guarantees exhaustiveness

 

Partition -> Equivalence relation

Declare all elements in a single partition to be equivalent,

1) reflexivity: trivial (x is in the same partition as x, so x~x)

2) symmetry: if x is in the same partition as y, so y is also in the same partition. Therefore, x~y=>y~x

3) transitivity: if x is in the same partition as y, y is in the same partition as z, then x is in the same partition as z. Therefore, x~y,y~z => x~z

 

 

 

 

[Author]

Posts