0
$\begingroup$

Suppose $R$ is a transitive binary relation that contains a cycle $a_1Ra_2$, $a_2Ra_3$, $\dots$, $a_{n-1}Ra_n$, $a_nRa_1$. Does this imply that $R$ is symmetric for any pairs in this cycle, i.e. $a_iRa_j\Rightarrow a_jRa_i$ for all $a_i, a_j\in \{a_1, \dots, a_n\}$?

If so, how do I prove it?

$\endgroup$
  • $\begingroup$ Try proving it when you have a cycle of length, say five. Once you do that, it should be clear how to go about it in a general setting. Note, If you want to be perfectly precise, I think you will have to use an induction here to deal with the "..." In the statement. $\endgroup$ – Sean English Jan 18 '16 at 16:08
  • $\begingroup$ Yes, it's the induction I'm struggling with. It's clear that I get $a_iRa_{i+2}$ from $a_iRa_{i+1}$, $a_{i+1}Ra_{a+2}$ and that two such shortcuts can be divided again, until I get from $a_i$ to any $a_j$ but there seems to be a difference between even and odd $n$ and anyway I don't know how to write this down properly. This is not homework, btw, I was just wondering. $\endgroup$ – Eric '3ToedSloth' Jan 18 '16 at 16:38
1
$\begingroup$

Let us consider induction on $n$ of a slightly stronger statement. If $R$ is a transitive binary relation that contains a cycle of length $n$, then $xRy$ for any $x$ and $y$ in the cycle. In this case we will say $R$ is full with respect to the cycle.

Base case $n=1$ and $n=2$ are trivial.

Inductive step. Assume that whenever there is a cycle of length $n\geq 2$ then the relation is full with respect to the cycle.. Now let $(a_1Ra_2, a_2Ra_3, ..., a_nRa_{n+1}, a_{n+1}Ra_1)$ be a cycle of length $n+1\geq 3$ and let $a_i$ and $a_j$ be any two elements of the cycle. Since $n+1\geq 3$ we may assume WLOG that $2\neq i$ and $2\neq j$. Then since the relation is transitive $a_1Ra_2$ and $a_2Ra_3$ implies $a_1Ra_3$ so we have a cycle $( a_1Ra_3, ..., a_nRa_{n+1},a_{n+1}Ra_1)$ of length $n$ that contains $a_i$ and $a_j$. Thus $a_iRa_j$.

Thus by induction we have that If $R$ is a transitive binary relation that contains a cycle, then $R$ is full with respect to the cycle.

Then symmetry follows trivially from that.

$\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.