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: Equivalence relations and classes

  1. Dec 4, 2012 #1
    Show that if R1 and R2 are equivalence relations on a set X, then R1 is a subset of R2 iff every R2-class is the union of R1 classes.

    Attempt: I don't understand that if R2 has elements nothing to do with the elements of R1, how can an R2 class be a union of those elements belonging to an R1 class?
  2. jcsd
  3. Dec 4, 2012 #2


    User Avatar
    Science Advisor

    I'm not sure what you mean by "R2 has elements nothing to do with the elements of R1". Both R1 and R2 are defined as equivalence relations on X so they both consist of ordered pairs of elements of X. Doesn't one "have something to do" with the other?

    It is, of course, possible that the two relations are dijoint, that is, that they have no elements in common. A simple example of this is X= {0, 1, 2, 3}, R1 defined by "xR1y if and only if x= y= 1" so that R1 is the set {(1, 1)} and R2 defined by "xR2y if and only if x=y= 3" so that R2 iis the set {(3, 3)}.
    But in this case the "if and only if" statement says if one is true then the other is also. In this example, both parts of the statement, "R1 is a subset of R2" and "every R2-class is the union of R1 classes" are both false and so the statement itself is true. The only way you could have a counter-example would be if one of the two statements was true and the other was false.
  4. Dec 4, 2012 #3
    Actually I didn't even realize that the statements were false... But why is "R1 is a subset of R2" false? Could you explain this as if I were a 5 year old?
  5. Dec 4, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Halls isn't saying the statements are false in general. You are required to show that in any given situation EITHER both statements about R1 and R2 are true OR both are false.
    The usual way to proceed is to do one direction at a time: first, suppose R1 is a subset of R2 and deduce that every R2-class is the union of R1 classes; next, suppose every R2-class is the union of R1 classes and deduce that R1 is a subset of R2.
    Commonly, either or both of these might most easily be achieved by working backwards. E.g. for the first half above, suppose some R2-class is not a union of R1 classes, then show there's an element of R1 that is not in R2. (With all this logical negation and reversal going on, the trap to avoid is proving the same direction twice over.)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook