Order, Zorn's Lemma, and the Axiom of Choice

Let $(P, \le)$ be a poset (Partial order and partially ordered set). A subset $C \subseteq P$ is a chain if any two of its elements are comparable: for all $x, y \in C$, either $x \le y$ or $y \le x$.

Equivalently, $C$ is a chain if the restriction of $\le$ to $C$ is a total order on $C$.

• The empty set is a chain, and so is every singleton, both vacuously. This is not a technicality to be waved past: the empty chain is exactly what forces a chain-complete poset to have a least element (Chain-complete poset), and that least element is the starting point of the Bourbaki–Witt construction (Bourbaki–Witt fixed point theorem). A convention that quietly excludes the empty chain has to reintroduce the same content as a separate hypothesis.
• A chain need not be finite, need not be countable, and need not have a largest element. In the power set of $\mathbb{N}$ ordered by inclusion, the sets $\{1, \dots, n\}$ for $n \ge 1$ form a chain with no largest element.
• "Chain" is a property of a subset, not of the ambient poset. The whole poset $P$ is a chain exactly when $\le$ is a total order.

Let $(P, \le)$ be a poset (Partial order and partially ordered set) and $S \subseteq P$.

An element $u \in P$ is an upper bound of $S$ if $s \le u$ for every $s \in S$.

An element $u \in P$ is a least upper bound (or supremum) of $S$ if $u$ is an upper bound of $S$ and $u \le v$ for every upper bound $v$ of $S$. When it exists we write $u = \sup S$.

An element $u \in P$ is a strict upper bound of $S$ if $s < u$ for every $s \in S$.

• A least upper bound is unique when it exists. If $u$ and $u'$ are both least upper bounds of $S$ then each is an upper bound and each is below the other, so $u \le u'$ and $u' \le u$, whence $u = u'$ by antisymmetry (Partial order and partially ordered set). This is what makes the notation $\sup S$ legitimate. Antisymmetry is not peculiar to this argument: the same two-inequality step gives uniqueness of a greatest element (Maximal element and greatest element), and it is used essentially in Bourbaki–Witt fixed point theorem, whose fixed point is obtained by passing from $f(c) \le c$ and $c \le f(c)$ to $f(c) = c$. Drop antisymmetry and it is the conclusion, not merely the notation, that goes: on two distinct elements each below the other, every subset still has a least upper bound, yet the map exchanging the two satisfies $x \le f(x)$ and has no fixed point.
• Every element of $P$ is an upper bound of the empty set, vacuously. Consequently $\sup \emptyset$, when it exists, is the least element of $P$.
• An upper bound of $S$ need not belong to $S$, and $S$ may have many upper bounds and no least one. In $\mathbb{Q}$ with its usual order, the set $\{q \in \mathbb{Q} : q^2 < 2\}$ has upper bounds but no least upper bound.
• In a poset, a strict upper bound is exactly an upper bound outside $S$. If $u$ is strict then $u\notin S$, since $u<u$ is impossible. Conversely, if $u$ is an upper bound and $u\notin S$, then every $s\in S$ satisfies $s\le u$ and $s\ne u$, hence $s<u$. This distinction from an arbitrary upper bound matters in Zorn's lemma, where the argument must produce one outside the chain.

Let $(P, \le)$ be a poset (Partial order and partially ordered set) and $m \in P$.

$m$ is a maximal element of $P$ if no element of $P$ is strictly above it: there is no $x \in P$ with $m < x$. Equivalently, for every $x \in P$, if $m \le x$ then $x = m$.

$m$ is a greatest element (or maximum) of $P$ if $x \le m$ for every $x \in P$.

Minimal and least elements are defined dually, reversing every inequality.

• Maximal is not greatest, and the difference is the single most common confusion about ordered sets. A maximal element has nothing strictly above it; a greatest element is above everything. In a total order the two coincide, which is why the distinction is invisible to intuition trained on $\mathbb{R}$, but a partial order may have many maximal elements and no greatest one. The refutation is FALSE: every maximal element is a greatest element, witnessed by Two maximal elements and no greatest element ↗.
• A greatest element is always maximal, and it is unique when it exists: if $m$ and $m'$ are both greatest then $m \le m'$ and $m' \le m$, so $m = m'$ by antisymmetry. Maximal elements need not be unique.
• Zorn's lemma concludes that a maximal element exists, never that a greatest one does (Zorn's lemma). In a particular poset the maximal element it produces may happen to be greatest, since a greatest element is maximal; what Zorn never supplies is a guarantee of greatestness. Every application of Zorn therefore has to be phrased so that maximality is enough, typically by arranging the poset so that a maximal object cannot be extended, which is a statement about nothing being strictly above it.
• Maximality says nothing about comparability: a maximal element may be incomparable to other elements, including to other maximal ones. In Two maximal elements and no greatest element ↗ the two maximal elements are incomparable to each other, and in an antichain every element is maximal and is incomparable to all the rest.

