Let $\rho$ be an antisymmetric, irreflexive relation, and $\rho ^t$ its transitive closure.
Prove or disprove: $\rho ^t$ is reflexive $\Rightarrow$ $\rho ^t$ is symmetric.
I tried to prove that $\rho ^t$ is symmetric by proving that if $(x,y)\in \rho ^t$, than $(x,y)\in \rho ^t$, but whatever I do, I just can't prove that this is true.
Also, I tried to find an example for where the statement isn't true, but
whenever I try to make a relation that is antisymmetric and irreflexive and I find its transitive closure which is reflexive, I get that $\rho ^t$ is symmetric which makes me think that the statement is correct.
Thanks in advance!
Best Answer
The statement is false. Here is a counterexample : take two disjoint length-three cycles $x_1 \rho x_2 \rho x_3 \rho x_1$ and $y_1 \rho y_2 \rho y_3 \rho y_1$, and add just one more edge $x_1 \rho y_1$.
The resulting $\rho^t$ is reflexive (because every element is in some cycle) but not symmetric (look at what happens on $x_1$ and $y_1$).