1

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.

DMcMor
  • 9,407
Adam Caverhill
  • 125

2 Answers2

4

$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$.

Mark Twain
  • 2,157
2

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.

RCT
  • 2,807
  • For R1/R2/R3 are those the only missing values that would make them transitive? – Adam Caverhill Apr 10 '17 at 23:56
  • @AdamCaverhill I'm not claiming that. For example, R1 also has $(4,1)$ and $(1,2)$ but not $(4,2).$ – RCT Apr 10 '17 at 23:57
  • 4
    @AdamCaverhill A comment: You don't need to find all instances where transitivity fails. If it fails just once, then it is not transitive; it only takes one instance to show failure (look back at the definition of transitivity---it involves universal quantifiers). – Mark Twain Apr 10 '17 at 23:58