nLab
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,\le )$, an element $x$ of $S$ is maximal if $y\le x$ whenever $x\le y$.

• A chain in $S$ is a subset $A\hookrightarrow S$ such that $\le$ is a total order on $A$.

• An upper bound of a subset $A$ of $S$ is an element $x$ of $S$ such that $y\le x$ whenever $y\in A$.

Definition

The proposition Zorn's Lemma states that each preordered set $S$ has a maximal element if every chain in $S$ 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 $A\subseteq S$ which is well-ordered under the preorder it inherits from $S$, choose a strict upper bound $f(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 $A$ is $f$-inductive if for all $x\in A$, $x=f(\{y\in A:y<x\})$. Thus $A_0=\varnothing$ is inductive, as is $A_1=\{f(A_0)\}$, $A_2=A_1\cup \{f(A_1)\}$, $A_3=A_2\cup \{f(A_2)\}$ and so on. Intuitively, using the chain hypothesis, one can (by transfinite induction) define $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_{\alpha }$ does have an upper bound $x$. This element is necessarily maximal.

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

   $$\{y\in A:y<x\}=\{y\prime \in B:y\prime <z\},$$\{y \in A: y \lt x\} = \{y' \in B: y' \lt z\} ,

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

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

Remark

The empty set is not an exception to Zorn's lemma, as the chain $\varnothing$ 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 $A$ be a set, and consider the poset whose elements are pairs $(X,R)$, where $X\subseteq A$ and $R$ is a (classical) well-ordering on $X$, ordered by $(X,R)\le (Y,S)$ if $X$ as a well-ordered set is an initial segment of $Y$. The hypothesis of Zorn’s lemma is easily established: given a chain $(X_t,R_t{)}_{t\in T}$, put $X={\bigcup }_t{X}_t$ and define the relation $R$ on $X$ by $xRy$ if $x{R}_{t}y$ for any (hence all) $X_t$ containing both $x,y$. Then $R$ is a well-ordering: if $U\subseteq X$ is any nonempty set, then $U\cap X_t$ is nonempty for some $t$, and the minimal element of $U$ with respect to $R$ will also be the minimal element of $U\cap X_t$ with respect to $R_t$ (crucially using here the initial segment condition).

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

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

Usage

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

Zorn's lemma may be used to prove all of the following:

• The Hausdorff maximal principle: Every chain in $S$ is contained in a maximal chain.
• The ultrafilter theorem: Every proper filter on a set may be extended to an ultrafilter.
• The maximal ideal theorem: Every ideal in a ring may be extended to a maximal ideal.
• The basis theorem: Every vector space (over a field) has a basis.
• etc …

Some of these are equivalent to Zorn's lemma, while some are weaker; conversely, some additionally require excluded middle.