10
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ Is the relation in question 2-ary? That is, is the arity always assumed to be 2? That is, is the question only concerned with binary relations? $\endgroup$ – Jacob Barnard Sep 4 '14 at 13:57
8
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ What do you mean by this, "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." A covering relation isn't transitive or reflexive? $\endgroup$ – Mack Nov 17 '12 at 13:47
  • $\begingroup$ @EMACK: You can form the reflexive transitive closure of any relation, not just covering relations, and I was talking there about the general situation $-$ specifically, about what is meant by reflexive transitive closure. A covering relation can be transitive, but it generally isn’t, and it’s never reflexive, so that comment doesn’t really pertain to this specific problem. It is, however, part of understanding what the reflexive transitive closure of a relation is in general. $\endgroup$ – Brian M. Scott Nov 17 '12 at 13:51
  • $\begingroup$ @BrianScott Why isn't a covering relation generally transitive; why isn't it ever reflexive? $\endgroup$ – Mack Nov 17 '12 at 15:50
  • $\begingroup$ @EMACK: The definition of covering relation rules out reflexivity: covering relations are by definition irreflexive. It also implies that a covering relation can be transitive only vacuously. If $\prec$ is a covering relation, $x\prec y$, and $y\prec z$, then $x\not\prec z$, $y$ is strictly between $x$ and $z$. $\endgroup$ – Brian M. Scott Nov 17 '12 at 21:16
  • 1
    $\begingroup$ @EMACK: Let $\le$ be a partial order on a set $A$. The associated covering relation is the relation $\prec$ defined as follows: for all $x,y\in A$, $x\prec y$ if and only if $x<y$ and there is no $z\in A$ such that $x<z<y$. In other words, $x\prec y$ if and only if $y$ is an immediate successor of $x$ in the order $\le$, with nothing strictly between them. $\endgroup$ – Brian M. Scott Nov 17 '12 at 21:29
2
$\begingroup$

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\{\langle a,a\rangle\mid a\in\ A\}$; and $R_{n+1}=R_n\cup R$. 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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ But the reflexive closure implies $2R2, 3R3, \dots$ should also included, not just $1R1$? $\endgroup$ – linear_combinatori_probabi Jul 5 '18 at 7:17

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.