0
$\begingroup$

Does this proof look right? Thanks!

Suppose $R_1$ and $R_2$ are relations on set $A$. For each part give either a proof or a counterexample to justify your answer.

If $R_1$ and $R_2$ are transitive, must $R_1 \cap R_2$ be transitive?

Let $x, y, z$ be arbitrary elements of $A$. Suppose that $(x, y) \in R_1 ∩ R_2$ and $(y, z) \in R_1 ∩ R_2$. Then $(x, y)$ and $(y, z) \in R_1$ and $(x, y)$ and $(y, z) \in R_2$. This would mean that $(x, z) \in R_1$ and $R_2$ since $x, y, z$ are arbitrary. Because $x, y, z$ are arbitrary, $(x, z) \in R_1 ∩ R_2$, meaning $R_1 \cap R_2$ is transitive on $A$.

$\endgroup$
1
$\begingroup$

You have the right idea, but some of what you’ve actually said isn’t quite right.

This would mean that $(x,z)\in R_1$ and $R_2$ since $x,y,z$ are arbitrary.

No, it means that $(x,z)\in R_1$ and $(x,z)\in R_2$ because $R_1$ and $R_2$ are transitive; it has nothing to do with whether $x,y$, and $z$ were arbitrary or hand-picked.

Because $x,y,z$ are arbitrary, $(x,z)\in R_1\cap R_2$

No, $(x,z)\in R_1\cap R_2$ because $(x,z)\in R_1$ and $(x,z)\in R_2$; here again $x,y$, and $z$ could have been hand-picked.

It’s at the very last step that the arbitrary nature of the choice of $x,y$, and $z$ comes into play. What you want to say at the end is:

Since $x,y$, and $z$ were arbitrary elements of $A$ such that $(x,y),(y,z)\in R_1\cap R_2$, it follows that $R_1\cap R_2$ is transitive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.