1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove a set X is union of disjoint equivalence classes

  1. Oct 13, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove: If E1, · · · , Ek are the disjoint equivalence classes
    determined by an equivalence relation R over a set X, then
    (a) X = union of disjoint equivalence classes Ej
    (b) R = union of disjoint (Ej x Ej)

    2. Relevant equations
    R is a subset of X x X

    3. The attempt at a solution
    For (a), my thoughts are :
    1/ By reflexive property of equiv. relation, there exists an element a in X such that <a,a> belongs to R
    2/ I know "E1, · · · , Ek are the disjoint equivalence classes
    determined by an equivalence relation R", so if a belongs to R, then a must also belongs to some of the equivalence classes.
    3/ Then I use the fact that a is in X, and a belongs to some of equivalence classes, then X must be the union of those equiv. classes

    But then I'm not sure if my thoughts are correct, probably what I'm confused is with my 3rd idea.

    For (b), my thoughts are:
    Since R is a subset of X x X
    and by (a), X is an union of disjoint equiv. classes
    then X x X = union of (Ej x Ej)

    And again, I feel shaky about my reasoning

    Would someone please give me some hints or ideas?
    I really appreciate your time and your help.
  2. jcsd
  3. Oct 13, 2011 #2


    User Avatar
    Science Advisor

    You know an equivalence relation partitions your set into disjoint equivalence classes,right? If aRb and aRc, then bRa (symmetry) and aRc , so bRc (so b and c are in the same class) , so no element belongs to more than one equivalent class, and all elements belong to some class.

    For (b), don't you mean R=EixEj , for Ei,Ej disjoint?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook