# Math Help - Prove or disprove equivalence relation of union and intersection

1. ## Prove or disprove equivalence relation of union and intersection

Please check and critique the following proof:

Let $R_{1}$and $R_{2}$ be equivalence relations on a set A.

a) Is $R_{1}\cup R_{2}$ an equivalance relation on A? Prove or disprove.

First we need to test the Reflexive property: Let $a_{1}\in$ A such that $(a_{1},a_{1})\in R_{1}$ and $a_{2}\in A$ such that $(a_{2},a_{2})\in R_{2}$. Since $(a_{1},a_{1})\in R_{1}$, then $(a_{1},a_{1})\in R_{1}\cup R_{2}$. Similarly, $(a_{2},a_{2})\in R_{2}$, then $(a_{2},a_{2})\in R_{1}\cup R_{2}$. This proves that $R_{1}\cup R_{2}$ is Reflexive.

Second we need to test the Symmetric property: Let $a_{1},b_{1}\in$ A such that $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}$ and $a_{2},b_{2}\in$ A such that $(a_{2},b_{2}),(b_{2},a_{2})\in R_{2}$. Clearly if $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}$ then $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cup R_{2}$. Also if $(a_{2},b_{2}),(b_{2},a_{2})\in R_{2}$ then $(a_{2},b_{2})$, $(b_{2},a_{2})\in R_{1}\cup R_{2}$. This proves that $R_{1}\cup R_{2}$ is Symmetric.

Third we need to test the Transitive property: Let $a_{1},b_{1},c_{1}\in$ A such that $(a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}$ and $a_{2},b_{2},c_{2}\in$ A such that $(a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}$. Clearly if $(a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}$ then $(a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}\cup R_{2}$. Similarly if $(a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}$ then $(a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{1}\cup R_{2}$. Therefore $R_{1}\cup R_{2}$ is Transitive. Since $R_{1}\cup R_{2}$ is Reflexive, Symmetric, and Transitive, it is an equivalence relation on A.

b) Is $R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Suppose $a_{1}\in A$ such that $(a_{1},a_{1})\in R_{1}$ and $(a_{1},a_{1})\notin R_{2}$. Then clearly $(a_{1},a_{1})\notin R_{1}\cap R_{2}$. Since $R_{1}\cap R_{2}$ is not Reflexive, it is not an equivalence relation on A.

2. Originally Posted by oldguynewstudent
Please check and critique the following proof:

Let $R_{1}$and $R_{2}$ be equivalence relations on a set A.

a) Is $R_{1}\cup R_{2}$ an equivalance relation on A? Prove or disprove.

First we need to test the Reflexive property: Let $a_{1}\in$ A such that $(a_{1},a_{1})\in R_{1}$ and $a_{2}\in A$ such that $(a_{2},a_{2})\in R_{2}$. Since $(a_{1},a_{1})\in R_{1}$, then $(a_{1},a_{1})\in R_{1}\cup R_{2}$. Similarly, $(a_{2},a_{2})\in R_{2}$, then $(a_{2},a_{2})\in R_{1}\cup R_{2}$. This proves that $R_{1}\cup R_{2}$ is Reflexive.
You're working backwards!

To show that $R_1 \cup R_2$ is reflexive, you need to show that $\forall a \in A, \ (a,a) \in R_1 \cup R_2$
This clearly follows from the fact that $R_1, \ R_2$ are reflexive.

Second we need to test the Symmetric property: Let $a_{1},b_{1}\in$ A such that $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}$ and $a_{2},b_{2}\in$ A such that $(a_{2},b_{2}),(b_{2},a_{2})\in R_{2}$. Clearly if $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}$ then $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cup R_{2}$. Also if $(a_{2},b_{2}),(b_{2},a_{2})\in R_{2}$ then $(a_{2},b_{2})$, $(b_{2},a_{2})\in R_{1}\cup R_{2}$. This proves that $R_{1}\cup R_{2}$ is Symmetric.
You're not following the definition! A relation $R$ is symmetric if $(a,b) \in R \Rightarrow (b,a) \in R$.
Here, in order to show that $R_1 \cup R_2$ is symmetric, you need to show $(a,b) \in R_1 \cup R_2 \Rightarrow (b,a) \in R_1 \cup R_2$
This, again, easily follows from your relations being symmetric.

