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?

  • 1
    This ordering (and one closely related) is known. See my post about [game trees](http://wimcouwenberg.wordpress.com/2011/05/08/game-trees-under-a-partial-order-part-1/) and look for the definition of minimizing and maximizing order. I also encountered these orderings elsewhere but I'll have to search for a reference. Not sure if there's a name for them.2012-12-09
  • 0
    See [here](http://www.dcs.bbk.ac.uk/research/techreps/2000/bbkcs-00-09.pdf) for example.2012-12-09
  • 0
    @Wim: This is thoroughly off-topic, but that is a wonderfully appropriate picture on your Math Blog!2012-12-09
  • 0
    WimC: A more detailed paper about the same thing by the same authors: http://isg.rhul.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