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 (although he himself protested the naming after him).

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

By contradiction. (A direct proof of the existence of a maximal element is not possible, so we freely use the axiom of excluded middle, which in any case follows from AC, the axiom of choice. The one use made of AC is noted below. WLOG we prove the result for posets.)

Suppose SS has no maximal element. Then every chain CSC \subseteq S has a strict upper bound: an element xx such that c<xc \lt x for all cCc \in C. (Take an upper bound yy of CC, then yy is not maximal by supposition, so any xx with y<xy \lt x will serve.) For each WSW \subseteq S that is well-ordered by \leq, use AC to choose a strict upper bound f(W)f(W) of WW. Given a such a function f:Well(S)Sf: Well(S) \to S from well-ordered subsets of SS to SS, let us say WWell(S)W \in Well(S) is ff-inductive if for every xWx \in W, we have x=f({yW:y<x})x = f(\{y \in W: y \lt x\}).

Let Y,ZWell(S)Y, Z \in Well(S) be ff-inductive sets; we will show one is an initial segment of the other. Let II be the union of all subsets that are initial segments of both YY and ZZ; then II is maximal among initial segments of both (possibly empty). Suppose II is properly contained in both; let yy be the least element of YIY \setminus I, and zz the least element of ZIZ \setminus I. Then {xY:x<y}=I={xZ:x<z}\{x \in Y: x \lt y\} = I = \{x' \in Z: x' \lt z\}, so by ff-inductivity of Y,ZY, Z, we have y=f(I)=zy = f(I) = z. Thus II extends to an initial segment I{y}=I{z}I \cup \{y\} = I \cup \{z\}, contradicting maximality of II. Therefore we must have I=YI = Y or I=ZI = Z, so one of Y,ZY, Z is an initial segment of the other.

So the collection of ff-inductive sets is totally ordered by inclusion of initial segments, making their union UU the maximal ff-inductive set (Lemma 1 below). Appending its strict upper bound f(U)f(U), the chain U{f(U)}U \cup \{f(U)\} is a larger ff-inductive set, contradiction. The proof is complete.

Remark

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

Remark

The proof above (does anyone know where it appears in the literature?) can be seen as an application of general recursion theory à la Paul Taylor’s book, which in turn is inspired in large part by Osius. In particular, initial segments are the same as PP-coalgebra maps between well-founded coalgebras, and the maximal UU constructed is a maximal attempt with respect to a partial algebra structure f:P(S)Sf: P(S) \rightharpoonup S, following Taylor’s formulation of the recursion scheme. For a slightly different arrangement of the facts, one very commonly found in the literature, see the account of the Bourbaki-Witt theorem below.

Lemma

Let P αP_\alpha be a collection of subsets of a set SS, each equipped with a well-ordering α\leq_\alpha, such that for any α,β\alpha, \beta, one of P α,P βP_\alpha, P_\beta (each with their orderings) is an initial segment of the other. Let PP be the union αP α\cup_\alpha P_\alpha, equipped with the ordering xyx \leq y if x αyx \leq_\alpha y in some P αP_\alpha containing them both. Then PP is well-ordered by \leq, with each P αP_\alpha an initial segment of PP.

Proof

Observe that \leq is well-defined, and is a total order: if x,yPx, y \in P, then xP αx \in P_\alpha and yP βy \in P_\beta for some α,β\alpha, \beta, where one of P α,P βP_\alpha, P_\beta contains the other, say P αP βP_\alpha \subseteq P_\beta, whence x,yx, y are comparable in P βP_\beta. If TT is an inhabited subset of PP, then TP αT \cap P_\alpha is inhabited for some α\alpha, so there is a minimal element tTP αt \in T \cap P_\alpha with respect to α\leq_\alpha. This tt is minimal in TT with respect to \leq, for if sTs \in T, sts \leq t, then sP αs \in P_\alpha by the initial segment condition, and then tst \leq s by definition of tt.

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 XPAX \in P 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. If CC is a chain in the poset consisting of subsets X αX_\alpha, then their union XX is a well-order by Lemma 1, and so the hypothesis of Zorn’s lemma is satisfied.

  2. By Zorn’s lemma, conclude that 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.

Bourbaki-Witt theorem