Third we need to test the Transitive property: Let $a_{1},b_{1},c_{1}\in$ A such that $(a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}$ and $a_{2},b_{2},c_{2}\in$ A such that $(a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}$. Clearly if $(a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}$ then $(a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}\cup R_{2}$. Similarly if $(a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}$ then $(a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{1}\cup R_{2}$. Therefore $R_{1}\cup R_{2}$ is Transitive. Since $R_{1}\cup R_{2}$ is Reflexive, Symmetric, and Transitive, it is an equivalence relation on A.
Same reasoning. Here, you need to show that $(a,b) \in R \ \wedge \ (b,c) \in R \Rightarrow (a,c) \in R$.
Now try proving these conditions again (you'll find something is missing for transitiveness...)
Once you've done that, b) will be much easier.

b) Is $R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Suppose $a_{1}\in A$ such that $(a_{1},a_{1})\in R_{1}$ and $(a_{1},a_{1})\notin R_{2}$. Then clearly $(a_{1},a_{1})\notin R_{1}\cap R_{2}$. Since $R_{1}\cap R_{2}$ is not Reflexive, it is not an equivalence relation on A.

3. Originally Posted by oldguynewstudent
Let $R_{1}$and $R_{2}$ be equivalence relations on a set A.
a) Is $R_{1}\cup R_{2}$ an equivalance relation on A? Prove or disprove.
Part a is FALSE. Consider the set $A=\{1,2,3\}$.
$R_1=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}~\&~ R_2=\{(1,1),(2,1),(3,3),(2,2),(1,2)\}$

Consider the set $\mathcal{A}$ of all relations of a set $A$.
If $R\in\mathcal{A} ~\&~S\in\mathcal{A}$ if $R$ is reflexive then $R\cup S$ must be reflexive.

The union of two symmetric relations is also symmetric.

But as the above counterexample shows that does hold for transitivity.

Originally Posted by oldguynewstudent
Let $R_{1}$and $R_{2}$ be equivalence relations on a
b) Is $R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove.
Part b is true. You ought to prove it.

4. Thank you both for your help. However, I am getting more confused.

First Defunkt, I thought I was doing what you said needed to be done by showing arbitrary elements of both $R_1$ and $R_2$ were in the union to prove reflexive. So I don't see how exactly I was working backwards. I know my proofs are not "up to par" and I saw my professor yesterday to get help. I am trying to learn and not trying to be argumentative. Should I maybe have said $a_1$ and $a_2$ were arbitrary? Thank you for your patience and understanding.

Plato, again thank you for your help.

I don't see how transitivity does not work for the union. (1,2) (2,1) (2,3) (3,2) are all in the union.

What if $R_1$={ $(1,1),(2,2),(1,2),(2,1)$} and $R_2$={ $(3,3),(4,4),(3,4),(4,3)$} with their intersection equal the null set. Would that be an equivalence relation?

5. Originally Posted by oldguynewstudent
Plato, again thank you for your help. I don't see how transitivity does not work for the union. (1,2) (2,1) (2,3) (3,2) are all in the union.
Let $R_{1}$and $R_{2}$ be equivalence relations on a set A. $R_{1}\cup R_{2}$ an equivalance relation on A? Prove or disprove.
Consider the set $A=\{1,2,3\}$. $R_1=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}~\&~ R_2=\{(1,1),(2,1),(3,3),(2,2),(1,2)\}$
The union is not transitive. $(1,2)\in R_1\cup R_2~\&~ (2,3)\in R_1\cup R_2\text{ BUT }(1,3)\notin R_1\cup R_2$
Originally Posted by oldguynewstudent
What if $R_1$={ $(1,1),(2,2),(1,2),(2,1)$} and $R_2$={ $(3,3),(4,4),(3,4),(4,3)$} with their intersection equal the null set. Would that be an equivalence relation?
Where did the 4 come from? You cannot throw things about.
The intersection of two transitive relations on the same set is transitive.

6. Originally Posted by Plato
Consider the set $A=\{1,2,3\}$. $R_1=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}~\&~ R_2=\{(1,1),(2,1),(3,3),(2,2),(1,2)\}$
The union is not transitive. $(1,2)\in R_1\cup R_2~\&~ (2,3)\in R_1\cup R_2\text{ BUT }(1,3)\notin R_1\cup R_2$

Where did the 4 come from? You cannot throw things about.
The intersection of two transitive relations on the same set is transitive.
I see the error now that you've drilled it into my thick skull. Thank you for your patience. We're just starting to go over equivalence relations. I really appreciate your help!

