Question

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

Short answer

Hence, it is proved that a finite poset can be reconstructed from its covering relation.

Step-by-step solution

Given data

Suppose that \((S, \le )\) is a poset, with relation \(R\) on the set \(S\).

Concept used of covering relations

Let\((S, \le )\)be a poset. We say that an element\(y \in S\)covers an element\(x \in S\)if\(x < y\)and there is no element\(z \in S\)such that\(x < z < y\). The set of pairs\((x,y)\)such that\(y\)covers\(x\)is called the covering relation of\((S, \le )\).

Prove that a finite poset can be reconstructed from its covering relation

The reflexive transitive closure of \({\rm{R}}\) is the smallest relation \(P\) on \(S\), such that \(P \subseteq S\) and that \({\rm{P}}\) is reflexive and transitive.

If \((a,b)\) is in \(P\) then, either \(a = b\) or \(a < b \Rightarrow a \le b\), by transitivity of \( \le \)

Alternatively if \(a \le b\), then if \(a = b\) then \((a,b)\), is very much in the set \({\rm{P}}\), \(a < b\) and for no element \(x\), we have \(a < x < b\), then \((a,b)\) is in covering relation and thus is in \(P\)

Lastly if \((a,b)\), is such that \(a < {x_1} < {x_2} < \ldots < {x_n} < b\) then since \(P\) is finite there must be a string of longest length, and whose length cannot be increased since that would increase the size of the set, so for that string, all the intermediate elements pair will also be in the covering relation and thus in \(P\).

Hence, a finite poset can be reconstructed from its covering relation.