if $R_1$ and $R_2$ are symmetric and transitive, then $R_1 \cup R_2$ is still symmetric and transitive.

173 Views Asked by At

This is an exercise of the assignment we have:

Suppose $R_1$ and $R_2$ are relations on A. Prove (with a formal proof) or confute (with a counterexample) that if $R_1$ and $R_2$ are symmetric and transitive, then $R_1$ $\cup$ $R_2$ is still symmetric and transitive.

I am not so familiar with relations, so that's why I am asking.

I am supposing that there's a tuple $(x, y) \in R_1 \cup R_2$, which means that $(x, y) \in R_1 \lor (x, y) \in R_2$, so we have a proof of the type $P \lor Q$, then we have to prove $P$ and $Q$.

So we have to 2 cases:

Case 1:

$(x, y) \in R_1$

Since $R_1$ is symmetric, then also $(y, x) \in R_1$

(But I don't know how to continue... Same for the Case 2)

Case 2:

$(x, y) \in R_2$

1

There are 1 best solutions below

0
On BEST ANSWER

Symmetric:

Let $(x,y)\in R_1\cup R_2$. Then $(x,y)\in R_1$ or $(x,y)\in R_2$. WLOG, suppose $(x,y)\in R_1$. Now, $R_1$ is symmetric so $(y,x)\in R_1$. Therefore, $(y,x)\in R_1\cup R_2$, so $R_1\cup R_2$ is symmetric.

Transitive: (disprove by counter-example)

Let set $A=\{1,2,3\}$ and relations on $A$,

\begin{eqnarray*} R_1 &=& \{(1,1),\;(1,2),\;(2,1),\;(2,2)\} \\ R_2 &=& \{(3,3),\;(3,2),\;(2,3),\;(2,2)\} \end{eqnarray*}

It's easy to see $R_1$ and $R_2$ are both symmetric and transitive. Now,

$$R_1\cup R_2 = \{(1,1),\;(1,2),\;(2,1),\;(2,2),\;(3,3),\;(3,2),\;(2,3)\}.$$

We have $(1,2),\;(2,3) \in R_1\cup R_2$ but $(1,3) \notin R_1\cup R_2$. So $R_1\cup R_2$ is not transitive.