Given a binary relation $\mathcal{R}$ on a set $A$, you can be assured that the relation $\mathcal{R} \cup \mathcal{R}^{-1}$ is symmetric. (I can give a proof of this, if you would like.)

I wanted to write some similar result for transitivity. I realized that although $\mathcal{R} \cup \mathcal{R}^{-1}$ is always symmetric for any relation $\mathcal{R}$, it isn't enough for transitivity because given $(a,b) \in \mathcal{R}$, we would have $(b,a) \in \mathcal{R}^{-1}$, so we would at least need to make sure that $(a,a) \in \mathcal{R} \cup \mathcal{R}^{-1}$.

Thus our next candidate to try is $\mathcal{R} \cup \mathcal{I}_A \cup \mathcal{R}^{-1}$, where $\mathcal{I}_A$ is the identity relation, also called the diagonal of $A$, defined as $\mathcal{I}_A=\{(a,a):a \in A\}$. But this isn't enough either if $\mathcal{R}$ isn't transitive. So impose $\mathcal{R}$ is transitive (this implies $\mathcal{R}^{-1}$ is also transitive; I can give a proof of this if you would like), and we might be closer to saying $\mathcal{R} \cup \mathcal{I}_A \cup \mathcal{R}^{-1}$ is transitive. So I tried to prove this but then I came up with a counterexample: \begin{align} \mathcal{R}&=\{(a,b),(b,c),(a,c),(d,b),(d,c)\} \\ \mathcal{R}^{-1}&=\{(b,a),(c,b),(c,a),(b,d),(c,d)\} \end{align} Now $(a,b) \in \mathcal{R} \cup \mathcal{I}_A \cup \mathcal{R}^{-1}$ and $(b,d) \in \mathcal{R} \cup \mathcal{I}_A \cup \mathcal{R}^{-1}$, but $(a,d) \notin \mathcal{R} \cup \mathcal{I}_A \cup \mathcal{R}^{-1}$. So I still haven't come up with something that works. How can I continue to make $\mathcal{R} \cup \mathcal{I}_A \cup \mathcal{R}^{-1}$ transitive? What other relations can I "union in" to come up with a transitive set? I'm trying to discover and prove a nice little theorem here...

Thanks for your help!

  • 3
    $\begingroup$ What you want is basically what is done here: en.m.wikipedia.org/wiki/Transitive_closure $\endgroup$ – symplectomorphic Mar 15 '15 at 6:45
  • $\begingroup$ If you're ok with the relation being an equivalence relation, then you can just partition $A$ and let the partition define the relation. $\endgroup$ – Gyu Eun Lee Mar 15 '15 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.