4
$\begingroup$

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) \cup 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)\ and\ (y,x) \in R,S$ For each (x,y) in R and S there is an (y,x) in R and S so that (x,y) ~ (y,x). Is that correct?

Transitivity: ?

2 Answers 2

13

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).

  • 0
    @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.2017-05-20
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)

  • 0
    You wrote a question in an answer field. Please do not use answer fields for questions.2018-09-15