# Equivalence relations with $\cap$, $\cup$ and $\circ$

I have the relations $E_1$ and $E_2$.

A reflexive, symmetric and transitive property shows that two relations are equivalent to each other. I need to prove if this is true for the following

a) $E_1 ∩ E_2$

b) $E_1 ∪ E_2$

c) $E_1 ∘ E_2$

I found out that a) is true, but I am not sure about it. This is my proof for transitivity:

$E_1 ∩ E_2 ⇒ (a, b, c) ∈ E_1 ∧ (a, b, c) ∈ E_2 ⇒ \\((a, b) ∈ E_1 ∧ (b, c) ∈ E_1 → (a, c) ∈ E_1) ∧ ((a, b) ∈ E_2 ∧ (b, c) ∈ E_2 → (a, c) ∈ E_2)$

Also I found different arguments on the internet, so I'm pretty unsure about this.

Regarding b) $E_1 ∪ E_2$ a friend found out that this is not transitive and they wanted to prove it with an example. The example is the following:

$A = \{1,2,3\}$

$E_1 = \{(1,2), (2,1), (2,2)\}$

$E_2= \{(1,3), (3,1), (3,3)\}$

$E_1 ∪ E_2 = \{(1,2), (2,1), (2,2), (1,3), (3,1), (3,3)\}$

This is transitive, isn't it? If not, what is it what I did not understand?

And maybe you can help me with with c), as well.

• Regarding your friend's example, the union relation indeed isn't transitive. – Yuval Filmus Nov 15 '15 at 16:09
• A relation being reflexive, symmetric and transitive means it's called an equivalence relation. The claim is not that "$E_1$ and $E_2$ are equivalent to each other": it's that they are equivalence relations. Unfortunately, your attempt to prove transitivity makes no sense: $X\rightarrow Y$ means "If X is true, then Y must be true, too" but you've written "$E_1\cap E_2 \Rightarrow ..." and$E_1\cap $E_2$ isn't something that can be true or false: it's a set, not a Boolean value. $(a,b,c)$ cannot be an element of $E_1$, since $E_1$ is a binary relation, not ternary. – David Richerby Nov 15 '15 at 16:10
• Your example to prove non-transitivity of the union doesn't work because your $E_1$ and $E_2$ aren't equivalence relations, they're not reflexive or transitive. However, given those relations $E_1$ and $E_2$, you've calculated $E_1\cup E_2$ correctly and you're correct that it's not transitive. I'm not sure why you're surprised that it's not transitive: you're looking for $E_1$ and $E_2$ such that $E_1\cup E_2$ isn't an equivalence relation, meaning you need $E_1\cup E_2$ to be non-reflexive and/or non-symmetric and/or non-transitive. – David Richerby Nov 15 '15 at 16:13
• Can you explain why this question belongs here on Computer Science? It looks like a pure math question to me (and thus more suitable to Math.SE). We are not 100% averse to pure math questions if the question can explain why it needs to be answered from a CS perspective -- do you have something like that in mind, or would this be reasonable to migrate to Math.SE? – D.W. Nov 15 '15 at 18:09
• @Lintu I'm sorry -- I didn't mean to belittle you by saying I didn't know why you were surprised. You were trying to prove that $E_1\cup E_2$ isn't always an equivalence relation and you almost succeeded, so I was expecting you to be happy rather than surprised. ("Almost" because the relations you started with weren't reflexive but, if you make them reflexive, you're done). I hope my other comments were more helpful to you. I think the best thing you can do is talk to your TA or professor about this because I think you need a more interactive style of help than can happen on the internet. – David Richerby Nov 15 '15 at 21:55

## 1 Answer

Here are some hints:

a) If $E_1,E_2$ are equivalence relations then so is $E_1 \cap E_2$. The proof is just by "unpacking" the definitions. (More generally, every class defined by universal statements – those of the form $\forall x_1,\ldots,x_n \phi(x_1,\ldots,x_n)$ – is closed under intersection.)

b) When trying to prove that $E_1 \cup E_2$ is transitive, we get stuck in the following case: if $a E_1 b$ and $b E_2 c$ then we have to show that $a E_1 c$ or $a E_2 c$, though there is no reason to believe that this must be the case. This helps you construct a counterexample.

c) When trying to prove that $E_1 \circ E_2$ is symmetric, we get stuck: if $a E_1 x E_2 b$ then there is no particular reason that $b E_1 y E_2 a$ for some $y$. This helps you construct a counterexample.

• Thanks Yuval, I prove b and c by choosing one counterexample, because it exists at least one example that doesn't have one of the properties? – LSR Nov 16 '15 at 21:03
• Well, to show that b) and c) aren't necessarily equivalence relations, by far the easiest way is to give explicit counterexamples. – Yuval Filmus Nov 16 '15 at 22:50