# Equivalence Relation proof

1. Oct 20, 2008

### estra

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. Oct 20, 2008

### HallsofIvy

Staff Emeritus
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.

3. Oct 20, 2008

### estra

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 }.

4. Oct 20, 2008

### HallsofIvy

Staff Emeritus
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".

5. Oct 20, 2008

### estra

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.

Thank you again

6. Oct 20, 2008

### HallsofIvy

Staff Emeritus
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.

7. Oct 20, 2008

### estra

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...

8. Oct 20, 2008

### HallsofIvy

Staff Emeritus
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".