1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\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.