nLab Zorn's lemma

Zorns Lemma

Context

Foundations

foundations

The basis of it all

 Set theory

set theory

Foundational axioms

foundational axioms

Removing axioms

Zorn's Lemma

Idea

Zorn's lemma, also known as Kuratowski-Zorn 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. Sometimes the maximal element is only a convenience, and it’s enough to use the entire poset or perhaps the collection of all chains instead; sometimes, the use of Zorn’s Lemma is essential.

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 a 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. (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 of SS that are initial segments of both YY and ZZ; then II is maximal among such initial segments of both. 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 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 (with its unique structure as preordered set) is not an exception to Zorn's lemma, as the chain \emptyset does not have an upper bound.

Remark

The proof above (originally by Kneser) 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 , 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.

Well-ordered formulation

Terry Taopoints out (Remark 14) that the proof of Zorn’s Lemma uses only the well-ordered chains, allowing a weakened hypothesis. This is most naturally stated in the context of quosets rather than posets:

Definition
  • Given a quasiordered set (S,<)(S, \lt), an element xx of SS is maximal if x<yx \lt y never holds.

  • A well-ordered chain (or a well-ordered subset or simply a well-chain) in SS is a subset ASA \hookrightarrow S such that <\lt is a well order on AA.

  • A strict upper bound? of a subset AA of SS is an element xx of SS such that y<xy \lt x whenever yAy \in A.

The change to strict upper bounds is natural in a quasiordered context; it makes no difference in the presence of excluded middle, since we wish to conclude that a maximal element exists; if there is no maximal element, then any set with an upper bound immediately gets a strict upper bound along with it.

Definition

The well-ordered Zorn's Lemma states that any quasiordered set SS has a maximal element if every well-chain in SS has a strict upper bound, or more simply that it is not possible in a quasiordered set that every well-chain has a strict upper bound. Or from another perspective, if every well-ordered subset of a quasiordered class SS has a strict upper bound, then SS is a proper class.

The ‘more simply’ formulation is equivalent (even constructively) because, on the one hand, if mm is a maximal element, then m{m} is a well-chain with no strict upper bound, contradicting the hypothesis; while on the other hand, anything whatsoever is true of a nonexistent quoset SS. The ‘another perspective’ is then immediate if by a ‘proper class’ one simply means a class that is not a set.

Assuming excluded middle, this is (a priori) stronger than the usual Zorn’s Lemma, since only well-ordered chains are required to have upper bounds. (Of course, once all the proofs are in, they are both simply equivalent to the Axiom of Choice.) In constructive mathematics, however, it is not stronger, for two reasons: just because SS has no maximal element, that doesn’t mean that every upper bound has a strict upper bound; and even if this could be fixed, we would only conclude that SS does not not have a maximal element. However, I intend to argue that this version of Zorn’s Lemma should be regarded as more constructively acceptable; some relativized versions are flat-out true.

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

Due Kuratowski and, independently later, Zorn:

  • Casimir Kuratowski, Une méthode d’élimination des nombres transfinis des raisonnements mathématiques, Fundamenta Mathematicae 3 (1922) 76–108 doi

  • Max Zorn, A remark on method in transfinite algebra, Bull. Amer. Math. Soc. 41 (10): 667–670 (1935)doi

  • Serge Lang, Algebra (third edition), Addison-Wesley 1993.

  • Gerhard Osius, Categorical set theory: a characterization of the category of sets, Jour. Pure Appl. Alg. 4 (1974), 79–119. doi:10.1016/0022-4049(74)90032-2

  • Andrej Bauer, On the Failure of Fixed-Point Theorems for Chain-complete Lattices in the Effective Topos, Electronic Notes in Theoretical Computer Science, 249 (2009) 157–167, doi:10.1016/j.entcs.2009.07.089 and

    Theoretical Computer Science, 430 (2012) 43–50, doi:10.1016/j.tcs.2011.12.005. arXiv:0911.0068.

  • Andrej Bauer, Peter LeFanu Lumsdaine, On the Bourbaki-Witt Principle in Toposes, Math. Proc. Cam. Phil. Soc. 155 (2013), no. 1, 87–99 doi:10.1017/S0305004113000108, arXiv:1201.0340.

  • Hellmuth Kneser, Das Auswahlaxiom und das Lemma von Zorn, Mathematische Zeitschrift, 96:62–63, 1967; available here

On Zorn’s lemma and Boolean algebra in intuitionistic type theories:

  • John Lane Bell, Zorn’s lemma and complete Boolean algebras in intuitionistic type theories, The Journal of Symbolic Logic, 62(4):1265–1279, 1997 (doi:10.2307/2275642)

Last revised on December 13, 2022 at 08:33:04. See the history of this page for a list of all contributions to it.