What is the transitive closure of the relation $\{(1,5),(5,7),(7,9),(1,7),(1,9),(5,9)\}$ on $X=\{1,5,7,9\}$?

I think this relation is already transitive.

  • $(1,5),(5,7) \implies (1,7)$ already exist

  • $(1,5),(5,9) \implies (1,9)$ already exist

  • $(1,7),(7,9) \implies (1,9)$ already exist

Did I miss something or this relation is already transitive so my answer which is $\{(1,5),(5,7),(7,9),(1,7),(1,9),(5,9)\}$ correct?

  • $\begingroup$ What is $A$ that is mentioned in the question? $\endgroup$ – D. Dmitriy Nov 4 '20 at 8:04
  • 1
    $\begingroup$ On X this relation is already transitive indeed. $\endgroup$ – D. Dmitriy Nov 4 '20 at 8:05
  • $\begingroup$ Oh typo it is X sorry and thank you for your answer! $\endgroup$ – Zeroo Nov 4 '20 at 10:17

You are indeed correct that the relation is already transitive. This is easy to see when you visualize the relation as a directed graph like below, where $x$ points to $y$ iff $(x,y) \in R$ (where $R$ is your relation on $X$).

enter image description here

In diagrams like these, transitivity amounts to, whenever you can travel from node $x$ to $y$ and then to node $z$, then there is a path letting you cut across from $x$ to $z$. Basically whenever two sides of a triangle exist, the third is also filled in (though the orientation of the third side depends on the other two).

Using the graph above, follow every path of length two from every node, and you'll always end up finding a "shortcut" path of length one exists from the start to end. Thus, the relation is transitive, and is its own transitive closure.

...granted, this question a bit old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.


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.