8
$\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?

  • 0
    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?2014-09-04

3 Answers 3

7

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

  • 0
    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?2012-11-17
  • 0
    @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.2012-11-17
  • 0
    @BrianScott Why isn't a covering relation generally transitive; why isn't it ever reflexive?2012-11-17
  • 0
    @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$.2012-11-17
  • 0
    Is it possible for you to provide me with a definition that hints at these things? The definition my book provides doesn't even remotely suggest that a covering relation can't be reflexive--actually, my book does not really have nice succinct definition on this concept.2012-11-17
  • 1
    @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 **and** there is no $z\in A$ such that $x. 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.2012-11-17
2

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.

1

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.

  • 0
    But the reflexive closure implies $2R2, 3R3, \dots$ should also included, not just $1R1$?2018-07-05