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?

  • 1
    $\begingroup$ 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)$. $\endgroup$
    – J126
    Mar 24 '15 at 1:27
  • $\begingroup$ $(c,c)$ is not a statement, $(c,c)\in R$ is. $\endgroup$
    – Carsten S
    Mar 24 '15 at 8:38

When unsure about this things, make a drawing: enter image descr

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.

  • $\begingroup$ Interesting! Thank you! $\endgroup$ 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.

  • 2
    $\begingroup$ Thanks I like the dropping the "middle" elements analogy $\endgroup$ Mar 24 '15 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.