equivalence relation difficult problem

Question

Let $R_1$, $R_2$ be 2 equivalence relations on $X$; prove that $R_1\cup R_2$ is an equivalence relation on $X$ if and only if $R_1\cup R_2=R_1\circ R_2$ I really don´t have any idea how to do it, I would appreciate your help

Answer 1

HINT: First notice that $R_1\cup R_2\subseteq R_1\circ R_2$: if $\langle x,y\rangle\in R_1\cup R_2$, it’s not hard to use reflexivity to show that there is a $z\in X$ such that $\langle x,z\rangle\in R_1$ and $\langle z,y\rangle\in R_2$ (or such that $\langle x,z\rangle\in R_2$ and $\langle z,y\rangle\in R_1$, depending on which way around you evaluate compositions).

The real work is showing that $R_1\circ R_2\subseteq R_1\cup R_2$ if and only if $R_1\cup R_2$ is an equivalence relation. It’s easy to show that $R_1\cup R_2$ is reflexive and symmetric, so it’s an equivalence relation if and only if it’s transitive. Thus, you need to show that $R_1\circ R_2\subseteq R_1\cup R_2$ if and only if $R_1\cup R_2$ is transitive.

• It’s very straightforward to show that if $R_1\cup R_2$ is transitive, then $R_1\circ R_2\subseteq R_1\cup R_2$.

• If $R_1\cup R_2$ is not transitive, there must be $x,y,z\in X$ such that $\langle x,z\rangle\in R_1$, $\langle z,y\rangle\in R_2$, and $\langle x,y\rangle\notin R_1\cup R_2$ (why?); use this to find a member of $R_1\circ R_2$ that is not in $R_1\cup R_2$.

Answer 2

(I can't add a comment)

I think I managed to prove transitivity.

Remember that by hypothesis $R_{1}\cup R_{2} = R_{1}\circ R_{2}$ and consider that we already proved that $R_{1}\cup R_{2}$ is reflexive, so $R_{1}\circ R_{2}$ is also reflexive.

Let $x,y,z\in X$ such that $(x,y)\in R_{1}\cup R_{2}\land (y,z)\in R_{1}\cup R_{2}$, then:

$[(x,y)\in R_{1} \lor (x,y)\in R_{2}]\land [(y,z)\in R_{1} \lor (y,z)\in R_{2}]\\ \Rightarrow [(x,y)\in R_{1}\land ((y,z)\in R_{1} \lor (y,z)\in R_{2})]\lor [(x,y)\in R_{1}\land ((y,z)\in R_{1} \lor (y,z)\in R_{2})]\\ \Rightarrow [(x,y)\in R_{1}\land (y,z)\in R_{1}]\lor [(x,y)\in R_{1}\land (y,z)\in R_{2}]\lor [(x,y)\in R_{2} \land (y,z)\in R_{1}]\lor [(x,y)\in R_{2}\land (y,z)\in R_{2}]\\ \Rightarrow [(x,z)\in R_{1}]\lor [(x,z)\in R_{1}\circ R_{2}]\lor [(z,y)\in R_{1}\land (y,x)\in R_{2}]\lor [(x,z)\in R_{2}]\\ \Rightarrow [(x,z)\in R_{1}\cup R_{2}]\lor [(x,z)\in R_{1}\cup R_{2}]\lor [(z,x)\in R_{1}\circ R_{2}]\lor [(x,z)\in R_{1}\cup R_{2}]\\ \Rightarrow [(x,z)\in R_{1}\cup R_{2}]\lor [(x,z)\in R_{1}\circ R_{2}]\\ \Rightarrow (x,z)\in R_{1}\cup R_{2}$

I am right?