Let R1 and R2 be two equivalence relations on X.prove that whether R1UR2 is an equivalence relation on X if R1UR2 ⊆ R1 o R2.

Question

So...I actually proved this statement but my teacher told me that I should make a counterexample.however I think the statement is correct plus, I couldn't find any counterexample for the problem. Can you tell me whether the statement is correct or not?and if it is incorrect...what counterexample is suitable?

Answer 1

Suppose $R_1,R_2$ are both equivalence relations on $X$.

Suppose $R_1\cup R_2\subseteq R_1\circ R_2$.

We want to prove $R_1\cup R_2$ is an equivalence relation as well.

Clearly, for all $x\in X$ we have that $(x,x)\in R_1$ since $R_1$ is an equivalence relation and so $(x,x)\in R_1\cup R_2$ so $R_1\cup R_2$ is reflexive.

Suppose that $(x,y)\in R_1\cup R_2$ and so $(x,y)\in R_1$ or $(x,y)\in R_2$. Without loss of generality suppose it was the first. Then it follows that since $R_1$ is an equivalence relation that $(y,x)\in R_1$ as well and so $(y,x)\in R_1\cup R_2$, so $R_1\cup R_2$ is symmetric. (By saying "without loss of generality" we imply that any other cases would have been proven identically just with names and labels swapped around and so we only bother writing out the argument once rather than repeating ourselves)

Finally, suppose that $(x,y)\in R_1\cup R_2$ and $(y,z)\in R_1\cup R_2$. We wish to prove that $(x,z)$ is also in $R_1\cup R_2$ and if we do so then we have proven that $R_1\cup R_2$ is an equivalence relation.

Well... if $(x,y)$ and $(y,z)$ both originated from the same equivalence relation, then it follows that $(x,z)$ would also be in that equivalence relation, so let us instead consider the case where $(x,y)$ came from $R_1$ and $(y,z)$ came from another more closely and see if there is anything we can do about it...

Suspecting that there is not, let us consider making a counterexample based around this scenario. We recognize that it would be helpful then to have our counterexample involve three distinct numbers where one of the pairs of numbers are related under the first relation while a different pair of numbers are related under the second relation.

Let $X=\{1,2,3\}$. Let $R_1 = \{(1,1),(1,2),(2,1),(2,2),(3,3)\}$ and let $R_2 = \{(1,1),(2,2),(2,3),(3,2),(3,3)\}$

$~$

We have that $R_1\cup R_2$ does not contain $(1,3)$ despite containing both $(1,2)$ and $(2,3)$ and so is not transitive. One can check that this example does indeed satisfy $R_1\cup R_2\subseteq R_1\circ R_2$ (and indeed, one can prove that every pair of equivalence relations $R_1,R_2$ over the same set satisfy that $R_1\cup R_2\subseteq R_1\circ R_2$)