Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$).
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.
