# Is the given relation transitive?

Consider the relation:

$$R = \{(a,b), (a,c), (c,c), (b,b), (c,b), (b,c)\}$$ on the set $A = \{a,b,c\}$. Is $R$ transitive? I said no because

$$[(c, c) \wedge (a, c)] \Longrightarrow (c,a)$$ is a false statement. Is my reasoning correct?

• From $(c,c)$ and $(a,c)$ transitivity would yield $(a,c)$ again. To break transitivity you would need $(x,y)$ and $(y,z)$, but not $(x,z)$.
– J126
Mar 24 '15 at 1:27
• $(c,c)$ is not a statement, $(c,c)\in R$ is. Mar 24 '15 at 8:38

When unsure about this things, make a drawing: Transitivity means that if you can get somewhere through some route (for example, from $a$ to $c$ doing $a\to b\to c$) you must be able to get there directly ($a\to c$).

I hope this is easily seen in the drawing.

• Interesting! Thank you! Mar 24 '15 at 1:47

No, your statement is incorrect. I think you have something backwards - it looks like you want to say that $(x,z)$ and $(y,z)$ being a set means that $(x,y)$ is too - but this is a distinct condition from transitivity. Perhaps it would be clearer to write that $(a,c)$ and $(c,c)$ being in $R$ means that if we drop the "middle" elements (i.e. the $c$), then the result, $(a,c)$, is in $R$ too - and it is.

$R$ happens to be transitive, in fact - you can notice this because it can be written as $R=\{a,b,c\}\times \{b,c\}$ - that is, $(x,y)$ is in $R$ if and only if $y$ is $b$ or $c$. It's clearly transitive as that means if $(x,y)$ and $(y,z)$ are in $R$, then $z$ is $b$ or $c$ and hence $(x,z)$ is in $R$ too.

• Thanks I like the dropping the "middle" elements analogy Mar 24 '15 at 1:45