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?
Asked
Active
Viewed 536 times
8
-
1From $(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 01:27
-
$(c,c)$ is not a statement, $(c,c)\in R$ is. – Carsten S Mar 24 '15 at 08:38
2 Answers
13
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.
YoTengoUnLCD
- 13,384
7
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.
Milo Brandt
- 60,888