0
$\begingroup$

If we have two transitive relations $R_1, R_2$ on a set $A$, then I know that if $$R_3 = R_1 \cup R_2$$ that $R_3$ is not transitive.

And if $$R_3 = R_1 \cap R_2$$ then $R_3$ is transitive. But I can't figure out why my "proof" stating the opposite of those is false.

My reasoning went as follows: For $R_3 = R_1 \cup R_2$, Let $x,y,z\in A$ and assume $(x,y),(y,z),(x,z)\in R_1$. Since $R_1\subseteq R_1 \cup R_2 = R_3$ then $(x,y),(y,z),(x,z)\in R_3$ and similarly the same argument for $R_2$ so $R_3$ is transitive.

For $R_3 = R_1 \cap R_2$ let $A = \lbrace 1,2,3,4 \rbrace$ and have $R_1 = \lbrace (1,2),(2,3),(1,3) \rbrace$ and $R_2 = \lbrace (1,2),(2,4),(1,4) \rbrace$ hence $R_1$ and $R_2$ are transitive but $R_3 = \lbrace (1,2) \rbrace$ which is not transitive

Can someone point out my logical flaws in both arguments? I know one can show counter examples for the first one but I don't see where I'm making poor arguments in both of them as I was told we can handle relations just like any other type of set.

$\endgroup$

2 Answers 2

2
$\begingroup$

Firstly, in order to prove transitivity of some relation $R$, you need to show that $(x,y),(y,z)\in R$ implies $(x,z)\in R$.

The problem with your "proof" for the union is that you assume that $(x,y),(y,z)$ both belong to the same relation $R_i$. In that case, you indeed have $(x,z)\in R_i$ and hence $(x,z)\in R_3$. The problem occurs when you take $(x,y)\in R_1$ and $(y,z)\in R_2$. For example, if $R_1=\{(x,y)\in\mathbb N^2\mid x-y\text{ is divisible by 2}\}$ and $R_2=\{(x,y)\in\mathbb N^2\mid x-y\text{ is divisible by 3}\}$, both $R_i$ are transitive, but $R_1\cup R_2$ isn't: Consider $(0,2)\in R_1$ and $(2,5)\in R_2$. Do you think $(0,5)\in R_1\cup R_2$?

Your "counterexample" concerning the intersection isn't actually a counterexample! $R_3$ is indeed transitive. More precisely, we need to prove $$\forall x,y,z: (x,y),(y,z)\in R_3 \implies (x,z)\in R_3.$$

This implication is vacuously tue, that is, the antecedent (the part before $\implies$) is never satisfied, and thus the implication holds (here we use that the implications "false implies true" and "false implies false" are both correct).

$\endgroup$
0
$\begingroup$

This is really two questions:

Why $R_3 = R_1 \cup R_2$ is not transitive. The property must hold for two arbitrary elements of the relation. Say $(x, y) \in R_1$ and $(y, z) \in R_2$ but not the reverse. They are both elements of the relation $R_3$ but there's no guarantee that $(x, z) \in R_3$ inherited from either $R_1$ or $R_2$. You can come up with a specific small counterexample.

Why your example doesn't contradict the fact that $R_3 = R_1 \cap R_2$ is transitive. Basically, there are no pairs of the form $(a, b), (b, c) \in R_3$, so the property holds vacuously.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .