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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.