Use a reflexive and transitive closure to transform an antisymmetric and acyclic relation into a partially ordered set.

Question

The relation $R=\{(x,S_1),(S_1,S_2),(S_2,S_3),(S_3,S_4),(S_4,y)\}$ is antisymmetric and acyclic but not transitive or reflexive. We know that any antisymmetric and acyclic relation can be turned into a partial ordering through the usage of the transitive and reflexive closure. To make $R$ transitive we can utilize the concept the transitive cover: $$R^+=R \cup \{(x,y) : \exists k \in \mathbb{N}, S_1,...,S_k \in S, s.t. (x_1,S_1),..., (x_k,S_k) \in R\}$$

Essentially, we have to introduce all transitive pairs into $R$ thereby making $R$ transitive. After doing that we have: $$R=\{(x,S_1), ,(x,S_2),(x,S_3),(x,S_4),(x,y),\\(S_1,S_2),(S_1,S_3), (S_1,S_4), (S_1,y), \\(S_2,S_3), (S_2,S_4), (S_2,y)\\(S_3,S_4), (S_3,y), \\(S_4,y)\}$$

I can't introduce any more pairs without the relationship becoming symmetric. To make the relation reflexive, I use the idea of the reflexive closure and introduce $(x,x),(S_1,S_1),(S_2,S_2),(S_3,S_3),(S_4,S_4),(y,y)$ into $R$.

In the end I have:

$$R=\{(x,x),(x,S_1), ,(x,S_2),(x,S_3),(x,S_4),(x,y),\\(S_1,S_1),(S_1,S_2),(S_1,S_3), (S_1,S_4), (S_1,y), \\(S_2,S_2), (S_2,S_3), (S_2,S_4), (S_2,y)\\(S_3,S_3)(S_3,S_4), (S_3,y), \\(S_4,S_4)(S_4,y) \\ (y,y)\}$$

This relation is reflexive, antisymmetric and transitive thus is a partially ordered set. Is this working out correct, or have I missed something?

Answer 1

Yes, what you did is correct.

By the way, your formal definition of transitive closure (and not cover) of a binary relation $R$ over a set $S$ is wrong. The correct one is the following: \begin{align} \begin{split} R^+ = \{(x,y) \in S \times S \mid \exists k \in \mathbb{N}^+\!, \ \exists \, s_0, \dots, s_k \in S : x = s_0, \ y = s_k, \ \\ (s_i, s_{i+1}) \in R \ \ \forall \, 0 \leq i < k \} \end{split} \end{align} Note that, according this definition, $R \subseteq R^+$ (take $k = 1$).