I have a relation $S$ on $A = \{1, 2, 3, 4, 5\}$, which isn't transitive, and I don't get why.
$S = \{(1, 1),(1, 2),(1, 4),(2, 1),(2, 2),(2, 3),(3, 2),(3, 3),(3, 4),(4, 1),(4, 3),(4, 4)\}$
According to my understanding, it should be transitive, so I'm clearly missing something.
Apparently $(1,3)$ is in the transitive closure of $S$ which I don't understand why, since $1 → 2$ and $2 → 3$ so $1 → 2 → 3$. So why is $(1, 3)$ necessary in order for the relation to be transitive?
Hope you can help me get a better understanding for this. Thanks.
A relation $R$ is transitive if any time we have pairs of the form $(a,b)$ and $(b,c)$ in $R$, it must also be the case that $(b,c) \in R$.
As you have observed, $(1,2) \in S$ and $(2,3) \in S$, so these are two pairs of the form $(a,b)$ and $(b,c)$, but $(1,3) \notin S$, which is required by transitivity. So by definition, the relation is not transitive. You can find other pairs in $S$ that also violate the transitivity conditions.