8
$\begingroup$

Let $(S, \leq)$ be a partial order. Let $T$ be the set of antichains of $S$ (i.e., subsets of $S$ whose elements are pairwise incomparable). Define a relation $\leq'$ on $T$ as follows: for all $A$, $B \in T$, $A \leq' B$ iff $\forall x \in A, \exists y \in B, x \leq y$.

It seems to me that $\leq'$ is also a partial order (it is reflexive, transitive and antisymmetric), and I feel this construction is natural enough to be standard, but I can't find a name for it. How is this construction called? Are there other ways to extend a partial order on a set to a partial order on antichains?

Bonus question: Does $\leq'$ share some of $\leq$'s properties? For instance, if $\leq$ is a well-quasi-ordering, is $\leq'$ also a well-quasi-ordering?

  • 0
    WimC: A more detailed paper abo$u$t the same thing by the same a$u$thors: http://isg.rh$u$l.ac.uk/~jason/Pubs/imj.pdf2013-01-01

2 Answers 2

2

For finite posts at least, there is a one to one correspondence between antichains and lower sets (an antichain $A$ defines the lower sets of elements $x$ such that $\exists y \in A,\,x \leq y$, and conversely the set of maximal elements of a lower set is an antichain). The order relation I have just given is the image of the inclusion order on lower sets under this correspondence: $A \leq' B$ iff $\overline{A} \subseteq \overline{B}$ for $\overline{A}$ and $\overline{B}$ the lower sets associated to $A$ and $B$.

The order induced by the inclusion order of the lower sets of a poset is well-known: is is a distributive lattice, and Birkhoff's representation theorem states that the mapping from posets to the distributive lattice of the inclusion order on its lower set is one-to-one. To wrap it up, the order relation I described in my question is isomorphic to the distributive lattice associated to $(S, \leq)$ by Birkhoff's representation theorem.

0

It is not true, in general, that there is a 1-to-1 correspondence between antichains and lower sets. It is true if the poset satisfies the ascending chain condition.

Here's a counterexample. Take as the poset the unit interval with the usual order: $([0,1], \leq)$. Consider the set $S = [0, 1)$. Then $S$ is a lower set, because for any $x\in S$, any $y\leq x$ is in S. However, $S$ has no maximal elements.

  • 0
    Thanks for this remark! In my answer I was implicitly thinking about *finite* posets, even though the question was more general. I rephrased accordingly.2015-09-28