Extend an acyclic relation to an ordering I am pre-studying a course (Discrete Mathematics) that I will be taking come fall quarter this October. We are using the textbook Invitation to Discrete Mathematics and I am having trouble starting to write proofs.
Q: Let $R$ be a relation on a set $X$ such that there is no finite sequence of elements $x_1, x_2, ..., x_k$ of $X$ satisfying $x_1 R x_2, x_2 R x_3, ..., x_{k-1} R x_k, x_k R x_1$ (we say that such an $R$ is acyclic). Prove that there exists an ordering on $X$ such such that $R$ is contained in the ordering.
Any help would be greatly appreciated.
Thanks.
 A: I suppose that with ordering they mean partial ordering.  Which means
that the relation $S \supseteq R$ you're supposed to find has to be
reflexive on $X$, antisymmetric and transitive.
First, because of the condition mentioned in the exercise (with $k=2$)
we won't be able to find elements $x_1$, $x_2$ with $x_1Rx_2$ and
$x_2Rx_1$.  This means that $R$ is already antisymmetric.  But we'll
likely have to extend $R$, so in the next steps we'll have to check
that we don't destroy antisymmetry by accident.
Let's first tackle transitivity.  For that, we define $S_1$ to be the
transitive closure of $R$.  This will ensure that $S_1$ is transitive
and a superset of $R$.  But we have to check whether $S_1$ is still
antisymmetric.  So, let $x_1$ and $x_2$ be elements of $X$ with
$x_1S_1x_2$ and $x_2S_1x_1$.  By definition of the transitive closure
we'll find $y_1,\dots,y_m$ and $z_1,\dots,z_n$ with
$$x_1=y_1Ry_2Ry_3\dots y_{m-1}Ry_m=x_2 \text{ and }
x_2=z_1Rz_2Rz_3\dots z_{n-1}Rz_n=x_1.$$ But then $(y_1,y_2,y_3,\dots
y_{m-1},z_1,z_2,z_3\dots z_{n-1},z_n)$ would be a sequence that
according to the exercise doesn't exist, so we can't find such $x_1$
and $x_2$ to begin with.
What remains is reflexivity.  This merely says that
$\operatorname{id}_X$ (or $\bigtriangleup_X$ or whatever you call it)
needs to be a subset of $S$.  So, let's set $S = S_1 \cup
\operatorname{id}_X$.  $S$ now surely is reflexive on $X$.  It should
also be clear that $S$ is still transitive.  (If not, please try to
write the reasons down explicitly.)  Is $S$ still antisymmetric?
Let's suppose we have $x_1$ and $x_2$ in $X$ with $x_1Sx_2$ and
$x_2Sx_1$.  Then (see above) it can't be that $x_1S_1x_2$ and
$x_2S_1x_1$, so either $x_1=x_2$ or $x_2=x_1$ or both - which means
we're done.
So, $S$ is an ordering with $S \supseteq R$.