For the intersection problem I was proposing two new relations where their intersection would result in the null set. We haven't had that theorem yet.

7. Originally Posted by oldguynewstudent
Thank you both for your help. However, I am getting more confused.

First Defunkt, I thought I was doing what you said needed to be done by showing arbitrary elements of both $R_1$ and $R_2$ were in the union to prove reflexive. So I don't see how exactly I was working backwards. I know my proofs are not "up to par" and I saw my professor yesterday to get help. I am trying to learn and not trying to be argumentative. Should I maybe have said $a_1$ and $a_2$ were arbitrary? Thank you for your patience and understanding.

Plato, again thank you for your help.

I don't see how transitivity does not work for the union. (1,2) (2,1) (2,3) (3,2) are all in the union.

What if $R_1$={ $(1,1),(2,2),(1,2),(2,1)$} and $R_2$={ $(3,3),(4,4),(3,4),(4,3)$} with their intersection equal the null set. Would that be an equivalence relation?
You are getting a little confused here - you are given that $R_1$ and $R_2$ are equivalence relations; now define $R:= R_1 \cup R_2$.
You need to show that $R$ is an equivalence relation.

So for example, when checking for symmetry you will take two arbitrary elements of the set (not of $R_1$ and $R_2$!), let's say a and b, and check if $(a,b) \in R \Rightarrow (b,a) \in R$.
What you showed when you tried proving symmetry is that $(a_1, b_1) \in R_1 \Rightarrow (a_1, b_1) \in R_1 \cup R_2$ and $(a_2, b_2) \in R_2 \Rightarrow (a_2, b_2) \in R_1 \cup R_2$,
but that is always true because $R_1 \subseteq R_1 \cup R_2$ and $R_2 \subseteq R_1 \cup R_2$!

Also, if I came out offensive I am sorry - that was not my intention

8. Originally Posted by Defunkt
You are getting a little confused here - you are given that $R_1$ and $R_2$ are equivalence relations; now define $R:= R_1 \cup R_2$.
You need to show that $R$ is an equivalence relation.

So for example, when checking for symmetry you will take two arbitrary elements of the set (not of $R_1$ and $R_2$!), let's say a and b, and check if $(a,b) \in R \Rightarrow (b,a) \in R$.
What you showed when you tried proving symmetry is that $(a_1, b_1) \in R_1 \Rightarrow (a_1, b_1) \in R_1 \cup R_2$ and $(a_2, b_2) \in R_2 \Rightarrow (a_2, b_2) \in R_1 \cup R_2$,
but that is always true because $R_1 \subseteq R_1 \cup R_2$ and $R_2 \subseteq R_1 \cup R_2$!

Also, if I came out offensive I am sorry - that was not my intention
Not at all, I just did not want to come off argumentative. As Ricky said to Lucy "That 'splains it!" I understand how I was coming from the wrong angle now.

I did not have a professor I could relate to for Discrete, this professor is speaking to my understanding for Combinatorics. So I am a little behind with these proofs but with great help like this, I am catching up.

9. Originally Posted by Defunkt
You are getting a little confused here - you are given that $R_1$ and $R_2$ are equivalence relations; now define $R:= R_1 \cup R_2$.
You need to show that $R$ is an equivalence relation.
$R:= R_1 \cup R_2$ is not necessarily an equivalence relation.
$R:= R_1 \cap R_2$ is necessarily an equivalence relation.

10. Of course, but I was trying to show why the original approach (which led to the result that $R_1 \cup R_2$ is indeed an equivalence relation) was wrong.

It was also my opinion that if he sees that transitivity doesn't always hold for a union of equivalence relations, then it would be easier to set up a counter example for the claim.

11. Okay, gentlemen, let's see if I have gained any understanding on this:

Is $R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Take an arbitrary element $a_{1}\in R_{1}\cap R_{2}\in A$. Since $a_{1}\in R_{1}\cap R_{2}$ then $a_{1}\in R_{1}$ and $a_{1}\in R_{2}$. Since both $R_{1}$ and $R_{2}$ are equivalence relations on A, then $(a_{1},a_{1})\in R_{1}\cap R_{2}$. This shows $R_{1}\cap R_{2}$ is reflexive.

