Reflexive Transitive Closure

Question

The problem I am working on is, "Show that a finite poset can be reconstructed from its covering relation. [Hint:Show that the poset is the reflexive transitive closure of its covering relation.]"

I have been searching through my textbook, and on the internet, for the definition of reflexive transitive closure, but I was not successful.

Could someone please explain this concept to me?

Answer 1

Suppose that $R$ is a relation on a set $A$. The reflexive transitive closure of $R$ is the smallest relation $S$ on $A$ such that

1. $R\subseteq S$;
2. $S$ is reflexive; and
3. $S$ is transitive.

If $R$ is already reflexive and transitive, then $R$ is its own reflexive transitive closure, but that’s not the case with your covering relations.

One way of constructing the reflexive transitive closure of $R$ is to begin by expanding $R$ to $$R_r=R\cup\{\langle a,a\rangle:a\in A\}\;,$$ adding to $R$ all of the pairs $\langle a,a\rangle$ that aren’t already in it. Then whenever you have $\langle x,y\rangle$ and $\langle y,z\rangle$ in $R_r$, you throw in $\langle x,z\rangle$ if it’s not already there to get $R_r^2$. Repeat to get $R_r^3$. If $A$ is finite, after a finite number of steps nothing new will be added; the resulting relation $R_r^*$ is the reflexive transitive closure of $R$.

Answer 2

Recall that a relation $E \subseteq A\times A$ is reflexive if for all $a \in A$ we have $aEa$.

Recall that a relation $E \subseteq A\times A$ is transitive if for all $a,b,c \in A$ we have $aEb$ and $bEc$ imply $aEc$.

Let $R \subseteq A\times A$ be any relation.

The reflexive closure $R'$ of $R$ is the smallest reflexive relation containing $R$.

The transitive closure $R'$ of $R$ is the smallest transitive relation containing $R$.

---

For example if we had the following relation $1R2$ and $2R3$ then we do not have $1R3$ or $1R1$ but we have all of this in the reflexive transitive closure.

Answer 3

Suppose that $R$ is a relation on $A$ (namely $R\subseteq A\times A$).

The reflexive transitive closure of $R$ on $A$ is the smallest relation $R'$ such that $R\subseteq R'$ and $R'$ is transitive and reflexive.

To see that such relation exists you can either construct it internally or externally:

1. Internally takes $R_0=R\cup\{(a,a)\mid a\in A\}$; and $R_{n+1}=R_n \circ R$, where $\circ$ denotes composition of relation [1]. Then we define $R'=\bigcup_{n\in\mathbb N} R_n$. One can then show that this is a reflexive and transitive relation, and that if $S$ is reflexive and transitive and $R\subseteq S$ then $R'\subseteq S$.

2. Externally one can simply take $R'=\bigcap S$ where $S$ is a reflexive and transitive relation on $A$, and $R\subseteq R$. It is not hard to see that the intersection of reflexive relations is reflexive, and similarly for transitivity. It follows that $R'$ has the minimality properties wanted.

[1]: $R \circ S = \{(x,z) \in X \times Z \mid \exists y. (x,y) \in R \land (y,z) \in S \}$