Prove/disprove that if R and S are transitive then R union S is transitive

3.1k Views Asked by At

The problem reads:

Let R and S be relations on a set A. If R and S are transitive then R$U$S is transitive.

I know from a homework problem that R$U$S is not transitive, but I do not know why.

Wouldn't R$U$S be: $\forall$ x,y,z $\in$ A (((xRy ^ yRz) v (xSy ^ ySz)) $\rightarrow$ R$U$S is transitive.

But what if there were some (x,y) $\in$ R and (y,z) $\in$ S such that x does not relate to z $\in$ R$U$S?

Am I on the right track?

Thank you.

EDIT:

Counterexample: Let R {(1,2)} and S {(2,3)}. Then R and S are transitive but R$U$S is not.

1

There are 1 best solutions below

2
On

Try this:

$R=\{(1,2)\}$

$S=\{(2,1)\}$

$R$ and $S$ are both transitive, but $R \cup S=\{(1,2),(2,1)\}$ is not