2
$\begingroup$

This is a homework question and I am stuck.

Binary relation R is transitive and symmetric if and only if $R=R^{-1}∘R$

The "only if" way is trivial.

On the "if" way, I worked out that given $R=R^{-1}∘R$ we have $R\subseteq R^{-1}$ , but this doesn't gives symmetry since symmetry requires $R^{-1}\subseteq R$.

$\endgroup$
  • $\begingroup$ Showing symmetry isn't very hard if you know what's written here: math.stackexchange.com/questions/234891/… (Let $S = R^{-1} \circ R$ then compute $S^{-1}$.) $\endgroup$ – Myself Mar 5 '14 at 12:36
  • $\begingroup$ @Myself You're right. I should try work out transitivity given symmetry now. $\endgroup$ – sjtufs Mar 5 '14 at 12:44
  • $\begingroup$ Hint Note that transitivity means $R\circ R\subseteq R$. Spoiler But you have just shown that $R = R^{-1}$. Thus $R\circ R = R\circ R^{-1} = R$. $\endgroup$ – Myself Mar 5 '14 at 12:50
  • $\begingroup$ @Myself Yes, Thank you $\endgroup$ – sjtufs Mar 5 '14 at 12:54
2
$\begingroup$

As mentioned in the comments, we can use the hypothesis $R = R^{-1} \circ R$ to derive: $$R^{-1} = (R^{-1} \circ R)^{-1} = R^{-1} \circ (R^{-1})^{-1} = R^{-1}\circ R = R$$ Subsequently, $R \circ R = R^{-1} \circ R = R$ and it follows that $R$ is both symmetric ($R= R^{-1}$) and transitive ($R \circ R \subseteq R$).

$\endgroup$

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.