A cycle in a relation R is a sequence of k distinct elements a_0, a_1, ..., a_(k-1) of A where (a_i, a_((i+1) mod k)) ∈ R for each i ∈ {0, 1, ..., k-1}. A cycle is nontrivial if k ≥ 2. Prove that there are no nontrivial cycles in any transitive, antisymmetric relation R.
I understand that a cycle in graph theory is a path of length >= 2 from vertex u, back to vertex u that doesn't traverse the same edge twice. What I don't understand is how can I represent a cycle as a set of relations, and then prove that it holds the following properties? Thanks for your help.
I will prove by contrapositive and say that if R is transitive and has a non-trivial cycle, then R is not anti-symmetric.
To do this I will show that if (a_i, a_i+1) ∈ R for i = 0, 1, ..., k-2; then (a_0, a_k-1) ∈ R using induction on i.
Let i = j for some j ∈ Natural Numbers. The base case will be j=0 and thus we have,
(a_0, a_0) = (a_0, a_(0 (mod 1))) == (a_0, a_0)
Our inductions hypothesis will be to assume that (a_k-1, a_0) ∈ R. Next we will assume that (a_0, a_j) is in the relation R, for some j ∈ {1,2,...,k-2} Thus,
(a_0, a_j+1) == (a_0, a_k-1)
Therefore, since (a_0, a_k-1) ∈ R, and (a_k-1, a_0) ∈ R by the I.H.; and since every node is different, a_0 =/= a_k-1, hence R cannot be anti-symmetric, hence proved.
Q.E.D.
It’s not a matter of representing a cycle as a set of relations: you’re dealing with only one relation. For example, consider a tiny round-robin tennis tournament in which $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$. Then the relation $x\,r\,y$ iff $x$ beats $y$ in this tournament has a non-trivial cycle $A,B,C$: $A\,r\,B$, $B\,r\,C$, and $C\,r\,A$.
You’re asked to show that if a relation $R$ is transitive and antisymmetric, then it cannot have a non-trivial cycle. In other words, there cannot be elements $a_0,\ldots,a_{k-1}$ in the underlying set such that $k\ge 1$, $\langle a_i,a_{i+1}\rangle\in R$ for $i=0,\ldots,k-2$, and $\langle a_{k-1},a_0\rangle\in R$.
HINT: Show that if $\langle a_i,a_{i+1}\rangle\in R$ for $i=0,\ldots,k-2$, then $\langle a_0,a_{k-1}\rangle\in R$. I’ve added a further hint in the spoiler-protected block below; mouse over it to see it.
Added: We’ll assume that $R$ is transitive and has a cycle $a_0,a_1,\ldots,a_{k-1}$ of length $k\ge 2$ and prove that $R$ cannot then be antisymmetric. From this it follows at once that a transitive, antisymmetric relation cannot have a non-trivial cycle.
We’ll begin by proving by induction on $i$ that $\langle a_0,a_{i+1}\rangle\in R$ for $i=1,2,\ldots,k-2$. To get the induction started, we know that this is true for $i=1$: $\langle a_0,a_1\rangle\in R$ by hypothesis. For the induction step we need to prove that if $\langle a_0,a_i\rangle\in R$ for some $i<k-2$, then $\langle a_0,a_{i+1}\rangle\in R$. Since $i<k-2$, we know by hypothesis that $\langle a_i,a_{i+1}\rangle\in R$, and the induction hypothesis tells us that $\langle a_0,a_i\rangle\in R$. We also know that $R$ is transitive, so $\langle a_0,a_{i+1}\rangle\in R$, which is exactly what we wanted. By induction, therefore, we can conclude that $\langle a_0,a_i\rangle\in R$ for $i=1,2,\ldots,a_{k-1}$, and in particular that $\langle a_0,a_{k-1}\rangle\in R$.
That concludes the induction part of the proof, and we now use that result. We have $\langle a_0,a_{k-1}\rangle\in R$ from the induction argument, and we know by hypothesis that $\langle a_{k-1},a_0\rangle\in R$. And by hypothesis $k\ge 2$, so $a_0\ne a_{k-1}$, so $R$ is not antisymmetric. This concludes the proof.