PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
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 | get metadata)

View style:


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

Cross-references: expanded, domain, member, 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 7456 times total.

Classification:
AMS MSC03E25 (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)