Zorn's lemma

Let $(P,\le )$ be a nonempty partially ordered set. If every chain in a partial order $C\subseteq P$ has an upper bound in $P$, then $P$ has a maximal element. The hypothesis meansThe upper bound may depend on $C$ and need not belong to $C$. A least upper bound is not required. The conclusion asserts that some $m\in P$ satisfies $m\le x⟹x=m$; it does not assert a greatest element, which would satisfy $x\le m$ for every $x\in P$.^[ref]

Here a chain in a partial order may be the empty set. Every member of $P$ is an upper bound of the empty chain in a partial order, so including it in the hypothesis already forces $P$ to be nonempty. If “chain” means only nonempty chains in a partial order, the separate nonempty-$P$ assumption is essential: the empty poset otherwise satisfies the hypothesis vacuously and has no maximal element. These are two equivalent conventions for the theorem.

The strength of Zorn's lemma is that compatible partial constructions can have a completed, unextendible member without an explicit procedure for finding it. The next examples separate the upper bound calculation from the reason a maximal element has the desired property. All chains in a partial order must be covered, including uncountable ones, rather than just increasing sequences. The condition is sufficient, not necessary: a poset can have a maximal element and still have an unbounded chain in a partial order elsewhere.

Consider the following finite set of subsets, ordered by subset containment:Every nonempty chain in a partial order has a greatest element within that chain in a partial order, hence an upper bound in $P$. For the empty chain in a partial order, choose $\varnothing \in P$. Thus the hypothesis of Zorn's lemma holds. The two maximal elements are $\{a,b\}$ and $\{b,c\}$: neither is a proper subset of another member of $P$. There is no greatest element, because it would have to contain both, and no member of $P$ contains $\{a,b,c\}$.

For the chain in a partial order $C=\{\varnothing ,\{b\}\}$, the member $\{b\}$ is already an upper bound, although it is not a maximal element of $P$. Both orange members are also upper bounds for $C$. A chain in a partial order need not have a unique upper bound, and the upper bound used to check the hypothesis need not be the eventual maximal element.

The restriction to chains in a partial order matters. The subset $\{\{a\},\{c\}\}\subseteq P$ has no upper bound in $P$, but its two members are incomparable, so it is not a chain in a partial order. Requiring every subset of $P$ to have an upper bound would be much stronger: taking that subset to be $P$ itself would force a greatest element.

Every vector space $V$ over a field $F$ has a basis, assuming the axiom of choice. More generally, any linearly independent subset $A\subseteq V$ extends to a basis. This is an algebraic Hamel basis: each representation uses a finite linear combination, even when the basis is infinite.^[ref]

Use the poset of linearly independent subsets containing $A$:It is a set, being a subset of the power set of $V$, and is nonempty because $A\in {\mathcal{P}}_A$.

A short proof outline supplies both essential steps:

Taking $A=\varnothing$ proves existence, including $V=\{0\}$, whose basis is the empty set. The chain in a partial order need not be indexed by the natural numbers: only the finitely many members needed for a particular linear relation are compared. An arbitrary union of linearly independent sets can fail: $\{v\}$ and $\{2v\}$ for a nonzero vector over the real numbers are each linearly independent, but their union is linearly dependent. The nesting of a chain in a partial order is what prevents this failure.

For an explicit basis extension in ${\mathbb{R}}^2$, start with $A=\{u\}$, where $u=(1,1)$. Its linear span is the line $y=x$. Adding $w=(1,-1)$ preserves linear independence, because $w$ is outside that line, and gives a basis. Every vector has the finite linear combinationThe vector $2u=(2,2)$ cannot be added while preserving linear independence: it is already in the linear span. Many choices outside the line work, so maximality does not select a unique basis.

For a finite-dimensional vector space with a supplied finite spanning set, a greedy algorithm scans the list, retaining each vector precisely when it is outside the linear span of those already retained. Starting with a linearly independent $A$, the same scan adjoins only the needed vectors. Retained vectors remain linearly independent, and every skipped vector is in the final linear span, so the result is a basis containing $A$. Finite reasoning needs no axiom of choice.

For an arbitrary vector space, this finite stopping argument is unavailable. Accepting Zorn's lemma asserts existence of a maximal element once every chain in a partial order has an upper bound; it supplies no general computational recipe. Over ZF, Zorn's lemma, the axiom of choice and the well-ordering theorem are equivalent. Particular infinite vector spaces can still have explicit bases, such as $1,x,x^2,\dots$ for the vector space of univariate polynomials over a specified field; infinity alone does not force a nonconstructive argument.^[ref]

Assume the axiom of choice and suppose a poset satisfying the hypothesis has no maximal element. Fix a choice function on its nonempty subsets. By transfinite recursion, choose at each ordinal stage an upper bound of the chain in a partial order already constructed, then choose a strictly larger member. Both choices are available, including the initial empty stage. This produces distinct members throughout the Hartogs ordinal of $P$, contradicting the Hartogs theorem. Thus a maximal element exists. Conversely, apply Zorn's lemma to partial choice functions on a family of nonempty sets, ordered by extension. A chain in a partial order has the compatible union as an upper bound, and a maximal element must be defined on the whole family, since one missing value could be adjoined.

Zorn's lemma was introduced in 1935 to shorten algebra proofs using choice or the well-ordering theorem.^[ref]