# Prove that the intersection of two equivalence relations is an equivalence relation.

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!

-

Which of the three conditions are you finding hard to verify? – Isomorphism Dec 15 '12 at 19:02

## 3 Answers

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.

-

## Did you find this question interesting? Try our newsletter

email address

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

-

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 $<x,x> \in R \cap S$ and for each pair$<x,y> \in R \cap S$, you have to show that $<y,x> \in R \cap S$ and for each pairs $<x,y>, <y,z> \in R \cap S$ you have to show that $<x,z> \in R \cap S$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 28, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9524861574172974, "perplexity_flag": "head"}