# Thread: 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 $\displaystyle R_{1}$and $\displaystyle R_{2}$ be equivalence relations on a set A.

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

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

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

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

b) Is $\displaystyle R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Suppose $\displaystyle a_{1}\in A$ such that $\displaystyle (a_{1},a_{1})\in R_{1}$ and $\displaystyle (a_{1},a_{1})\notin R_{2}$. Then clearly $\displaystyle (a_{1},a_{1})\notin R_{1}\cap R_{2}$. Since $\displaystyle 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 $\displaystyle R_{1}$and $\displaystyle R_{2}$ be equivalence relations on a set A.

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

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

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

Second we need to test the Symmetric property: Let $\displaystyle a_{1},b_{1}\in$ A such that $\displaystyle (a_{1},b_{1}),(b_{1},a_{1})\in R_{1}$ and $\displaystyle a_{2},b_{2}\in$ A such that $\displaystyle (a_{2},b_{2}),(b_{2},a_{2})\in R_{2}$. Clearly if $\displaystyle (a_{1},b_{1}),(b_{1},a_{1})\in R_{1}$ then $\displaystyle (a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cup R_{2}$. Also if $\displaystyle (a_{2},b_{2}),(b_{2},a_{2})\in R_{2}$ then $\displaystyle (a_{2},b_{2})$,$\displaystyle (b_{2},a_{2})\in R_{1}\cup R_{2}$. This proves that $\displaystyle R_{1}\cup R_{2}$ is Symmetric.
You're not following the definition! A relation $\displaystyle R$ is symmetric if $\displaystyle (a,b) \in R \Rightarrow (b,a) \in R$.
Here, in order to show that $\displaystyle R_1 \cup R_2$ is symmetric, you need to show $\displaystyle (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 $\displaystyle a_{1},b_{1},c_{1}\in$ A such that $\displaystyle (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}$ and $\displaystyle a_{2},b_{2},c_{2}\in$ A such that $\displaystyle (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}$. Clearly if $\displaystyle (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}$ then $\displaystyle (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}\cup R_{2}$. Similarly if $\displaystyle (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}$ then $\displaystyle (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{1}\cup R_{2}$. Therefore $\displaystyle R_{1}\cup R_{2}$ is Transitive. Since $\displaystyle 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 $\displaystyle (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 $\displaystyle R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Suppose $\displaystyle a_{1}\in A$ such that $\displaystyle (a_{1},a_{1})\in R_{1}$ and $\displaystyle (a_{1},a_{1})\notin R_{2}$. Then clearly $\displaystyle (a_{1},a_{1})\notin R_{1}\cap R_{2}$. Since $\displaystyle R_{1}\cap R_{2}$ is not Reflexive, it is not an equivalence relation on A.

3. Originally Posted by oldguynewstudent
Let $\displaystyle R_{1}$and $\displaystyle R_{2}$ be equivalence relations on a set A.
a) Is $\displaystyle R_{1}\cup R_{2}$ an equivalance relation on A? Prove or disprove.
Part a is FALSE. Consider the set $\displaystyle A=\{1,2,3\}$.
$\displaystyle 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 $\displaystyle \mathcal{A}$ of all relations of a set $\displaystyle A$.
If $\displaystyle R\in\mathcal{A} ~\&~S\in\mathcal{A}$ if $\displaystyle R$ is reflexive then $\displaystyle 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 $\displaystyle R_{1}$and $\displaystyle R_{2}$ be equivalence relations on a
b) Is $\displaystyle 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 $\displaystyle R_1$ and $\displaystyle 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 $\displaystyle a_1$ and $\displaystyle 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 $\displaystyle R_1$={$\displaystyle (1,1),(2,2),(1,2),(2,1)$} and $\displaystyle R_2$={$\displaystyle (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 $\displaystyle R_{1}$and $\displaystyle R_{2}$ be equivalence relations on a set A. $\displaystyle R_{1}\cup R_{2}$ an equivalance relation on A? Prove or disprove.
Consider the set $\displaystyle A=\{1,2,3\}$. $\displaystyle 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. $\displaystyle (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 $\displaystyle R_1$={$\displaystyle (1,1),(2,2),(1,2),(2,1)$} and $\displaystyle R_2$={$\displaystyle (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 $\displaystyle A=\{1,2,3\}$. $\displaystyle 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. $\displaystyle (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 $\displaystyle R_1$ and $\displaystyle 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 $\displaystyle a_1$ and $\displaystyle 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 $\displaystyle R_1$={$\displaystyle (1,1),(2,2),(1,2),(2,1)$} and $\displaystyle R_2$={$\displaystyle (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 $\displaystyle R_1$ and $\displaystyle R_2$ are equivalence relations; now define $\displaystyle R:= R_1 \cup R_2$.
You need to show that $\displaystyle R$ is an equivalence relation.

So for example, when checking for symmetry you will take two arbitrary elements of the set (not of $\displaystyle R_1$ and $\displaystyle R_2$!), let's say a and b, and check if $\displaystyle (a,b) \in R \Rightarrow (b,a) \in R$.
What you showed when you tried proving symmetry is that $\displaystyle (a_1, b_1) \in R_1 \Rightarrow (a_1, b_1) \in R_1 \cup R_2$ and $\displaystyle (a_2, b_2) \in R_2 \Rightarrow (a_2, b_2) \in R_1 \cup R_2$,
but that is always true because $\displaystyle R_1 \subseteq R_1 \cup R_2$ and $\displaystyle 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 $\displaystyle R_1$ and $\displaystyle R_2$ are equivalence relations; now define $\displaystyle R:= R_1 \cup R_2$.
You need to show that $\displaystyle R$ is an equivalence relation.

So for example, when checking for symmetry you will take two arbitrary elements of the set (not of $\displaystyle R_1$ and $\displaystyle R_2$!), let's say a and b, and check if $\displaystyle (a,b) \in R \Rightarrow (b,a) \in R$.
What you showed when you tried proving symmetry is that $\displaystyle (a_1, b_1) \in R_1 \Rightarrow (a_1, b_1) \in R_1 \cup R_2$ and $\displaystyle (a_2, b_2) \in R_2 \Rightarrow (a_2, b_2) \in R_1 \cup R_2$,
but that is always true because $\displaystyle R_1 \subseteq R_1 \cup R_2$ and $\displaystyle 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 $\displaystyle R_1$ and $\displaystyle R_2$ are equivalence relations; now define $\displaystyle R:= R_1 \cup R_2$.
You need to show that $\displaystyle R$ is an equivalence relation.
$\displaystyle R:= R_1 \cup R_2$ is not necessarily an equivalence relation.
$\displaystyle 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 $\displaystyle 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 $\displaystyle R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Take an arbitrary element $\displaystyle a_{1}\in R_{1}\cap R_{2}\in A$. Since $\displaystyle a_{1}\in R_{1}\cap R_{2}$ then $\displaystyle a_{1}\in R_{1}$ and $\displaystyle a_{1}\in R_{2}$. Since both $\displaystyle R_{1}$ and $\displaystyle R_{2}$ are equivalence relations on A, then $\displaystyle (a_{1},a_{1})\in R_{1}\cap R_{2}$. This shows $\displaystyle R_{1}\cap R_{2}$ is reflexive.

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

Fianlly take three arbitrary elements $\displaystyle a_{1},b_{1},c_{1}\in R_{1}\cap R_{2}\in A$. Since $\displaystyle a_{1},b_{1},c_{1}\in R_{1}\cap R_{2}$ then $\displaystyle a_{1},b_{1},c_{1}\in R_{1}$ and $\displaystyle a_{1},b_{1},c_{1}\in R_{2}$. Since both $\displaystyle R_{1}$ and $\displaystyle R_{2}$ are equivalence relations on A, then $\displaystyle (a_{1},b_{1}),(b_{1},c_{1})\in R_{1}\cap R_{2}$. This shows that $\displaystyle 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
$\displaystyle R_{1}\cap R_{2}$ an equivalence relation on A? Prove or disprove. Take an arbitrary element $\displaystyle a_{1}\in R_{1}\cap R_{2}\in A$. Since $\displaystyle a_{1}\in R_{1}\cap R_{2}$ then $\displaystyle a_{1}\in R_{1}$ and $\displaystyle a_{1}\in R_{2}$. Since both $\displaystyle R_{1}$ and $\displaystyle R_{2}$ are equivalence relations on A, then $\displaystyle (a_{1},a_{1})\in R_{1}\cap R_{2}$. This shows $\displaystyle 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 $\displaystyle R_1\subseteq A\times A$, that is $\displaystyle R_1$ is a set of pairs.
The diagonal $\displaystyle \Delta_A=\{(a,a):a\in A\}$.
Any reflexive relation contains the diagonal: $\displaystyle \Delta_A\subseteq R$ implies that $\displaystyle R$ is reflexive.
A relation is symmetric if it equals its inverse $\displaystyle R=R^{-1}$.

So you should write $\displaystyle (a,b)\in R~\&~(b,c)\in R$ then $\displaystyle (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 $\displaystyle R_1\subseteq A\times A$, that is $\displaystyle R_1$ is a set of pairs.
The diagonal $\displaystyle \Delta_A=\{(a,a):a\in A\}$.
Any reflexive relation contains the diagonal: $\displaystyle \Delta_A\subseteq R$ implies that $\displaystyle R$ is reflexive.
A relation is symmetric if it equals its inverse $\displaystyle R=R^{-1}$.

So you should write $\displaystyle (a,b)\in R~\&~(b,c)\in R$ then $\displaystyle (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:

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

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

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

Second we show that the relation is symmetric.

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

Third we check transitive.

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

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# Intersection of two equivalence relation

Click on a term to search for related topics.