Gmail Calendar Documents Reader Web more »
Recently Visited Groups | Help | Sign in
Google Groups Home
Message from discussion Need help with proof of Zorn Lemma
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Arturo Magidin  
View profile  
 More options Nov 1 2009, 8:02 pm
Newsgroups: sci.math
From: Arturo Magidin <magi...@member.ams.org>
Date: Sun, 1 Nov 2009 12:02:13 -0800 (PST)
Local: Sun, Nov 1 2009 8:02 pm
Subject: Re: Need help with proof of Zorn Lemma
On Nov 1, 1:44 pm, agapito6...@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


    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2010 Google