It states: If X is a partially ordered set such that every chain in X has an upper bound, then X contains a maximal element. I'm trying to understand Halmos' proof. To summarize, instead of dealing with X, he deals with Y, which is the set of all chains in X, and, after a long series of contortions, proves the existence of a maximal element in Y. Can someone please help explain:
1.- How is this procedure equivalent to proving the existence of a maximal element in X?
2.- How or where is the original hypothesis invoked?
In the proof, the only basic principle invoked is the Axiom of Choice. Any help appreciated.
> It states: If X is a partially ordered set such that every chain in X > has an upper bound, then X contains a maximal element. I'm trying to > understand Halmos' proof. To summarize, instead of dealing with X, he > deals with Y, which is the set of all chains in X, and, after a long > series of contortions, proves the existence of a maximal element in > Y. > Can someone please help explain:
> 1.- How is this procedure equivalent to proving the existence of a > maximal element in X?
To be explicit:
Given x in X, the "weak initial segment of x", ws(x), is
ws(x) = {y in X : y<=x}.
You can consider ws as a function from X to P(X), the power set of X; the power set of X is ordered by inclusion, and we have that ws(x) is contained in ws(y) if and only if x<=y, so ws can be viewed as an order-preserving function between the partially ordered set X and the partially ordered set P(X). Morevoer, the function ws is one-to-one: if ws(x) = ws(y), then since x is in ws(x) and y is in ws(y), it follows that x<=y and y<=x, so x=y.
So, Halmost says: "finding a maximal element in X is the same as finding a maximal element in" the range of ws. Because you have an order isomorphism between X and its image under ws. And since X satisfies that every chain in X has an upper bound in X, then every chain in the range of ws has an upper bound in the range of ws.
Now let Y be the set of all chains in X, partially ordered by inclusion. Note that if A is a chain, then A has an upper bound x in X, so therefore, A is contained in ws(x) [here we are using the hypothesis on X]. Thus, every element of Y is dominated by an element of the range of ws.
This means that if y is a maximal element in Y (with respect to the inclusion order of Y), then y has to be a maximal element in ws(x) as well. For if y is contained in ws(x), then y\/{x} would be a chain, hence an element of Y; since it contains the maximal element y of Y, we must have y = y\/{x}, so x lies in y. Thus, y is in fact in the range of ws, and is also maximal in the range of ws. Thus, finding an maximal element in Y gives a maximal element of the range of ws, which in turn gives a maximal element of X.
> 2.- How or where is the original hypothesis invoked?
We invoke the original hypothesis to get that every element of Y is contained in an element of the range of ws; this is used in order to justify that a maximal element of Y must in fact be of the form ws(x) for some x, which you need in order to obtain the corresponding maximal element of X.
> In the proof, the only basic principle invoked is the Axiom of > Choice. Any help appreciated.
As with most proofs in Halmos's book, there is a fair amount unsaid; in this case, it is in the phrase "Since each set in Y is dominated by some set in S, the passage from S to X cannot introduce new maximal elements". The premise invokes the condition on X, the conclusion is the argument above.
> > It states: If X is a partially ordered set such that every chain in X > > has an upper bound, then X contains a maximal element. I'm trying to > > understand Halmos' proof. To summarize, instead of dealing with X, he > > deals with Y, which is the set of all chains in X, and, after a long > > series of contortions, proves the existence of a maximal element in > > Y. > > Can someone please help explain:
> > 1.- How is this procedure equivalent to proving the existence of a > > maximal element in X?
> To be explicit:
> Given x in X, the "weak initial segment of x", ws(x), is
> ws(x) = {y in X : y<=x}.
> You can consider ws as a function from X to P(X), the power set of X; > the power set of X is ordered by inclusion, and we have that ws(x) is > contained in ws(y) if and only if x<=y, so ws can be viewed as an > order-preserving function between the partially ordered set X and the > partially ordered set P(X). Morevoer, the function ws is one-to-one: > if ws(x) = ws(y), then since x is in ws(x) and y is in ws(y), it > follows that x<=y and y<=x, so x=y.
> So, Halmost says: "finding a maximal element in X is the same as > finding a maximal element in" the range of ws. Because you have an > order isomorphism between X and its image under ws. And since X > satisfies that every chain in X has an upper bound in X, then every > chain in the range of ws has an upper bound in the range of ws.
> Now let Y be the set of all chains in X, partially ordered by > inclusion. Note that if A is a chain, then A has an upper bound x in > X, so therefore, A is contained in ws(x) [here we are using the > hypothesis on X]. Thus, every element of Y is dominated by an element > of the range of ws.
> This means that if y is a maximal element in Y (with respect to the > inclusion order of Y), then y has to be a maximal element in ws(x) as > well. For if y is contained in ws(x), then y\/{x} would be a chain, > hence an element of Y; since it contains the maximal element y of Y, > we must have y = y\/{x}, so x lies in y. Thus, y is in fact in the > range of ws, and is also maximal in the range of ws. Thus, finding an > maximal element in Y gives a maximal element of the range of ws, which > in turn gives a maximal element of X.
> > 2.- How or where is the original hypothesis invoked?
> We invoke the original hypothesis to get that every element of Y is > contained in an element of the range of ws; this is used in order to > justify that a maximal element of Y must in fact be of the form ws(x) > for some x, which you need in order to obtain the corresponding > maximal element of X.
> > In the proof, the only basic principle invoked is the Axiom of > > Choice. Any help appreciated.
> As with most proofs in Halmos's book, there is a fair amount unsaid; > in this case, it is in the phrase "Since each set in Y is dominated by > some set in S, the passage from S to X cannot introduce new maximal > elements". The premise invokes the condition on X, the conclusion is > the argument above.
> -- > Arturo Magidin
As always, prof. Magidin, many thanks for your lucid explanation and for taking time to help me. I will now attempt to tackle the converse, that is Zorn Lemma ----> Axiom of choice. Again, thanks for your assistance.
On 1-Nov-2009, agapito6...@aol.com wrote in message <269a34a3-3630-4094-aa9a-a1701107f...@t2g2000yqn.googlegroups.com>:
> It states: If X is a partially ordered set such that every chain in X > has an upper bound, then X contains a maximal element. I'm trying to > understand Halmos' proof. To summarize, instead of dealing with X, he > deals with Y, which is the set of all chains in X, and, after a long > series of contortions, proves the existence of a maximal element in > Y. Can someone please help explain:
> 1.- How is this procedure equivalent to proving the existence of a > maximal element in X?
> 2.- How or where is the original hypothesis invoked?
Forget Halmos' explanation of this. In my opinion, he goes completely off the rails here, hopelessly complicating what's really quite simple:
A maximal element in Y is a maximal chain in X, that is, a chain that's not a proper subset of any chain. (Remember, Y is partially ordered by inclusion.) Let M be such a chain. By the hypothesis of Zorn's Lemma, M has an upper bound u in X, that is, m <= u for all m in M. Then u is a maximal element in X, for otherwise there would be some v in X with u < v, so m <= u < v for all m in M, and M would be a proper subset of the chain M U {v}, contradicting the maximality of M.
> In the proof, the only basic principle invoked is the Axiom of > Choice. Any help appreciated.
Actually, I rather like the proof in general, despite all its contortions. It makes it very clear that you needn't invoke well-ordering per se to prove Zorn's Lemma. (Though of course Halmos' function g:Y -> Y, combined with his requirement that the union of any chain in a "tower" T be an element of T, is equivalent to well-ordering the minimal tower T_0.)
> On 1-Nov-2009, agapito6...@aol.com > wrote in message > <269a34a3-3630-4094-aa9a-a1701107f...@t2g2000yqn.googlegroups.com>:
> > It states: If X is a partially ordered set such that every chain in X > > has an upper bound, then X contains a maximal element. I'm trying to > > understandHalmos' proof. To summarize, instead of dealing with X, he > > deals with Y, which is the set of all chains in X, and, after a long > > series of contortions, proves the existence of a maximal element in > > Y. Can someone please help explain:
> > 1.- How is this procedure equivalent to proving the existence of a > > maximal element in X?
> > 2.- How or where is the original hypothesis invoked?
> ForgetHalmos' explanation of this. In my opinion, he goes > completely off the rails here, hopelessly complicating what's > really quite simple:
> A maximal element in Y is a maximal chain in X, that is, a chain > that's not a proper subset of any chain. (Remember, Y is partially > ordered by inclusion.) Let M be such a chain. By the hypothesis ofZorn'sLemma, M has an upper bound u in X, that is, m <= u for all > m in M. Then u is a maximal element in X, for otherwise there would > be some v in X with u < v, so m <= u < v for all m in M, and M > would be a proper subset of the chain M U {v}, contradicting the > maximality of M.
I agree. However, how do you explain Halmos going "completely off the rails here"? This text has been around for 1/2 a century and I wonder if anyone has pointed this out before, or perhaps you & I are the ones going off the rails here! Many thanks for your response.
|
