 # Equivalence Relation to Partition

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

Viewing 5 posts - 6 through 10 (of 12 total)
• Author
Posts
• #24693

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.

#24695

Equivalence Relation guarantees Partition derivation but reverse is not true.

#24697

It is true because:

every equivalence relation is

-symmetric

-reflexive and

-transitive

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

#24699

No 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 .

#24700

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

Viewing 5 posts - 6 through 10 (of 12 total)
• You must be logged in to reply to this topic.