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:43 pm #24693Gouri BasakParticipant
It is true that every equivalence relation gives a partition

For an equivalence relation , the relation must be reflexive,symmetric and transitive

All partitions are reflexive,symmetric and transitive, so it is an equivalence relation.And the equivalence classes of a partition are the sets.So every equivalence relation partitions its set into equivalence classes.

December 8, 2018 at 8:50 pm #24695Saikrish KailashParticipantEquivalence Relation guarantees Partition derivation but reverse is not true.

December 8, 2018 at 8:56 pm #24697Shivani RameshParticipantIt is true because:

every equivalence relation is

-symmetric

-reflexive and

-transitive

so when we partition the sets they are reflexive, symmetric and transitive

December 8, 2018 at 9:41 pm #24699Gouri BasakParticipantNo it is not true that equivalence relation makes a partition and Partition makes an equivalence relation always.

Let’s take a way of changing an equivalence relation to a partition first

And for an example let’s make a rule that take two numbers x and y such that x and y is divisible by 3,then it is an equivalence relation

Like this many Sets (partitions) can be formed

{0,3,6,9,12….}

{1,4,7,10,13…}{2,5,8,11,14…}

But these partitions are going infinitely and these are disjointed and exhausted (and can’t be brought back to an equivalence relation)

So this example proves that the statement is false .

December 8, 2018 at 9:58 pm #24700aditi ChakrabortyMember**EQUIVALENCE TO PARTITONs**We 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-If A1~A3(A3 ~ A1 as well) then we can arrange them like {A1,A3} (or like {A3,A1})
- REFLEXIVE – If A2~A2 then we can arrange it like {A2}
- TRANSITIVE– If A4~A5 , A5~A6 and A4 ~A6 (so A6~A5 , A6 ~ A4 and A5 ~ A4 as well)then we can arrange them like {A4,A5,A6} (or like {A6,A5,A4} or {A6,A4,A5} or {A4,A6,A5} or {A5,A6,A4} or {A5,A4,A6})

So, we can get partitions from equivalence relations.

**PARTITIONS TO EQUIVALENCE**We can declare the points in a partition to be equivalent to each other like – suppose we have a set R which has 6 points/elements – {B1,B2,B3,B4,B5,B6}

- SYMMETRIC- If {B1,B2}({B2,B1} Can also be) is a partition then we can declare B1 ~ B2 (so B2 ~ B1 as well)
- REFLEXIVE- If {B3} is a partition then we can declare B3~B3
- TRANSITIVE- If {B4,B5,B6} (or {B4,B6,B5} or {B5,B4,B6} or {B5,B6,B4} or {B6,B4,B5} or {B6,B5,B4}) is a partition then we can declare B4~B5 B5~B6 and B4~B6 ( or B4~B6 B6~B5 and B4~B5 or B5~B6 B6~B4 and B5~B4 or B5~B4 B4~B6 and B6~B5 or B6~B5 B5~B4 and B6~B4 or B6~B4 B4~B5 and B6~B5)

So, we can get equivalence relations from partitions.

**PROVED** - AuthorPosts

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