Why isn't $\{(1, 1), (1, 2), (2, 1)\}$ transitive

4k Views Asked by At

I've been given a set of relations on $\{1,2,3,4\}$

\begin{align*} R1 &= {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}\\ R2 &= {(1, 1), (1, 2), (2, 1)}\\ R3 &= {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}\\ R4 &= {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}\\ R5 &= {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}\\ R6 &= {(3, 4)}. \end{align*}

And I've been told that $R4, R5, R6$ are transitive but the rest are not. I understand the nature of transitivity, if $(x,y)$ and $(y,z)$ are present then $x,z$ must be present, but I don't know how to apply this to examples given. $R6$ makes sense, there's no counterexample so it's already proven vacuously. But why isn't $R2$ transitive?

Anyone that can run down in detail each of the examples would help my understanding greatly.

2

There are 2 best solutions below

3
On BEST ANSWER

R1: We have $(3,4)$ and $(4,1)$ but not $(3,1).$

R2: We have $(2,1)$ and $(1,2)$ but not $(2,2).$

R3: We have $(2,1)$ and $(1,4)$ but not $(2,4).$

R4: You can check by exhaustion or notice that this is the relation "$>$".

R5: You can check by exhaustion or notice that this is the relation "$\leq$".

R6: Vacuous, as you said.

2
On

$R_2$ isn't transitive because $(2,1) \in R_2$ and $(1,2) \in R_2$, but $(2,2) \notin R_2$.

[Here, I've taken $(x,y) = (2,1)$, $(y,z) = (1,2)$, $(x,z) = (2,2)$.]

Another example: $R_1$ isn't transitive because $(3,4) \in R_1$ and $(4,1) \in R_1$, but $(3,1) \notin R_1$.