nLab
Zorn's lemma

Zorn's Lemma

Idea

Zorn's lemma is a proposition in set theory and order theory. It says that: A preorder in which every sub-total order has an upper bound has a maximal element.

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.

Statement and proofs

Definition
  • Given a preordered set (S,)(S, \leq), an element xx of SS is maximal if yxy \leq x whenever xyx \leq y.

  • A chain in SS is a subset ASA \hookrightarrow S such that \leq is a total order on AA.

  • An upper bound of a subset AA of SS is an element xx of SS such that yxy \leq x whenever yAy \in A.

Definition

The proposition Zorn's Lemma states that each preordered set SS has a maximal element if every chain in SS has an upper bound.

Theorem

Suppose the axiom of choice holds. Then Zorn's Lemma holds.

Proof

The proof may be arranged in the following steps:

  1. For each subset of ASA \subseteq S which is well-ordered under the preorder it inherits from SS, choose a strict upper bound f(A)Sf(A) \in S 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.)

  2. Say a well-ordered subset AA is ff-inductive if for all xAx \in A, x=f({yA:y<x})x = f(\{y \in A: y \lt x\}). Thus A 0=A_0 = \emptyset is inductive, as is A 1={f(A 0)}A_1 = \{f(A_0)\}, A 2=A 1{f(A 1)}A_2 = A_1 \cup \{f(A_1)\}, A 3=A 2{f(A 2)}A_3 = A_2 \cup \{f(A_2)\} and so on. Intuitively, using the chain hypothesis, one can (by transfinite induction) define A αA_\alpha for ordinals α\alpha by appending strict upper bounds in this way, until at some point α\alpha, one has run out of further strict upper bounds to choose from. But by hypothesis, A αA_\alpha does have an upper bound xx. This element is necessarily maximal.

  3. More precisely, ff-inductive sets are well-ordered by inclusion. For if AA and BB are distinct (well-ordered and) ff-inductive sets, then there is a smallest element contained in one but not the other, say xAx \in A but ¬(xB)\neg(x \in B). But then {yA:y<x}\{y \in A: y \lt x\} is a down-closed subset of BB, i.e., is an initial segment of BB. If it were a proper subset of BB, then for the least zBz \in B in its complement we would have

    {yA:y<x}={yB:y<z}, \{y \in A: y \lt x\} = \{y' \in B: y' \lt z\} ,

    whence by applying ff to both sides, we infer x=zx = z by ff-inductivity of AA and BB, contradiction. In that case, B={yA:y<x}B = \{y \in A: y \lt x\}. In other words, one of A,BA, B must be an initial segment of the other.

  4. Therefore the union of all ff-inductive sets is also ff-inductive. Being the maximal ff-inductive set MM, it contains any of its upper bounds (in fact there is only one up to isomorphism), and this element is necessarily maximal in SS.

Remark

The empty set is not an exception to Zorn's lemma, as the chain \emptyset does not have an upper bound.

Theorem

If Zorn's Lemma and the principle of excluded middle hold, then so do the well-ordering principle and the axiom of choice.

Proof

We first show that Zorn’s lemma implies the classical well-ordering principle. The axiom of choice easily follows from the well-ordering principle.

  1. Let AA be a set, and consider the poset whose elements are pairs (X,R)(X, R), where XAX \subseteq A and RR is a (classical) well-ordering on XX, ordered by (X,R)(Y,S)(X, R) \leq (Y, S) if XX as a well-ordered set is an initial segment of YY. The hypothesis of Zorn’s lemma is easily established: given a chain (X t,R t) tT(X_t, R_t)_{t \in T}, put X= tX tX = \bigcup_t X_t and define the relation RR on XX by xRyx R y if xR tyx R_t y for any (hence all) X tX_t containing both x,yx, y. Then RR is a well-ordering: if UXU \subseteq X is any nonempty set, then UX tU \cap X_t is nonempty for some tt, and the minimal element of UU with respect to RR will also be the minimal element of UX tU \cap X_t with respect to R tR_t (crucially using here the initial segment condition).

  2. By Zorn’s lemma, the poset above contains a maximal element (X,R)(X, R), where XAX \subseteq A. We claim X=AX = A; suppose not (here is where we need excluded middle), and let xx be a member of the complement ¬X\neg X. Well-order X{x}X \cup \{x\}, extending RR by deeming xx to be the final element. This shows (X,R)(X, R) was not maximal, contradiction. Hence any set AA may be well-ordered.

  3. The axiom of choice follows: suppose given a surjection p:EBp: E \to B, so that every fiber p 1(b)p^{-1}(b) is inhabited. Consider any well-ordering of EE, and define s:BEs: B \to E by letting s(b)s(b) be the least element in p 1(b)p^{-1}(b) with respect to the well-ordering. This gives a section ss of pp.

Usage

It is very common, when starting with a preordered set SS, to apply Zorn's lemma not to SS itself but to an up-set (an under category) in SS. That is, one starts with an element xx of SS and proves the existence of a maximal element comparable to xx.

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.

Revised on December 20, 2012 23:24:45 by Toby Bartels (98.19.38.141)