I was studying relations and functions and transitive relations were defined as :

$$R=\{(x,y)\} ; xRy ~\text{and}~ yRz \implies xRz$$

But what about a single element $(a,b)$?

For example, if the relation was

$$R = \{(1,2),(2,1),(1,1),(2,2)\}$$

Then clearly, it is transitive, but if the relation were : $$R = \{(1,2),(2,1),(1,1),(2,2),(5,6)\}$$

Or simply :


Then are these relations transitive ?

  • $\begingroup$ You might want to change the question in the title to the one actually being asked. (First and foremost, replace "set" by "relation".) $\endgroup$ – martin.koeberl May 10 '17 at 1:34

Yup, that's transitive! For every triple of elements $a, b, c$, if $aRb$ and $bRc$ then $aRc$. It doesn't matter that there are some elements - namely, $5$ and $6$ - which can't be "extended" to form a triple. There's no more to transitivity than the definition you wrote above.

  • $\begingroup$ Then what is '$c$' here ( in my example)? Is it defined to be transitive or there is any explanation? $\endgroup$ – Jaideep Khare May 10 '17 at 1:23
  • 1
    $\begingroup$ @JaideepKhare You're misunderstanding the definition. The definition just says whenever you have such a triple $a, b, c$, then [stuff]. It doesn't say that every element is part of some triple. The only way a relation $S$ is non-transitive is if there are three elements $a, b, c$ with $aSb$, $bSc$, but not $aSc$ - can you find such a triple of elements in this case? $\endgroup$ – Noah Schweber May 10 '17 at 1:24
  • $\begingroup$ Oh, now I understand, I think I misunderstood 'if ...(..)' as 'iff...(..)'. Right? $\endgroup$ – Jaideep Khare May 10 '17 at 1:26
  • $\begingroup$ @JaideepKhare Yeah, it's just a one-way implication. In particular, the empty relation is transitive! $\endgroup$ – Noah Schweber May 10 '17 at 1:41
  • 1
    $\begingroup$ @BrianTung It is a mystery to me that what do you mean by 'Not quite', btw thanks for your explanation! $\endgroup$ – Jaideep Khare May 10 '17 at 1:48

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.