5

Let $R \subseteq A \times A$ and $S \subseteq A \times A$ be two arbitary equivalence relations. Prove or disprove that $R \cup S$ is an equivalence relation.

Reflexivity: Let $(x,x) \in R$ or $(x,x) \in S \rightarrow (x,x) \in R \cup S$

Now I still have to prove or disprove that $R \cup S$ is symmetric and transitive. How can I do that?

My guess for symmetry is: R and S are equivalence relations, which means that $(x,y), (y,x) \in R \cup S$ For each $(x,y)$ in R and S there is an $(y,x)$ in $R$ and $S$ so that $(x,y) \sim (y,x)$. Is that correct?

Transitivity: ?

NON
  • 9
user3001
  • 153

2 Answers2

15

Transitivity fails. Let $A = \{1,2,3\}$, $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ and $S = \{(1,1), (2,2), (3,3), (2,3), (3,2)\}$, then $R \cup S$ contains both $(1,2)$ and $(2,3)$, but not $(1,3)$.

The symmetry could be worded better, but is alright. The important thing is that if $(x,y) \in R \cup S$ then $(x,y) \in R$ or $(x,y) \in S$, but both $R$ and $S$ are symmetrical so $(y,x)$ must be contained in at least one of them (here I use "or" instead of "and" you have used).

dtldarek
  • 37,381
  • And just to add, though trivial, its reflexice too, I guess. – Mahesha999 Jan 23 '15 at 08:57
  • It is not a proof, but a counter example. You should prove it. – Hamio Jiang May 19 '17 at 16:17
  • 3
    @HamioJiang If you want to disprove some theorem starting with "for all", a counterexample is enough. – dtldarek May 19 '17 at 20:04
  • @dtldarek there is no theorem. It just asks whether RUS is an equivalence relation or not. If it is, prove it. If it is not, prove it. – Hamio Jiang May 19 '17 at 22:28
  • @HamioJiang A bit of flexibility would not kill you. Theorem, lemma, claim, statement, whatever, the name is unimportant, and it does not need to be clearly labeled. I guess that next you will nit-pick about lack of "for all" – sure, you are welcome to disagree, for me that answer is fine as it stands. – dtldarek May 20 '17 at 07:46
  • @dtldarek Actually, you are right. It says to disprove the statement. To disprove a statement only need to find its counter example. It can be restated as, to disprove "for all, P is true( or false)", we need to prove its negation "there exists, such that P is false (or true). However, for me, I want to show a proposition that " for all, negation P is false (or true)", because I think it is more interesting. Sorry for the irrational "dislike". I've liked your solution now. – Hamio Jiang May 20 '17 at 10:53
0

I don't know if i m right or wrong. But here is how i can think of it.

Lets say R and S are two equivalence relations on nonempty set A.

To answer whether R union S is equivalence relation? consider the fact that R forms partitions on A and S also forms some partitions

My intuition: taking union of R and S is equivalent to taking union of their partitions (haven't proved it yet)

case 1: if partitions of R and S overlap imperfectly, partitions formed after union are not disjoint hence R union S can't be equivalence relation

case 2: if partitions of R contained in those of S perfectly, which happens when either of them is subset of one another , then in their union one set of partitions can be dropped, and rest of the partitions will be disjoint and their union generates whole A. thus R union S must be equivalence in this case

case 3: if partitions don't overlap at all (can't happen)

Ashish kakran
  • 1
  • You wrote a question in an answer field. Please do not use answer fields for questions. – amWhy Sep 15 '18 at 14:46