2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Regarding your friend's example, the union relation indeed isn't transitive. $\endgroup$ – Yuval Filmus Nov 15 '15 at 16:09
  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 15 '15 at 16:10
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 15 '15 at 16:13
  • 3
    $\begingroup$ 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? $\endgroup$ – D.W. Nov 15 '15 at 18:09
  • 3
    $\begingroup$ @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. $\endgroup$ – David Richerby Nov 15 '15 at 21:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – LSR Nov 16 '15 at 21:03
  • $\begingroup$ Well, to show that b) and c) aren't necessarily equivalence relations, by far the easiest way is to give explicit counterexamples. $\endgroup$ – Yuval Filmus Nov 16 '15 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.