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
    Gouri Basak
    Participant

    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
    Saikrish Kailash
    Participant

    Equivalence Relation guarantees Partition derivation but reverse is not true.

    #24697
    Shivani Ramesh
    Participant

    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
    Gouri Basak
    Participant

    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.