equivalence of Zorn’s lemma and the axiom of choice

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

Suppose no p(x)=. Then by the axiom of choiceMathworldPlanetmath (http://planetmath.org/AxiomOfChoice) there is a choice function f on p(X), and since for each p(x) we have f(p(x))p(x), it follows that x<f(p(x)). Define fα(p(x)) for all ordinalsMathworldPlanetmathPlanetmath α by transfinite inductionMathworldPlanetmath:



And for a limit ordinalMathworldPlanetmath α, let fα(p(x)) be an upper bound of fi(p(x)) for i<α.

This construction can go on forever, for any ordinal. Then we can easily construct an injective function from Ord to X by g(α)=fα(p(x)) for an arbitrary xX. This must be injective, since α<β implies g(α)<g(β). But that requires that X be a proper classMathworldPlanetmath, in contradictionMathworldPlanetmathPlanetmath to the fact that it is a set. So there can be no such choice function, and there must be a maximal elementMathworldPlanetmath 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={fadom(f)(aCf(a)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, dom(f)=C, and so f is a choice function for C.

Title equivalence of Zorn’s lemma and the axiom of choice
Canonical name EquivalenceOfZornsLemmaAndTheAxiomOfChoice
Date of creation 2013-03-22 12:59:04
Last modified on 2013-03-22 12:59:04
Owner Henry (455)
Last modified by Henry (455)
Numerical id 10
Author Henry (455)
Entry type Proof
Classification msc 03E25