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 Relation proof

  1. Oct 20, 2008 #1
    1. The problem statement, all variables and given/known data

    Prove that when R and S are equivalence relations, then SR is
    equivalance relation when SR=RS.

    2. Relevant equations

    3. The attempt at a solution

    I want to know what sets should i take for the relations ?
    is it ok when i take R a a subset of X x Y and S as a subset of Y
    and Z or should i take it some other way?
    then SR is a subset of X x Z ? am i moving right?

    also when tring to solve this problem I found that x has to be equal
    to y when SR = RS..

    Thank you!
  2. jcsd
  3. Oct 20, 2008 #2


    User Avatar
    Science Advisor

    You shouldn't take any sets for the relation! an "example" is not a proof and if you choose any specific set, you have only an example. It makes no sense to say "R a a subset of X x Y and S as a subset of Y and Z" when a "relation" has to be a subset of some X x X.

    A relation is, by definition, a subset of XxX (where X is any set) such that

    1) (x,x) is in the subset (reflexive property)
    2) If (x, y) is in the subset then so is (y,x) (symmetric property)
    3) If (x, y) and (y, z) are in the subset then so is (x, z) (transitive property)

    You are given that R and S are subsets of X x X for some set X and you want to perove that SR is also when SR= RS. It would help a lot if you would first say what "RS" and "SR" mean when S and R are subsets of X x X.
  4. Oct 20, 2008 #3
    But who do you what "RS" and "SR" mean when S and R are subsets of X x X

    I can only think that way
    S ∘ R = { (x, z) | there exists y ∈ Y, such that (x, y) ∈ R and (y, z) ∈ S }.
  5. Oct 20, 2008 #4


    User Avatar
    Science Advisor

    YOU were the one who used the notation "SR= RS"! I have no idea what you mean by it. In your second line, you appear to have used a character that does not show up on my reader. Please define "SR" and "RS".
  6. Oct 20, 2008 #5
    ok sorry about that.
    Lets say it again.

    Prove that, when S and R are equivalence relations in the set X, then RS is an equivalence relation in the set X when SR=RS.

    I think that on the second part we have to show that the composition of equivalence relations is commutative.. (when for any two equivalence relations S and R on an object X there is a equality SR=RS..)
    But I'm not sure how to define SR and RS.

    Sorry about the mess..

    Thank you again
  7. Oct 20, 2008 #6


    User Avatar
    Science Advisor

    If you don't know what it means, how can you expect to do any proofs about it? I do not recognize the notation myself: check your textbook.
  8. Oct 20, 2008 #7
    well that is how it is asked in my textbook. and i was told to prove that. there is no more information about that there...
  9. Oct 20, 2008 #8


    User Avatar
    Science Advisor

    you finally used the phrase "composition of equivalence relations". Where did you get that?

    Are you saying that if xRy and ySz, then xRSz? In other words, if (x,y) is in the relation R and (y,z) is in the relation S then (x, z) is in the relation RS.

    To prove something is a relation, you have to show the three properties hold:
    1) reflexive. If x is in X, then xRx and xSx because they are reflexive. Does that show that xRSx?

    2) symmetric. If (x,y) is in R, then (y,x) is also. If (x,y) is in S, then (y,x) is also. You need to use that (and RS= SR) to show that "if (x,y) is in RS, the (y,x) is also".

    3) transitive. If (x,y) and (y,z) are both in R, then so is (x,z). If (x,y) and (y,z) are both in S, then so is (x, z). You need to use that to show "if (x,y) and (y,z) are both in RS, then (x,z) is also".
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Equivalence Relation proof Date
Equivalence relation - Proof question Jun 12, 2013
Equivalence relation proof Mar 14, 2012
Proofs Question: Equivalence Relation and Classes Nov 7, 2011
Equivalence relation proof Sep 8, 2011
Equivalence relation proof Aug 28, 2011