# Are any two pairs in a cyclic path of a transitive relation symmetric?

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?

• 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. – Sean English Jan 18 '16 at 16:08
• 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. – Eric '3ToedSloth' Jan 18 '16 at 16:38

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.