Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows.

Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R \cap S$ is also an equivalence relation.

Thanks for helps!

share|improve this question
    
Which of the three conditions are you finding hard to verify? –  Isomorphism Dec 15 '12 at 19:02
add comment

3 Answers 3

up vote 6 down vote accepted

Hint: Use the fact that $R$ and $S$ are EQUIVALENCE relations on THE SAME set, and hence both must be reflexive, symmetric, and transitive on that set.

Then use the definition of set intersection: $R\cap S$ is the set of all pairs of elements in the set such that $(x, y) \in R$ AND $(x, y) \in S$ or, put differently, $(x, y) \in R\cap S \iff (x, y)\in R$ and $(x, y) \in S$.

Try to figure out what elements must necessarily be in $R\cap S$ and check to see that they must then be in both $R$ and $S$.


Another approach would be to use an indirect proof with the hints above:

"Given $R$ and $S$ are equivalence relations on a set $A$, suppose for the sake of contradiction, that $R\cap S$ is NOT an equivalence relation...". If not an equivalence relation, then $R\cap S$ fails to be reflexive and/or fails to be symmetric, and/or fails to be transitive. If you can work towards a contradiction (that this assumption must contradict the fact that both $R$ and $S$ are equivalence relations), then you are done.

share|improve this answer
add comment

For the solution of this exercise, you have to show that $R \cap S$ keeps the three properties of equivalence relations (reflexive, symmetric and transitive).

This means that for each x you have to show that $\langle x,x\rangle \in R \cap S$ and for each pair $\langle x,y\rangle \in R \cap S$, you have to show that $\langle y,x\rangle \in R \cap S$ and for each pairs $\langle x,y\rangle, \langle y,z\rangle \in R \cap S$ you have to show that $\langle x,z\rangle \in R \cap S$

share|improve this answer
add comment

Hint (did this in school):
Let's have 2 relations $$R- antisymmetric$$ $$S-antisymmetric$$ I had to prove that $R \cap S$ is also antisymmetric.

$$P=R \cap S$$ $$(x,y) \in P$$ $$\implies (x,y) \in R \cap S $$ $$\implies (x,y) \in R \wedge (x,y) \in S $$ $$\implies ((y,x) \notin R \wedge (y,x) \notin S) \Rightarrow(x \ne y) $$ $$\implies (y,x) \notin R \cap S $$ $$\implies (y,x) \notin P $$

PS: Someone who know how to align text to left please edit :) Thanks

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.