Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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