If $R_1$ and $R_2$ are relations on A, must $R_1 \cup R_2$ be transitive?

355 Views Asked by At

I have a very elementary question to ask, so please do bare with me. My goal is to show by counterexample that if two sets, $R_1$ and $R_2$ are transitive, then $R_1 \cup R_2$ is not necessarily transitive. It is easy to concoct one counterexample for the case of two sets, such that

$$R_1 = \{(a,b)|a<b\}$$

and

$$R_2=\{(a,b)|b<a\}$$

so I will not go into that in detail. I am more curious about the counterexample that my book uses, which asserts that one possible counterexample is to consider a set

$$A=\{1, 2, 3\}$$

where

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

and $$R_2=\{(2,3)\}.$$

However, I don't understand how these two sets fit the definition of transitive, as a set is said to be transitive iff

$$R\circ R\subset R$$

so if

$$(1,2) \in R_1 \circ R_1$$

then by the definition of the composition

$$(1,2) \in \{(a,b) \in A \times A|\exists_{z\in A}((a,z)\in R_1 \text{ and } (z,a) \in R_1)\} $$

but there is no intermediate z to make this true, so I am not sure how this fits the definition of transitive. Furthermore, if we use an alternate definition, such that for every $x,y,z$, if $xRy$ and $yRz$, then $xRz$, we still find (according to my flawed idea of transitivity) that $R_1$ does indeed relate $1$ to $2$ in $A$ and $2$ to $1$ in $A$, but not $1$ to $1$ in $A$ or $2$ to $2$ in $A$ because $(2,2)$ and $(1,1)$ are not elements of $A$, so I again conclude that $R_1$ is not transitive.

Thank you for considering my question.

1

There are 1 best solutions below

0
On BEST ANSWER

The relations $R_1$ and $R_2$ are indeed transitive.

A relation $R$ is not transitive if it's possible to find elements $x,y,z$ such that $(x,y)\in R$, $(y,z)\in R$, but $(x,z)\notin R$.

Such a choice is possible neither for $R_1$ nor for $R_2$, so they qualify as transitive.


Note that $R_1\circ R_1=\emptyset$ (and the same for $R_2$), which is just the observation that for no $x,y,z$ we can have $(x,y)\in R_1$ and $(y,z)\in R_1$.

On the other hand, if $R=R_1\cup R_2$, we have $R\circ R=\{(1,3)\}\not\subset R$.