Many accounts of the proof of Zorn’s lemma start by establishing first the so-called Bourbaki-Witt theorem, which does not require AC and is of interest in its own right. However, it too does not admit a constructive proof; see Bauer for a demonstration that it is not valid in the effective topos. That said, the issue is subtle enough that the Bourbaki-Witt theorem nonetheless holds in topos with a geometric morphism to SetSet, for instance any Grothendieck topos, assuming B-W holds in SetSet (Bauer-Lumsdaine 2013).

Theorem

(Bourbaki-Witt) Let PP be an inhabited poset such that every chain has a least upper bound, and s:PPs: P \to P a function that is inflationary: satisfies xs(x)x \leq s(x) for all xx. Then ss has a fixed point: an xx such that s(x)=xs(x) = x.

Proof

Without loss of generality, assume PP has a bottom element 00; otherwise just pick an element aPa \in P and replace PP with the upward set a\uparrow a.

Say that a subset IPI \subseteq P is ss-inductive if: 0I0 \in I, II is closed under ss (s(I)Is(I) \subseteq I), and II contains the sup of any chain in II. The intersection of any family of ss-inductive sets is also ss-inductive, so the intersection MM of all ss-inductive sets is ss-inductive.

The idea is that MM is totally ordered (is a chain) by the following intuition: the elements of MM are 0,s(0),ss(0),s n(0),0, s(0), s s(0), \ldots s^n(0), \ldots, where we continue by transfinite induction: at limit ordinals α\alpha define s α(0)s^\alpha(0) to be the sup of {s β(0):β<α}\{s^\beta(0): \beta \lt \alpha\}, and at successors define s α+1(0)=s(s α(0))s^{\alpha + 1}(0) = s(s^\alpha(0)). We cannot have a strictly increasing chain that goes on forever, by cardinality considerations, so at some point we hit an α\alpha such that s α+1(0)=s α(0)s^{\alpha + 1}(0) = s^\alpha(0), which provides a fixed point. (What could be nonconstructive about that? See this comment by Lumsdaine.) In any case, once we prove MM is totally ordered, the sup of MM is obviously a fixed point.

Without getting into ordinals, one may prove MM is totally ordered as follows. Call an element cMc \in M a cap if x<cx \lt c for xMx\in M implies s(x)cs(x) \leq c. For each cMc \in M, put M c={xM:xcs(c)x}M_c = \{x \in M: x \leq c \vee s(c) \leq x\}. A routine verification shows M cM_c is ss-inductive if cc is a cap, so in fact M c=MM_c = M by minimality of MM. Then, show that the set of caps is ss-inductive. This is also routine if we avail ourselves of the just-proven fact that M c=MM_c = M for any cap (but consult Appendix 2 in Lang’s Algebra if you get stuck). So again by minimality of MM, every element of MM is a cap. Finally, if c,dMc, d \in M, use the fact that cc is a cap to conclude either that dcd \leq c or s(c)ds(c) \leq d, whence cs(c)dc \leq s(c) \leq d; thus we see any two elements are comparable.

For a discussion of how to get from Bourbaki-Witt to Zorn, see either Lang or this nn-Category Café post by Tom Leinster, especially the main post which gives three very closely related results bearing on Zorn’s lemma, and a follow-up comment here which brings in Bourbaki-Witt.

Remark

An alternative proof of Bourbaki-Witt would be along lines similar to those used to show AC implies Zorn’s lemma. Given the inflationary function ss, consider the function f:Well(S)Sf: Well(S) \to S which takes a well-ordered subset WW to s(supW)s(\sup W). If ss has no fixed points, then f(W)f(W) will always be a strict upper bound of WW, and from there one derives a contradiction exactly as in the proof of Zorn’s lemma.

Remark

The Bourbaki-Witt theorem is an example of a fixed-point theorem. We should point out its kinship with the quite remarkable fixed-point theorem due to Pataraia, who observed that the conclusion of the Bourbaki-Witt theorem may be strengthened quite considerably, and proved constructively (!), if we change the hypothesis to say that ss is a monotone operator (preserves the order \leq) on an inhabited dcpo. See fixed point for a brief account, and this blog post for some appreciative commentary.

Usage/applications

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.

References

Revised on January 28, 2016 19:56:50 by Todd Trimble (67.81.95.215)