3
$\begingroup$

Give an example to show that when the symmetric closure of the reflexive closure of the transitive closure of a relation is formed, the result is not necessarily an equivalence relation.

My attempt at a solution:

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

Transitive closure: $\{(2,1),(2,3)\}$.

Reflexive closure: $\{(1,1),(2,1),(2,2),(2,3),(3,3)\}$.

Symmetric closure: $\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)\}$.

Since the set is missing $(1,3)$ and $(3,1)$ to be transitive, it is not an equivalence relation.

I am not sure if this is correct.

$\endgroup$
  • 1
    $\begingroup$ It is indeed correct. $\endgroup$ – Brian M. Scott Nov 30 '15 at 8:11
  • $\begingroup$ Could you please clarify why R is already transitive at the beginning? $\endgroup$ – Philippe Nov 30 '15 at 23:40
  • $\begingroup$ Transitivity says that if there are elements $a,b,c$ (any of which can be equal) such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$. This condition is vacuous – says nothing – if there are no elements $a,b$, and $c$ such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$. That’s the case here: the hypothesis of the if-then is never satisfied, so the then part is never invoked. To put it differently, if $R$ were not transitive, there would have to be $a,b$, and $c$ such that $\langle a,b\rangle\in R$ and ... $\endgroup$ – Brian M. Scott Dec 1 '15 at 4:21
  • $\begingroup$ ... $\langle b,c\rangle\in R$, but $\langle a,c\rangle\notin R$. And there certainly aren’t, since there aren’t even $a,b$, and $c$ such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$. $\endgroup$ – Brian M. Scott Dec 1 '15 at 4:22
  • $\begingroup$ Very clear explanation. Thank you very much! $\endgroup$ – Philippe Dec 2 '15 at 4:32

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.