Intersect and Union of transitive relations

16.3k Views Asked by At

Let $R$ and $S$ be relations on a set $A$. Assume $A$ has at least three elements.

These are my best guesses at these two proofs. The first one I don't feel confident about at all, as it seems I'm making too many assumptions.

If $R$ and $S$ are transitive, then $R \cap S$ is transitive

Let $(a,b),(b,c) \in R \cap S$ $\implies$

$(a,b),(b,c)\in R$ and $(a,b),(b,c)\in S$ $\implies$

$(a,c)\in R$ and $(a,c) \in S$ (as $R$ and $S$ are transitive) $\implies$

$(a,c) \in R \cap S$.

Thus, $R \cap S$ is transitive.

If $R$ and $S$ are transitive, then $R \cup S$ is transitive

Proof by counterexample:

If $A = \{x,y, z\}$, suppose $R = \{(x,y)\}$ and $S = \{(y,z)\}$

$R$ and $S$ are both transitive by default.

However, $R \cup S$ is not transitive because $(x,z)$ is not a member of $R \cup S$.

2

There are 2 best solutions below

0
On

These both look perfectly good to me.

For the counterexample, you may want to specify that $x$, $y$, and $z$ are all distinct (I suspect you had that in mind anyway). For example, you could use $\{1,2,3\}$ instead of $\{x,y,z\}$.

0
On

The only glitch is that you should say

Let $x,y,z\in A$, with $x,y,z$ pairwise distinct

instead of $A=\{x,y,z\}$ because you don't know that $A$ has exactly three elements.

The rest of the arguments are good.