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
  • #24693
    Gouri Basak

    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.

    Saikrish Kailash

    Equivalence Relation guarantees Partition derivation but reverse is not true.

    Shivani Ramesh

    It is true because:

    every equivalence relation is


    -reflexive and


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


    Gouri Basak

    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


    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 .




    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.


    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.




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