Depending on the chosen perspective on foundations this is either an axiom or a consequence of the axiom of choice; or neither if neither the axiom of choice nor Zorn’s lemma is assumed as an axiom. Conversely, Zorn's lemma and the axiom of excluded middle together imply the axiom of choice. Although it doesn't imply excluded middle itself, Zorn's lemma is not generally accepted in constructive mathematics as an axiom.
(Say something about how one can systematically get around this in many situations ….)
In as far as it holds or is assumed to hold, Zorn’s lemma is a standard method for constructing (or at least, proving the existence of) objects that are ‘maximal’ in an appropriate sense. It is commonly used in algebra and named after the algebraist Max Zorn.
The proposition Zorn's Lemma states that each preordered set has a maximal element if every chain in has an upper bound.
Suppose the axiom of choice holds. Then Zorn's Lemma holds.
The proof may be arranged in the following steps:
For each subset of which is well-ordered under the preorder it inherits from , choose a strict upper bound if it has one. (Note that we use the axiom of choice here. We also freely use its consequence, the axiom of excluded middle, below.)
Say a well-ordered subset is -inductive if for all , . Thus is inductive, as is , , and so on. Intuitively, using the chain hypothesis, one can (by transfinite induction) define for ordinals by appending strict upper bounds in this way, until at some point , one has run out of further strict upper bounds to choose from. But by hypothesis, does have an upper bound . This element is necessarily maximal.
More precisely, -inductive sets are well-ordered by inclusion. For if and are distinct (well-ordered and) -inductive sets, then there is a smallest element contained in one but not the other, say but . But then is a down-closed subset of , i.e., is an initial segment of . If it were a proper subset of , then for the least in its complement we would have
whence by applying to both sides, we infer by -inductivity of and , contradiction. In that case, . In other words, one of must be an initial segment of the other.
Therefore the union of all -inductive sets is also -inductive. Being the maximal -inductive set , it contains any of its upper bounds (in fact there is only one up to isomorphism), and this element is necessarily maximal in .
The empty set is not an exception to Zorn's lemma, as the chain does not have an upper bound.
Let be a set, and consider the poset whose elements are pairs , where and is a (classical) well-ordering on , ordered by if as a well-ordered set is an initial segment of . The hypothesis of Zorn’s lemma is easily established: given a chain , put and define the relation on by if for any (hence all) containing both . Then is a well-ordering: if is any nonempty set, then is nonempty for some , and the minimal element of with respect to will also be the minimal element of with respect to (crucially using here the initial segment condition).
By Zorn’s lemma, the poset above contains a maximal element , where . We claim ; suppose not (here is where we need excluded middle), and let be a member of the complement . Well-order , extending by deeming to be the final element. This shows was not maximal, contradiction. Hence any set may be well-ordered.
The axiom of choice follows: suppose given a surjection , so that every fiber is inhabited. Consider any well-ordering of , and define by letting be the least element in with respect to the well-ordering. This gives a section of .
It is very common, when starting with a preordered set , to apply Zorn's lemma not to itself but to an up-set (an under category) in . That is, one starts with an element of and proves the existence of a maximal element comparable to .
Zorn's lemma may be used to prove all of the following:
Some of these are equivalent to Zorn's lemma, while some are weaker; conversely, some additionally require excluded middle.