A poset $(P, \le)$ is chain-complete if every chain $C \subseteq P$ (Chain in a poset) has a least upper bound $\sup C$ in $P$ (Upper bound, least upper bound, and strict upper bound).

The empty set is a chain, so a chain-complete poset has an element $\bot := \sup \emptyset,$ and $\bot$ is the least element of $P$: every $x \in P$ is an upper bound of $\emptyset$, so $\bot \le x$ by leastness. In particular a chain-complete poset is nonempty.

A map $f : P \to P$ is progressive (also inflationary, or increasing in Bourbaki's sense) if $x \le f(x) \quad \text{for every } x \in P.$

• Progressive is not monotone. A progressive map is required to move each point weakly upward; it is not required to preserve the order, and Bourbaki–Witt fixed point theorem assumes no monotonicity whatsoever. This is what makes the theorem strong enough to drive Zorn's lemma, where the map is built from an arbitrary choice function and has no reason to be monotone.
• On the empty-chain convention. Some authors let "chain" mean nonempty chain, and then state Bourbaki–Witt for a nonempty chain-complete poset. The two conventions give the same theorem. Given $P \ne \emptyset$ chain-complete in the nonempty-chain sense and $f$ progressive, pick any $p \in P$ and pass to $P_{\ge p} = \{x \in P : p \le x\}$: it contains $p$, it is closed under $f$ because $f$ is progressive, the supremum of a nonempty chain in $P_{\ge p}$ again lies in $P_{\ge p}$, and $\sup \emptyset = p$ there. So $P_{\ge p}$ is chain-complete in the sense used here. Including the empty chain simply packages that reduction into the definition, and it is Wikipedia's convention for a pointed chain-complete order.
• Chain-completeness is strictly weaker than requiring least upper bounds for all subsets (which would make $P$ a complete lattice). The power set of any set is a complete lattice, hence chain-complete (The power set is chain-complete, with union as supremum ↗); the posets Zorn's lemma is applied to usually are not.
• The hypothesis cannot be dropped from Bourbaki–Witt fixed point theorem: a progressive map on a poset that is not chain-complete may have no fixed point (A progressive map with no fixed point, on a poset that is not chain-complete ↗).

Let $n \in \mathbb{N}$ and let $F$ be a function with domain $n$ all of whose values are nonempty sets. Then the family of its values, $\mathcal{F} = F[n] = \{\, F(i) : i \in n \,\}$, has a choice function (Choice function).

This is a theorem of ZF: its proof uses no form of the Axiom of Choice (The Axiom of Choice).

What is proved below is exactly the displayed statement, by induction on $n$. The natural number $n$ serves as the index set in the von Neumann sense, $n = \{0, 1, \dots, n-1\}$ (The natural numbers $\mathbb{N}$ (von Neumann)), so "$F$ has domain $n$" says precisely that the members of $\mathcal{F}$ are listed as $F(0), \dots, F(n-1)$. The listing need not be injective, and $\mathcal{F}$ is the set of values, so repetitions are harmless and are not counted.

The displayed statement and its proof use only a natural-number-indexed function. They do not identify an arbitrary finite family with a particular enumeration.

• Later finiteness terminology. A finite set is defined later as one equinumerous with a natural number (Finite, countably infinite, countable, uncountable ↗). That terminology is not used in the proof above, which keeps its exact indexed-family scope.
• Where the Axiom of Choice would be needed, and why it is not needed here. Step 2.2 picks one element out of one nonempty set. That is a single existential instantiation, licensed by first-order logic alone. The induction performs one such instantiation per stage, and the stages are indexed by a natural number, so the process terminates. ZF cannot in general turn an arbitrary infinite family of nonempty sets into a simultaneous choice function; that is the gap The Axiom of Choice fills. An infinite family with a distinguished element in each member may still have an explicit choice function in ZF, as Russell's shoes and socks ↗ shows.
• Why the family is presented as an indexed one. Stated over "a family of exactly $n$ sets", the successor step would have to assert that deleting one member of a family of $n+1$ sets leaves exactly $n$, which is a claim about cardinality and needs a theory of finiteness this page does not have. Indexed by $n$, the same step is the restriction $F \restriction n$ of a function, which is immediate from $n \subseteq \sigma(n)$ and costs nothing. Nothing else in the argument changes.
• The listing may repeat, and the argument is arranged so that repetition needs no separate treatment: $g$ is built by overwriting rather than by adjoining, so it is a function whether or not $S$ already occurs among $F(0), \dots, F(n-1)$. In particular $\mathcal{F}$ may have strictly fewer than $n$ members.
• The lemma is not a special case of the Axiom of Choice that happens to be provable; it is the precise boundary of what is free. Russell's shoes and socks ↗ makes the boundary concrete, and Finite choice written out: a choice function for three sets ↗ works this induction out on a small family.

Let $(P, \le)$ be a chain-complete poset and $f : P \to P$ a progressive map (Chain-complete poset). A subset $A \subseteq P$ is $f$-admissible (or simply admissible, when $f$ is fixed) if:

• (C1) closed under $f$: $f(x) \in A$ for every $x \in A$;
• (C2) closed under chain suprema: $\sup C \in A$ for every chain $C \subseteq A$.

• (C2) already forces $\bot \in A$. The empty set is a chain contained in $A$ (Chain in a poset), and $\sup \emptyset = \bot$, so every admissible set contains the least element of $P$. Presentations that list "$\bot \in A$" as a third condition are therefore stating a consequence, not an extra hypothesis. This is the first of four places on this page where insisting that the empty set counts as a chain removes a case rather than creating one; the others are The cut at an extremal element is closed under chain suprema, A supremum of extremal elements is extremal and Every element of $M$ is extremal.
• The suprema in (C2) are taken in $P$ and exist there by chain-completeness; the condition is that they land back inside $A$.
• $P$ itself is admissible, so admissible sets exist. The content of A smallest admissible set exists is that there is a smallest one, and its minimality is what carries the two decisive steps of the Bourbaki–Witt argument, Everything in $M$ is comparable to an extremal element and Every element of $M$ is extremal: to prove that all elements of the smallest admissible set $M$ have some property, one shows that the elements of $M$ with that property again form an admissible set. The remaining lemmas use only admissibility of $M$, progressivity of $f$, and the order axioms.
• Nothing here assumes $f$ is monotone, injective, or continuous in any sense. Only (C1), (C2) and progressivity are ever used.

Let $(P, \le)$ be a chain-complete poset and $f : P \to P$ progressive (Chain-complete poset). Then there is a smallest $f$-admissible subset $M \subseteq P$ (Admissible subset (Bourbaki–Witt)): $M$ is admissible, and $M \subseteq A$ for every admissible $A \subseteq P$.

• Uniqueness is automatic: two smallest admissible sets each contain the other, so they are equal. This licenses writing $M$ for "the" smallest admissible set throughout Extremal element and its cut (Bourbaki–Witt) and the lemmas that follow.
• $M$ is never empty. Condition (C2) applied to the empty chain puts $\bot = \sup\emptyset$ into every admissible set, so $\bot \in M$.
• Minimality is used exactly twice in what follows, in Everything in $M$ is comparable to an extremal element and in Every element of $M$ is extremal, and both times in the same shape: to prove that all of $M$ has some property, one shows that the elements of $M$ with that property again form an admissible set, which minimality then forces to be all of $M$. That pattern is what replaces transfinite recursion in this proof of Bourbaki–Witt fixed point theorem. The remaining lemmas use only admissibility of $M$, progressivity of $f$, and the order axioms.

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, and let $M$ be the smallest $f$-admissible subset of $P$ (A smallest admissible set exists).

An element $x \in M$ is extremal if $\text{for every } y \in M \text{ with } y < x, \quad f(y) \le x.$

For $x \in M$, the cut at $x$ is the subset $M_x := \{\, y \in M \ : \ y \le x \ \text{ or } \ f(x) \le y \,\} \subseteq M.$

• Read extremality as: $x$ cannot be jumped over from below. If $y$ sits strictly below $x$ inside $M$, then applying $f$ to $y$ does not carry it past $x$. Nothing in the definition says such $y$ exist; $\bot$ is extremal vacuously.
• The cut $M_x$ is the set of elements of $M$ that are comparable to $x$ in the strong sense of lying at or below $x$, or at or above $f(x)$. It deliberately omits anything strictly between $x$ and $f(x)$. The whole Bourbaki–Witt argument consists of showing that for extremal $x$ the cut is everything (Everything in $M$ is comparable to an extremal element) and that every element is extremal (Every element of $M$ is extremal), and those two facts together say precisely that $M$ is totally ordered (The smallest admissible set is a chain).
• Both notions are relative to $M$ and to $f$, not to $P$. They are scaffolding for one proof and are not used after Bourbaki–Witt fixed point theorem.

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, $M$ the smallest admissible set, and $x \in M$ extremal (Extremal element and its cut (Bourbaki–Witt)). Then the cut $M_x$ satisfies $f(y) \in M_x$ for every $y \in M_x$.

• The case $y = x$ is the one that explains the shape of the cut. It is precisely why $M_x$ is defined with $f(x) \le z$ rather than $x < z$: the image $f(x)$ must itself land inside $M_x$, and it does so on the upper side.
• Extremality of $x$ is used only in the first case, and it is exactly what stops $f$ from carrying an element from strictly below $x$ into the forbidden zone strictly between $x$ and $f(x)$. That zone is what the cut omits, and keeping it empty of elements of $M$ is what eventually makes $M$ a chain (The smallest admissible set is a chain).

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, $M$ the smallest admissible set, and $x \in M$ extremal (Extremal element and its cut (Bourbaki–Witt)). Then $\sup C \in M_x$ for every chain $C \subseteq M_x$.

• The empty chain is covered without a separate argument: it falls into the first case vacuously, and $\sup \emptyset = \bot \le x$.
• Note which property of the supremum each case uses. The first case uses leastness, that $s$ is below any upper bound; the second uses only that $s$ is an upper bound. Both halves of the definition of least upper bound are needed, which is why chain-completeness cannot be weakened here to the mere existence of some upper bound.
• Together with The cut at an extremal element is closed under $f$ this makes $M_x$ admissible, which is what Everything in $M$ is comparable to an extremal element feeds to minimality.

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, $M$ the smallest admissible set, and $x \in M$ extremal (Extremal element and its cut (Bourbaki–Witt)). Then $M_x = M$; that is, for every $y \in M$, either $y \le x$ or $f(x) \le y$.

• This is the first payoff of minimality, and the pattern is worth naming: to prove that everything in $M$ has a property, collect the elements that have it, show the collection is admissible, and let minimality do the rest. The same move proves Every element of $M$ is extremal.
• The conclusion is a comparability statement with a gap. It says nothing about elements strictly between $x$ and $f(x)$, and indeed the content of the lemma is that $M$ has none: an element of $M$ lies at or below $x$, or at or above $f(x)$, never inside.
• The hypothesis that $x$ is extremal is doing real work and cannot be dropped. It is what Every element of $M$ is extremal later supplies for every element, which is what turns this one-sided statement into total comparability (The smallest admissible set is a chain).

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, $M$ the smallest admissible set, and $x \in M$ extremal (Extremal element and its cut (Bourbaki–Witt)). Then $f(x)$ is extremal.

• Step 2.1 is where the comparability lemma earns its place. Without it there would be no way to rule out an element of $M$ sitting strictly between $x$ and $f(x)$, and such an element would break extremality of $f(x)$ immediately.
• Extremality is not a monotonicity condition in disguise. Nothing here assumes $f$ preserves order, and the proof never compares $f$ of two different elements except through $x$ itself.

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, $M$ the smallest admissible set, and $C \subseteq M$ a chain every element of which is extremal (Extremal element and its cut (Bourbaki–Witt)). Then $\sup C$ is extremal.

• Step 2.1 is the subtle one, and it is where chain-completeness does real work. The move from $y < s$ to "$y$ is not an upper bound of $C$" is exactly leastness of the supremum, closed off by antisymmetry: leastness gives $s \le y$, and it is antisymmetry that turns that together with $y \le s$ into $y = s$, contradicting $y \ne s$. If $\sup C$ were merely some upper bound of $C$, the step would fail and the lemma with it, which is why the Bourbaki-Witt hypothesis asks for least upper bounds rather than upper bounds.
• The empty chain is covered without comment: $\sup \emptyset = \bot$, and there is no $y \in M$ with $y < \bot$, so the condition holds vacuously.
• Nothing here needs $C$ to have a largest element, and in the intended application it does not have one.

Let $(P, \le)$ be a chain-complete poset, $f : P \to P$ progressive, and $M$ the smallest admissible set. Then every element of $M$ is extremal (Extremal element and its cut (Bourbaki–Witt)).