2
$\begingroup$

I have been working on one of the problem from Velleman's How to prove book and there is a relation $R$ like this:

$R = \{(a,b), (b,a), (a,d), (b,d)\}$

We have to find out if $R$ is transitive.

Now, looking at the example, I concluded that it isn't transitive since $(a,b) \land (b,a) \implies (a,a)$ doesn't hold for relation $R$. But the answer given here says that it is transitive. Am I missing something ?

$\endgroup$
2
$\begingroup$

For a relation $R$ to be transitive, we require that if $(x,y) \in R$ and $(y,z) \in R$, then it must also be the case that $(x,z) \in R$. As you have correctly observed, for your example, $(a,b) \in R$ and $(b,a) \in R$, but $(a,a) \notin R$.

So your relation is not transitive and the answer on the website you found is wrong. If we add $(a,a)$ and $(b,b)$ to the relation, it will become transitive, however.

$\endgroup$
  • $\begingroup$ The relation will not become transitive if we add $(a,a)$, we have to add $(a,a)$ and $(b,b)$ for transitivity. $\endgroup$ – CameronJWhitehead Feb 22 '15 at 11:21
  • $\begingroup$ @CameronJWhitehead Ah yes, you are right, I missed that one. $\endgroup$ – mrp Feb 22 '15 at 11:23

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.