wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> The classification of posets
        
(Message started by: Icarus on Aug 10^th, 2006, 5:45pm)

Title: The classification of posets
Post by Icarus on Aug 10^th, 2006, 5:45pm

Show that every partially ordered set is isomorphic to a collection of sets ordered by subset.

I.e., given a poset (X, <), find a set S and an order-preserving injection from X into 2^S.

(Suggested by the recent discussion Dr. Dagg and I had about topologies and posets.)

Title: Re: The classification of posets
Post by Icarus on Aug 11^th, 2006, 3:36pm

Michael_Dagg has pointed out to me that is far more trivial than I was thinking when I posted it. So let me give the other part I was holding back on, in hopes that it will make the problem at least a little bit interesting:

Suppose that in addition to your poset (X, <), you are given a decreasing involution T: X --> X (T² = I, and if x < y, then Tx > Ty).

Can you always find a set S and an order-preserving injection f: X --> 2^S such that f(Tx) = S - f(x). And if not, what additional conditions on Tare sufficient?

[Thanks, Eigenray, for reminding me of the term "involution".]

Title: Re: The classification of posets
Post by Eigenray on Aug 18^th, 2006, 9:30pm

To answer your first question: f(x) = {y : y<x }.

For the second, such an f need not exist. Clearly it is necessary that
(*) Tx be incomparable to x, unless x is the greatest or least element (if it exists).

For example, if X = {0,1,2,...,n}, and T(x) = n-x, there is no such f unless n=0 or 1.

The surprising result is that (*) is also sufficient. For a while I tried to find an example proving it wasn't, and I realized that in constructing f I was adding points to S to separate points of X, making f injective.

For each pair a != b, we construct h_ab : X -> {0,1} satisfying

(1) y<z implies h(y)<h(z)
(2) h(a) != h(b)
(3) h(y)=0 iff h(Ty)=1.

Then f(x) will be the set of pairs (a,b) such that h_ab(x)=1. This is <-preserving by (1), injective by (2), and intertwines T and complement by (3).

If a<b, set h(a)=h(Tb)=0, h(b)=h(Ta)=1; else h(a)=h(Tb)=1, h(b)=h(Ta)=0.

In the first case, we can't have b<a, and if b<Tb, then (*) implies b is the least element, which is false. The other cases are similar, so h satisfies (1) for y,z in {a,b,Ta,Tb}. Now the result will follow from Zorning the following:

Lemma: if Y=T(Y) is a subset of X, and h : Y -> {0,1} satisfies (1),(3) for all y,z in Y, then h may be extended to Y u {x, Tx} for any x in X\Y.

Pick x in X\Y. If y<x<z, and y,z in Y, then h(y) < h(z). Consequently, we may pick h(x) such that
h(y) < h(x) < h(z) if y<x<z, y,z in Y, and h(Tx) := 1-h(x).
To verify (1), first note that if y<Tx<z, with y,z in Y, then Tz<x<Ty, so h(Tz)<h(x)<h(Ty), which by (3) gives h(y)<h(Tx)<h(z). Finally, if x is the least/greatest element, then by (2), h(x) will be 0/1; by (*) this completes the proof.

Title: Re: The classification of posets
Post by Icarus on Aug 19^th, 2006, 12:47pm

Well done!

I never worked this out myself, which is why I hadn't included it in the original post. I wanted to think about it more before I posted it. But for reasons that now escape me, I thought at the time that f(x) = {y : y < x} wouldn't work. Instead my solution involved S = 2^X. But when Michael pointed out my mistake in a private message, I decided to go ahead and put the T question on, even if I never finished it.

I'm glad it at least provided some challenge.

Title: Re: The classification of posets
Post by Michael_Dagg on Nov 1^st, 2006, 7:39pm

What happened to all those pretty posets we were thinking of?