# 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.

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