Home › Forums › Math Olympiad, I.S.I., C.M.I. Entrance › Combinatorics › Equivalence Relation to Partition

- This topic has 11 replies, 8 voices, and was last updated 1 year, 8 months ago by Shivani Ramesh.

- AuthorPosts
- December 8, 2018 at 8:30 pm #24686Ashani DasguptaKeymaster
Does every equivalence relation defined on a set, automatically partitions the set?

If yes, give a rigorous proof.

If no, give an example.

December 8, 2018 at 8:36 pm #24687Pinaki BiswasParticipantProof:1. If there is

*x*in a set, then it will have to be in a partition.**(symmetric)**2.If

*x ~y*, they are in the same partition.=>

*y~x***(reflexive)**3.If

*x~y,y~z*,Then

*x~z*as all are in the same partition.**(transitive)**December 8, 2018 at 8:39 pm #24689aditi ChakrabortyMemberWe can partition the points/elements according to their equivalence like – suppose we have a set S which has 6 points/elements- {A1,A2,A3,A4,A5,A6}

**SYMMETRIC**-A1~A3 then we can arrange them like {A1,A3}**REFLEXIVE**– A2~A2 then we can arrange it like {A2}- T
**RANSITIVE**– A4~A5 , A5~A6 and A4 ~A6 then we can arrange them like {A4,A5,A6}

So, we can get partitions from equivalence relations

**PROVED**December 8, 2018 at 8:40 pm #24690Harshit ShahParticipant**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

- This reply was modified 1 year, 8 months ago by Harshit Shah.

December 8, 2018 at 8:41 pm #24691Writaban SarkarParticipantYes, since making equivalence relations means that the elements are in the same set, we can say that stating elements equivalent means to break the set and form some new set (partition).

- This reply was modified 1 year, 8 months ago by Writaban Sarkar.
- This reply was modified 1 year, 8 months ago by Writaban Sarkar.

- AuthorPosts

- You must be logged in to reply to this topic.