 |
|
| Science Forum Index » Mathematics Forum » Need help with proof of Zorn Lemma... |
|
Page 1 of 1 |
|
| Author |
Message |
| ... |
 Posted: Sun Nov 01, 2009 9:44 am |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
|
|
| Arturo Magidin... |
| Posted: Sun Nov 01, 2009 10:02 am |
|
|
|
Guest
|
On Nov 1, 1:44 pm, agapito6... at (no spam) aol.com wrote:
[quote]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.
[/quote]
[quote]Can someone please help explain:
1.- How is this procedure equivalent to proving the existence of a
maximal element in X?
[/quote]
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.
[quote]2.- How or where is the original hypothesis invoked?
[/quote]
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.
[quote]In the proof, the only basic principle invoked is the Axiom of
Choice. Any help appreciated.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| ... |
| Posted: Sun Nov 01, 2009 12:01 pm |
|
|
|
Guest
|
On Nov 1, 2:02 pm, Arturo Magidin <magi... at (no spam) member.ams.org> wrote:
[quote]On Nov 1, 1:44 pm, agapito6... at (no spam) aol.com wrote:
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
[/quote]
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. |
|
|
| Back to top |
|
|
|
| Jim Heckman... |
| Posted: Tue Nov 03, 2009 5:28 am |
|
|
|
Guest
|
On 1-Nov-2009, agapito6314 at (no spam) aol.com
wrote in message
<269a34a3-3630-4094-aa9a-a1701107f409 at (no spam) t2g2000yqn.googlegroups.com>:
[quote]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?
[/quote]
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.
[quote]In the proof, the only basic principle invoked is the Axiom of
Choice. Any help appreciated.
[/quote]
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.)
--
Jim Heckman |
|
|
| Back to top |
|
|
|
| ... |
| Posted: Tue Nov 03, 2009 10:13 am |
|
|
|
Guest
|
On Nov 3, 4:28 am, "Jim Heckman" <rot13(reply-to) at (no spam) none.invalid> wrote:
[quote]On 1-Nov-2009, agapito6... at (no spam) aol.com
wrote in message
269a34a3-3630-4094-aa9a-a1701107f... at (no spam) 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.
[/quote]
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. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 11, 2009 10:25 am
|
|