I have this equivalence relation problem:

Let $R$ and $S$ be two equivalence relations on the same set $A$. Define a new relation $U$ such that $U(x,y) \leftrightarrow [R(x,y) \text{ or } S(x,y)]$. Is $U$ necessarily an equivalence relation?

I said that is was an equivalence relation because $U$ is only true if $R$ or $S$ is true, and only depends on one. I do not know know exactly how to explain it, or prove this. Should I use proof by contradiction to prove this and make the negated statement $!U(x,y) \leftrightarrow {![R(x,y) \text{ or } S(x,y)]}$ and from this we can see that $U$ is an equivalence relation because the negation is saying that $R(x,y)$ or $S(x,y)$ isn't an equivalence when it actually is?

I am kind of stuck so any help is appreciated.


In order to prove that $U$ is an equivalence relation, you need to use the definition: prove that $U$ is reflexive, symmetric and transitive. If you try to do that but it doesn't work, you can try to disprove the claim that $U$ is always an equivalence relation by giving a counterexample: equivalence relations $R$ and $S$ such that the corresponding $U$ isn't an equivalence relation (that is, it either isn't reflexive, isn't symmetric or isn't transitive); you can use your failed proof attempts to guide you in the construction.

  • 1
    $\begingroup$ And to add a hint to this, maybe it'll save you some time: reflexivity and symmetry follow directly from those properties of $R$ and $S$, so focus on transitivity. $\endgroup$ – G. Bach Oct 7 '13 at 15:38

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.