PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] equivalence of Zorn's lemma and the axiom of choice (Proof)

Let $ X$ be a set partially ordered by $ <$ such that each chain has an upper bound. Define $ p(x)=\{y\in X\mid x< y\}\in P(X)$. Let $ p(X)=\{p(x)\mid x\in X\}$. If $ p(x)=\emptyset$ then it follows that $ x$ is maximal.

Suppose no $ p(x)=\emptyset$. Then by the axiom of choice there is a choice function $ f$ on $ p(X)$, and since for each $ p(x)$ we have $ f(p(x))\in p(x)$, it follows that $ x<f(p(x))$. Define $ f_\alpha(p(x))$ for all ordinals $ \alpha$ by transfinite induction:

$ f_0(p(x))=x$

$ f_{\alpha+1}(p(x))=f(p(f_\alpha(p(x))))$

And for a limit ordinal $ \alpha$, let $ f_\alpha(p(x))$ be an upper bound of $ f_i(p(x))$ for $ i<\alpha$.

This construction can go on forever, for any ordinal. Then we can easily construct an injective function from $ Ord$ to $ X$ by $ g(\alpha)=f_\alpha(p(x))$ for an arbitrary $ x\in X$. This must be injective, since $ \alpha<\beta$ implies $ g(\alpha)<g(\beta)$. But that requires that $ X$ be a proper class, in contradiction to the fact that it is a set. So there can be no such choice function, and there must be a maximal element of $ X$.

For the reverse, assume Zorn's lemma and let $ C$ be any set of non-empty sets. Consider the set of functions $ F=\{f\mid \forall a\in\operatorname{dom}(f) (a\in C \wedge f(a)\in a)\}$ partially ordered by inclusion. Then the union of any chain in $ F$ is also a member of $ F$ (since the union of a chain of functions is always a function). By Zorn's lemma, $ F$ has a maximal element $ f$, and since any function with domain smaller than $ C$ can be easily expanded, $ \operatorname{dom}(f)=C$, and so $ f$ is a choice function for $ C$.



"equivalence of Zorn's lemma and the axiom of choice" is owned by Henry.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: expanded, domain, union, inclusion, functions, Zorn's lemma, maximal element, contradiction, proper class, implies, injective, injective function, limit ordinal, transfinite induction, ordinals, choice function, upper bound, chain
There are 2 references to this entry.

This is version 7 of equivalence of Zorn's lemma and the axiom of choice, born on 2002-08-25, modified 2005-11-27.
Object id is 3358, canonical name is ProofOfZornsLemma.
Accessed 5665 times total.

Classification:
AMS MSC: 03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)
Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy
Elegant proof by ratboy on 2005-02-23 23:45:24
Thomas Forster, in a note preceding his fiddly proof of Zorn from AC, remarks "deducing Zorn from AC was a well-known fiddly task and in some ways remains so." Believing him, I didn't trouble to look beyond the obvious errors in the previous versions of this proof, so I was pleasantly surprised when a short, easy proof finally emerged.

There are some stylistic changes that I would make, but these are merely a matter of taste. A handy set-theoretic notation is f"Y ($f``Y$) for the image {f(y)|y in Y} of Y under the function f. There are actually two choice functions in play. First, there is your f on p"X. Define U:P(X)->P(X) by U(x)={y|y is an upper bound for x}; if C is the set of chains in X, then there is a choice function h on U"C. Let x be any member of X and define g:Ord->X by transfinite recursion:

g(0) = x,
g(a+1) = f(p(g(a))),
and
g(a) = h(U(g"a)) if a is a limit ordinal.

Then g is strictly increasing, etc.

If this proof originated with you, congratulations.

Forster's remark is on page 61 of _Logic, Induction and Sets_, Cambridge University Press, 2003.
[ reply | up ]
Interact
post | correct | update request | add example | add (any)