# Extending a partial order to antichains

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?

• This ordering (and one closely related) is known. See my post about game trees 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. – WimC Dec 9 '12 at 11:34
• See here for example. – WimC Dec 9 '12 at 11:37
• @Wim: This is thoroughly off-topic, but that is a wonderfully appropriate picture on your Math Blog! – Brian M. Scott Dec 9 '12 at 12:27
• WimC: A more detailed paper about the same thing by the same authors: isg.rhul.ac.uk/~jason/Pubs/imj.pdf – a3nm Jan 1 '13 at 12:36

## 2 Answers

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.

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.

• Thanks for this remark! In my answer I was implicitly thinking about finite posets, even though the question was more general. I rephrased accordingly. – a3nm Sep 28 '15 at 10:54