The Axiom of Choice (AC) asserts that for all sets of nonempty sets, there is a choice function such that for all , .
Zorn’s lemma says that for every partially ordered set such that every chain in has an upper bound in , there is a maximal element of .
The primary aim is to prove that the Axiom of Choice implies Zorn’s Lemma. For this we use the notion of wellordered sets, which are just linearly ordered sets such that every nonempty subset of has a least element.
To gain some intuition about the proof, let us instead try to define a wellordering of a given set, assuming the Axiom of Choice. For a given set , consider a choice function for the set of all nonempty subsets of . Then one could try to define a wellordering of as follows: pick as the first element, as the second, as the third, and so on. But all the ‘s might not exhaust all of , so one might have to extend this process of building a wellorder by choosing the element following all the ‘s to be . Then we continue with , and so on. But even this might not exhaust all of and we have to “jump to another limit point” and so on, to form the desired wellorder by a transfinite procedure. But we do not wish to build the machinery (ordinals) necessary to describe such a procedure. And indeed we do not need to, since the problem we are after is slightly different—that of proving Zorn’s Lemma assuming the Axiom of Choice!
Let us keep the above procedure in mind in trying to prove Zorn’s lemma. We are given a partially ordered set each of whose chains has an upper bound. And we suppose, towards a contradiction, that there is no maximal element, and use this to show that there is indeed a chain of with no upper bound in . The chain will be built essentially following the intuition in the above paragraph.
To begin with, notice that every chain in has some upper bound (, say). Now is not a maximal element of , and hence there is some such that . It follows that for every . The Axiom of Choice allows us to pick one such — , say — for each chain .
Now we can try to build our desired chain as follows: let (this is the same as !), , , and so on. The ‘s form a chain , but there is an element that is strictly greater than all the ‘s. So we add to the end of to get a larger chain. We can repeat this procedure “forever” (even taking into account “jumps to the next limit point”) to get a chain without an upper bound. This is the idea, but let’s do it a little more formally.
Notice that any chain is an initial segment of this chain that we are hoping to build if and only if is well-ordered by and it has the following property:
Consider the collection of all chains that are well-ordered by and that satisfy condition (1). (Intuitively, is just the collection of initial segments of “our big chain”, but we will have to get at it in a slightly roundabout manner.)
Proposition 1 For distinct , in , either is an initial segment of or is an initial segment of .
Proof: Let us first prove that either or . Suppose neither holds. Then consider the least in , and the least . Thus and . Notice that and . Now, since is a total order, either is greater than every element of , or it is less than or equal to some element of and thus less than .
Suppose the former. We claim that is an initial segment of , for if not, there exist in such that and . But this is a contradiction, since and was supposed to be the least element of not in , so after all! But now we have , and has an element greater than everything in , and thus the least such, , belongs to , a contradiction!
Suppose . Then by arguing just as above, we can show that belongs to , a contradiction!
Thus either or . Suppose, without loss of generality, that . Since and are distinct, there exists a least that is not in . We claim that is an initial segment of . Suppose not. Then there is a least such that and . But this means that for all , if and only if . But then , a contradiction. Thus is an initial segment of .
Proposition 2 If is an element of , is also an element of .
Proof: Of course will be the largest element in , and it is easy to see that is a well-ordering of this set, and that (1) is satisfied by .
Proposition 3 is an element of .
Proof: Let such that .
We first show that well-orders . Suppose there is an infinite descending chain in . Let such that , for each . Now it is easy to prove that for all , . It is trivially true for . Suppose and consider . Now if is an initial segment of , it follows that (from , and ). If is an initial segment of then and hence . But and hence is a well-ordering of it, so there cannot be an infinite descending sequence in , and the same holds for .
We now show that every is an initial segment of . Clearly is a subset of . We need to show that for every such that and , . Let be some element of such that . Now either is an initial segment of , in which case (since ), or is an initial segment of , in which case also (since and such that ).
Now suppose that . Let such that . As we have seen many times now, and since satisfies (1), it follows that .
Now we are almost done. We claim that above has to lack an upper bound in , contrary to the assumption that every chain has an upper bound. Because if did have an upper bound, then would be an element greater than everything in . But then would be a chain in . But this leads to an immediate contradiction, because this means that , but was supposed to be greater than every element of !
The upshot of all this is that for every partially ordered set , if every chain has an upper bound in , then has a maximal element. Thus the Axiom of Choice implies Zorn’s Lemma.
Update: Many thanks to Shreevatsa, as usual, for pointing out a bug in Proposition 1, which has now hopefully been fixed!