Author |
Topic: The classification of posets (Read 597 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
The classification of posets
« on: Aug 10th, 2006, 5:45pm » |
 Quote  Modify
|
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 2S.
(Suggested by the recent discussion Dr. Dagg and I had about topologies and posets.)
|
| « Last Edit: Aug 10th, 2006, 5:46pm by Icarus » |
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: The classification of posets
« Reply #1 on: Aug 11th, 2006, 3:36pm » |
Quote Modify
|
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 (T2 = I, and if x < y, then Tx > Ty).
Can you always find a set S and an order-preserving injection f: X --> 2S 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".]
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The classification of posets
« Reply #2 on: Aug 18th, 2006, 9:30pm » |
Quote Modify
|
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 hab : 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 hab(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.
|
| « Last Edit: Aug 18th, 2006, 9:34pm by Eigenray » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: The classification of posets
« Reply #3 on: Aug 19th, 2006, 12:47pm » |
Quote Modify
|
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 = 2X. 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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: The classification of posets
« Reply #4 on: Nov 1st, 2006, 7:39pm » |
Quote Modify
|
What happened to all those pretty posets we were thinking of?
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print