Now take two arbitrary elements $a_{1},b_{1}\in R_{1}\cap R_{2}\in A$. Since $a_{1},b_{1}\in R_{1}\cap R_{2}$ then $a_{1},b_{1}\in R_{1}$ and $a_{1},b_{1}\in R_{2}$. Since both $R_{1}$ and $R_{2}$ are equivalence relations on A, then $(a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cap R_{2}$. This shows $R_{1}\cap R_{2}$ is symmetric.

Fianlly take three arbitrary elements $a_{1},b_{1},c_{1}\in R_{1}\cap R_{2}\in A$. Since $a_{1},b_{1},c_{1}\in R_{1}\cap R_{2}$ then $a_{1},b_{1},c_{1}\in R_{1}$ and $a_{1},b_{1},c_{1}\in R_{2}$. Since both $R_{1}$ and $R_{2}$ are equivalence relations on A, then $(a_{1},b_{1}),(b_{1},c_{1})\in R_{1}\cap R_{2}$. This shows that $R_{1}\cap R_{2}$ is transitive and therefore since the intersection meets all three requirements, it is an equivalence relation.

12. Originally Posted by oldguynewstudent
$R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Take an arbitrary element $a_{1}\in R_{1}\cap R_{2}\in A$. Since $a_{1}\in R_{1}\cap R_{2}$ then $a_{1}\in R_{1}$ and $a_{1}\in R_{2}$. Since both $R_{1}$ and $R_{2}$ are equivalence relations on A, then $(a_{1},a_{1})\in R_{1}\cap R_{2}$. This shows $R_{1}\cap R_{2}$ is reflexive.
That notation is hopelessly confused! Unless you sort it out, you have no hope of ever understanding any of this.

First $R_1\subseteq A\times A$, that is $R_1$ is a set of pairs.
The diagonal $\Delta_A=\{(a,a):a\in A\}$.
Any reflexive relation contains the diagonal: $\Delta_A\subseteq R$ implies that $R$ is reflexive.
A relation is symmetric if it equals its inverse $R=R^{-1}$.

So you should write $(a,b)\in R~\&~(b,c)\in R$ then $(a,c)\in R$: That is transitive.

13. Originally Posted by Plato
That notation is hopelessly confused! Unless you sort it out, you have no hope of ever understanding any of this.

First $R_1\subseteq A\times A$, that is $R_1$ is a set of pairs.
The diagonal $\Delta_A=\{(a,a):a\in A\}$.
Any reflexive relation contains the diagonal: $\Delta_A\subseteq R$ implies that $R$ is reflexive.
A relation is symmetric if it equals its inverse $R=R^{-1}$.

So you should write $(a,b)\in R~\&~(b,c)\in R$ then $(a,c)\in R$: That is transitive.
Thank you Plato, you have given me a new approach to this.

Let me try a new problem to see if I am understanding this better, i.e. clean slate starting over:

$a\equiv b(mod{\atop }n)$ iff $n|(a-b)$. Prove the congruence mod n is an equivalence relation on $\mathcal{\mathbb{Z}}$.

To prove that $a\equiv b(mod{\atop }n)$ is an equivalence relation on $\mathcal{\mathbb{Z}}$, first we show that it is reflexive.

Let $(a_{1},a_{1})\in\mathbb{Z}X\mathbb{Z}$. We need to show that $a_{1}\equiv a_{1}(mod{\atop }n)$ for any $n\in\mathbb{Z}$. $n|(a_{1}-a_{1})$ for any $(a_{1},a_{1})\in\mathbb{Z}X\mathbb{Z}$. So the relation is reflexive.

Second we show that the relation is symmetric.

Let $(a_{1},b_{1})\in\mathbb{Z}X\mathbb{Z}$ we need to show that if $a_{1}\equiv b_{1}(mod{\atop }n)$ then $b_{1}\equiv a_{1}(mod{\atop }n)$. So we assume $n|(a_{1}-b_{1})$ does $n|(b_{1}-a_{1})$?? Yes, because $b_{1}-a_{1}=-(a_{1}-b_{1})$. Therefore the relation is symmetric.

Third we check transitive.

We need to show that if $a\equiv b(mod{\atop }n)$ and $b\equiv c(mod{\atop }n)$ then $a\equiv c(mod{\atop }n)$. We have $n|(a-b)$ and $n|(b-c)$. So $a=b+kn$ and $b=c+jn$, then $a=c+jn+kn$ which can be written as $a = c + (j+k)n$. This proves the relation is transitive and also that it is an equivalence relation.