I have a set of relations, shown below:

$R=\{(a,b), (b,c), (c,a)\}$ for $A= \{a,b,c\}$

According to my professor, this relation is transitive but I don't understand why. I was under the impression that any given three relations of a set of relations have to follow the $aRb, bRc, aRc$ pattern but since $aRc$ isn't in the set then it'd fail the test since $aRc$ and $cRa$ aren't equivalent. I'm sure I'm missing something, but I don't understand what.

  • 4
    $\begingroup$ Probably there is a typo and $(c,a)$ should be $(a,c)$. The relation as written is not transitive. In fact, there are three reasons: (1) $aRb\wedge bRc$ but not $aRc$; (2) $bRc \wedge cRa$ but not $bRa$; (3) $cRa\wedge aRb$ but not $cRb$. $\endgroup$ – vadim123 May 27 '13 at 22:13
  • 2
    $\begingroup$ Either there's a typo, as Vadim pointed, or your prof. is wrong. $\endgroup$ – DonAntonio May 27 '13 at 22:17
  • 1
    $\begingroup$ You don't have a set of relations, you have only one relation, $R$. $\endgroup$ – Prateek Dec 30 '13 at 14:56

As expressed, the relation $R$ fails to be transitive. Indeed, we need $(a, c) \in R$ and instead of $(c, a) \in R$, as $(c, a)$ poses a number of problems in terms of the relation being transitive:

As written:

  • $(a, b), (b, c) \in R,$ but $(a, c) \notin R$, as you observe.
  • Furthermore: $(c, a), (a, b) \in R$ but $(c, b) \notin R$.
  • And, $(b, c), (c, a) \in R$, but $(b, a)\notin R$.

For each reason above, transitivity fails.

So $(c, a) \in R$ seems to be the ill-placed, perhaps misprinted pair in $R$, which if replaced by $(a, c)$ would alleviate these failures, and the relation would then be transitive.

  • $\begingroup$ Thanks for the quick responses, everybody. I noticed this practice exam that we received in class has solutions with a few (assumed) typographical issues. A follow up question: Is a set of relations R={(a,a), (b,b), (c,c)} also not transitive? At a glance I want to say no since I can't see any logical link that would let me say aRc, but I'm really not very good at mathematics as a whole and this is all one big uphill battle for me $\endgroup$ – Harry Tuttle May 27 '13 at 23:00
  • $\begingroup$ Yes, to your follow up question: it is vacuously true that it is transitive, since there are no counterexamples for which it is NOT transitive. A relation has a property, unless a counterexample exists. Your follow-up relation is symmetric, for the same reason. $\endgroup$ – Namaste May 27 '13 at 23:23
  • $\begingroup$ Excellent information. Thank you! $\endgroup$ – Harry Tuttle May 27 '13 at 23:59
  • $\begingroup$ You're welcome, Harry! Just hang in there...you'll get the hang of the class! $\endgroup$ – Namaste May 28 '13 at 0:00
  • $\begingroup$ @amWhy: nice discourse ... +1 $\endgroup$ – Amzoti May 28 '13 at 0:36

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.