Order, Zorn's Lemma, and the Axiom of Choice: Examples and Counterexamples

Let

$\mathcal{F} = \{\, \{0,1\},\ \{1,2\},\ \{2,3\} \,\},$

a family of three nonempty sets of natural numbers. A choice function for $\mathcal{F}$ (Choice function) can be written down outright, by listing its three values:

$g(\{0,1\}) = 0, \qquad g(\{1,2\}) = 1, \qquad g(\{2,3\}) = 2.$

Nothing was assumed to produce it. Each value is one element taken from one set already known to be nonempty, and three such picks are made one after another. The induction of Every natural-number-indexed list of nonempty sets has a choice function on its family of values is exactly this process stated in general. That lemma indexes the family by a natural number rather than counting its members: writing the three sets as the values $F(0), F(1), F(2)$ of a function $F$ with domain $3 = \{0,1,2\}$ (The natural numbers $\mathbb{N}$ (von Neumann)), the successor step restricts $F$ to the shorter index set, takes a choice function for those values, and overwrites it with one further pair.

• Where an axiom would have been needed, and why it was not. Each pick is a single existential instantiation from a single nonempty set, licensed by first-order logic alone. Three of them are made, one at a time, and three is a natural number, so the process stops. What ZF does not supply is a choice function for every arbitrary family of nonempty sets. An infinite family can still have a choice function given by a defining rule — such as the minimum rule below — so the gap filled by the Axiom of Choice is arbitrary families, not mere infinitude.

• Choice functions are not unique. Taking the larger element of each pair gives another one, with values $1, 2, 3$; since each member has two elements there are $2 \cdot 2 \cdot 2 = 8$ choice functions for $\mathcal{F}$ in all. Nothing in the definition prefers one of them.

• The particular $g$ displayed above is the rule $S \mapsto \min S$, which happens to work for every nonempty set of natural numbers at once ($\min$ is a choice function on $\mathbb{N}$). That is a feature of $\mathbb{N}$, not of finiteness. The two ingredients come apart in Russell's shoes and socks, where the family is infinite and carries no such rule.

Every nonempty subset of $\mathbb{N}$ has a least element (The well-ordering principle), and that least element is unique, so

$\min : \mathcal{P}(\mathbb{N}) \setminus \{\emptyset\} \longrightarrow \mathbb{N}, \qquad \min S = \text{the least element of } S,$

is a well defined function, and $\min S \in S$ by construction. It is therefore a choice function on $\mathbb{N}$ (Choice function), given by a single rule and produced with no appeal to the Axiom of Choice.

What makes the choice free here is the structure of the order (Order on the natural numbers), not the size of the family. The order well-orders $\mathbb{N}$, and a well-order names a canonical element of every nonempty subset; how large the family of nonempty subsets is then does not matter.

• The rule, not the existence, is the point. [L1] gives a least element of each nonempty $S$ separately. Turning a family of separate existence statements into one function is exactly what the Axiom of Choice does in general, and it is exactly what is avoided here: uniqueness of the least element makes "the least element of $S$" a formula in $S$, so the graph of $\min$ is carved out by Separation from $\mathcal{F} \times \mathbb{N}$ with no further axiom.

• Every natural-number-indexed list of nonempty sets has a choice function on its family of values does not apply, and not for the reason usually given. That lemma carries no finiteness hypothesis at all, and it refuses that reading explicitly: it is stated over an indexed family, a natural number $n$ and a function $F$ with domain $n$ all of whose values are nonempty, and it gives a choice function for the family $F[n]$ of the values of $F$. What disqualifies $\mathcal{F} = \mathcal{P}(\mathbb{N}) \setminus \{\emptyset\}$ is that it is not $F[n]$ for any such $F$: sending each member of $F[n]$ to the least index at which $F$ takes it as a value injects $F[n]$ into $n$, the least index existing by [L1], whereas $\mathcal{F}$ already contains the $n + 1$ pairwise distinct singletons $\{0\}, \{1\}, \dots, \{n\}$, and no injection $\sigma(n) \to n$ exists (The pigeonhole principle on $\mathbb{N}$ ↗, which this library proves on a later page). Size is not what is at stake here, structure is, and Russell's shoes and socks is the contrasting case: a family of two element sets, with no listing of this kind and no rule either.

• The same construction works verbatim on any set carrying a well-order, with "least element" read in that order. Whether every arbitrary set carries a well-order is a different question, and answering it affirmatively is again a form of the Axiom of Choice. The library does prove it, but only from that axiom and only on a later page (The well-ordering theorem ↗); nothing in this example uses it, and no item on this page lists it as a dependency.

• Antisymmetry does the whole of the uniqueness work, and it is the only order axiom needed for it. This is the same one-line argument that makes $\sup$ legitimate notation in a poset (Upper bound, least upper bound, and strict upper bound).

Russell's illustration. Given infinitely many pairs of shoes and asked for one shoe from each pair, there is a rule: take the left shoe. It selects one member of every pair at once, it is written down once and for all, and it needs no axiom. Given infinitely many pairs of socks the rule is gone. The two socks of a pair are alike, nothing in the data distinguishes one of them, and the assertion that a function selecting one sock from each pair exists is an instance of the Axiom of Choice (The Axiom of Choice).

The difference is not about footwear. It is that the shoe family comes with a distinguished member in each pair, supplied in advance by the data, whereas a family of two element sets in general comes with nothing of the kind. Below, the shoe half is proved: a distinguishing set makes the choice function explicit, whatever the size of the family. The sock half is not proved here and is not provable here: it is the standard independence result that ZF alone, if consistent, does not prove that every countable family of two element sets has a choice function. The library records that result, with sources, as Fraenkel's socks: ZF does not prove choice for countably many pairs ‡, and does not prove it: it is established either by forcing, or by a permutation model of set theory with atoms together with a theorem transferring the conclusion to ZF, and this library develops neither.

• What is proved and what is quoted. Steps 1.1 to 3.1 are a complete ZF argument: a distinguishing set turns infinitely many choices into one formula. Step 5.1 rests on [A1], an external independence result. The honest reading is that the sock half is unavailable in ZF, not that it has been refuted here.

• Where [A1] sits in this library's record of unproved results. [A1] concerns countable families of two element sets, so it is the failure of a choice principle far weaker than the Axiom of Choice, and the library records it in its own right, with sources, as Fraenkel's socks: ZF does not prove choice for countably many pairs ‡. It is stronger than the bare independence of the Axiom of Choice: the Axiom of Choice implies choice for countable families of pairs, so any ZF proof of the Axiom of Choice would yield a ZF proof of that weaker principle, and [A1] denies the latter, so [A1] already gives Cohen 1963: ZF does not prove the Axiom of Choice ‡. Cohen's first model: an infinite Dedekind-finite set of reals ‡, that if ZF is consistent then so is ZF together with an infinite set of reals having no countably infinite subset, records a different failure of choice and is not what [A1] rests on. The standard Fraenkel-Mostowski "socks" model witnesses [A1] in ZFA, set theory with atoms, where the two socks of a pair are atoms and a permutation exchanging them is an automorphism; a permutation model is not a model of ZF, and the passage to ZF is supplied by the Jech-Sochor embedding theorem, whose role is recorded but not proved in Fraenkel's socks: ZF does not prove choice for countably many pairs ‡.

• Boundedly many pairs of socks are free. Whenever the pairs can be listed as the values $F(0), \dots, F(n-1)$ of a function $F$ with domain a natural number $n$, a choice function exists outright by Every natural-number-indexed list of nonempty sets has a choice function on its family of values, with the picks made one at a time. That lemma is stated over such an indexed family and deliberately does not say "finitely many." A finite set is defined later as one equinumerous with a natural number (Finite, countably infinite, countable, uncountable ↗); this example uses only the indexed-family statement and does not identify an arbitrary finite family with a particular enumeration. Russell's contrast is a genuinely infinite phenomenon, which is why he stated it for infinitely many pairs.

• The shoe argument never used that the pairs are pairwise disjoint, or that they are indexed by $\mathbb{N}$, or that they have two elements. All it used is that some formula picks out one element of each member, which is the general reason a concrete family can have an explicit choice function ($\min$ is a choice function on $\mathbb{N}$ is the same phenomenon with "least element" in place of "left shoe").

• Russell's own phrasing concerns a millionaire with denumerably many pairs of boots and of socks. "Shoes" is the usual modern retelling, and the mathematical content is unchanged: what matters is only that one member of each pair is singled out in advance.

For any set $X$, the power set $\mathcal{P}(X)$ ordered by inclusion is a poset (Partial order and partially ordered set) in which every $\subseteq$-chain $\mathcal{D}$ (Chain in a poset) has least upper bound

$\sup \mathcal{D} = \bigcup \mathcal{D} \in \mathcal{P}(X)$

(Upper bound, least upper bound, and strict upper bound). So $(\mathcal{P}(X), \subseteq)$ is chain-complete (Chain-complete poset), and its bottom element is $\bot = \sup \emptyset = \bigcup \emptyset = \emptyset$.

Both halves of "least upper bound" are checked below. Chain-completeness asks for the least one, not merely for some upper bound, and it is leastness that the Bourbaki–Witt argument consumes.

• The argument proves more than chain-completeness. Neither the construction of $U$ nor either of the two bound checks used that $\mathcal{D}$ is a chain, so every subset of $\mathcal{P}(X)$ has a supremum and $(\mathcal{P}(X), \subseteq)$ is a complete lattice. Chain-completeness is strictly weaker, and the posets to which Zorn's lemma is applied usually have only the weaker property (The chains of a poset, ordered by inclusion, form a chain-complete poset is the standard instance).

• Infima are present too: for nonempty $\mathcal{D}$ the greatest lower bound is $\bigcap \mathcal{D}$, and the greatest lower bound of the empty family is $X$, the top element. The class $\bigcap \emptyset$ is not a set, which is why the empty case is read inside $\mathcal{P}(X)$ rather than absolutely.

• The empty chain is not a technicality. It is what forces a chain-complete poset to have a least element at all, and here it produces $\emptyset$. A convention that excludes the empty chain has to reintroduce the same content as a separate nonemptiness hypothesis (Chain-complete poset records the reduction between the two conventions).

• Chain-completeness is not the same as having a top. Deleting the top element from $\mathcal{P}(\{1,2\})$ leaves the three-element poset of Two maximal elements and no greatest element, which is still chain-complete, since $\{1\}$ and $\{2\}$ are incomparable and so never lie in a common chain, yet it now has two maximal elements and no greatest one.

Let $(P, \le)$ be any poset and let

$\mathcal{C} = \{\, C \subseteq P : C \text{ is a chain of } P \,\}$

be the set of its chains (Chain in a poset), ordered by inclusion. Then $\mathcal{C}$ is chain-complete (Chain-complete poset): an inclusion chain $\mathcal{D} \subseteq \mathcal{C}$ has least upper bound $\bigcup \mathcal{D}$, which is again a chain of $P$ because any two of its elements lie in a common member of $\mathcal{D}$. Its bottom element is $\bot = \sup \emptyset = \emptyset$.

This is the poset that Zorn's lemma builds at its step 1.2 and declares chain-complete at its step 2.1, so what follows is that step worked out in full: the engine of Zorn's lemma, running on its own.

• This is the whole of Zorn's engine. Given a nonempty $P$ in which every chain has an upper bound and assuming no maximal element exists, every chain $C$ admits a strict upper bound; choosing one for each chain at once turns $C \mapsto C \cup \{\text{chosen strict upper bound}\}$ into a progressive map on $\mathcal{C}$, and Bourbaki-Witt applied to the chain-completeness proved here returns a chain equal to its own extension, which is absurd. That is Zorn's lemma, and the Axiom of Choice is used at exactly one point of it, the simultaneous choice of strict upper bounds, and nowhere in this example.

• $\mathcal{C}$ is chain-complete but usually not a complete lattice. An arbitrary union of chains need not be a chain: if $x, y \in P$ are incomparable then $\{x\}$ and $\{y\}$ are chains and $\{x, y\}$ is not, so the family $\{\{x\}, \{y\}\}$ has no supremum given by union. This is exactly the gap between this example and The power set is chain-complete, with union as supremum, and it is why chain-completeness rather than completeness is the right hypothesis for Bourbaki–Witt fixed point theorem.

• An immediate consequence, at the price of the Axiom of Choice. $\mathcal{C}$ is nonempty, since $\emptyset \in \mathcal{C}$, and every chain of $\mathcal{C}$ has an upper bound by the verification above. Assume in addition the Axiom of Choice (The Axiom of Choice), which Zorn's lemma assumes outright: Zorn's lemma then applies to $\mathcal{C}$ and yields a maximal element, so every poset has a maximal chain. This is the Hausdorff maximal principle, and it costs exactly one application of Zorn, hence the Axiom of Choice. The chain-completeness verified above costs nothing.

• The verification never used any property of $P$ beyond its being a poset. In particular $P$ may be empty, in which case $\mathcal{C} = \{\emptyset\}$ is the one-element poset.

Refuted claim: in every poset a maximal element is a greatest element, so that having nothing strictly above it forces an element to lie above everything (FALSE: every maximal element is a greatest element, Maximal element and greatest element).

The witness is

$P = \mathcal{P}(\{1,2\}) \setminus \{\{1,2\}\} = \{\, \emptyset,\ \{1\},\ \{2\} \,\},$

ordered by inclusion (Partial order and partially ordered set). Both $\{1\}$ and $\{2\}$ are maximal in $P$, neither is greatest, and $P$ has no greatest element at all.

• This witness is not the smallest one. The refutation in FALSE: every maximal element is a greatest element uses a two element antichain, which is minimal, but not for the reason one might expect: the empty poset satisfies the claim vacuously, having no maximal element at all, while a one element poset satisfies it outright, since its single element is maximal and is greatest by reflexivity. Two elements is therefore the least size at which the claim can fail, and it does fail there. Vacuous satisfaction is not confined to the empty poset, incidentally: $(\mathbb{N}, \le)$ has no maximal element either ($(\mathbb{N}, \le)$ has no maximal element: Zorn's chain hypothesis fails), and satisfies the claim for that reason. The witness here adds a least element $\emptyset$ below both maximal elements, which matters because it shows the failure is not caused by the poset splitting into unrelated pieces. Even a poset with a bottom, in which every element is comparable to something, can carry several maximal elements.

• The general pattern. Order the proper subsets of a set $X$ with at least two elements by inclusion. The maximal elements are exactly the sets $X \setminus \{x\}$ for $x \in X$: any proper $A \subsetneq X$ sits inside $X \setminus \{x\}$ for any $x \in X \setminus A$, and nothing lies strictly between $X \setminus \{x\}$ and $X$. Distinct points give distinct maximal elements, so there is one for each point of $X$, and there is no greatest element. The poset above is the case $X = \{1,2\}$.

• What would rescue the claim is totality. In a totally ordered set a maximal element is greatest, since every other element is comparable to it and cannot be strictly above it, which is why the confusion survives in intuition trained on $\mathbb{R}$.

• Maximality says nothing about comparability: here each maximal element is incomparable to the other, and both are above only $\emptyset$. Applications of Zorn's lemma must therefore be arranged so that "nothing is strictly above it" already means "it cannot be extended", since nothing stronger is available.

Refuted claim: the chain hypothesis of Zorn's lemma is redundant, that is every nonempty poset has a maximal element (Zorn's lemma, Maximal element and greatest element).

The witness is $(\mathbb{N}, \le)$ with its usual order (Order on the natural numbers). It is nonempty and has no maximal element whatsoever, and the hypothesis of Zorn's lemma that it violates is exactly one: $\mathbb{N}$ is itself a chain (Chain in a poset) and it has no upper bound in $\mathbb{N}$ (Upper bound, least upper bound, and strict upper bound).

• Nothing exotic is at work. The poset is totally ordered, it is the most familiar order there is, and it is even well ordered (The well-ordering principle). What it lacks is a ceiling. So the hypothesis Zorn's lemma really needs is boundedness of chains, and no amount of good behaviour elsewhere substitutes for it.

• It fails only at the top. Every chain of $\mathbb{N}$ that has an upper bound at all has a least one: the set of its upper bounds is a nonempty subset of $\mathbb{N}$, so The well-ordering principle hands back its least element. The empty chain has least upper bound $0$: it is vacuously an upper bound, and $0\le u$ for every natural $u$ because $0+u=u$ (Left identity for addition, Order on the natural numbers). So the only chains without suprema are the ones with no upper bound whatever, and $\mathbb{N}$ is one of them. The same observation, read as a statement about suprema rather than upper bounds, is A progressive map with no fixed point, on a poset that is not chain-complete.

• Nonemptiness is not what fails here, and how much work it does depends on the convention. Under the convention of Chain in a poset, where $\emptyset$ counts as a chain, "every chain has an upper bound" already forces $P \ne \emptyset$, since an upper bound of $\emptyset$ is just some element of $P$; the separate nonemptiness hypothesis of Zorn's lemma is then emphasis rather than extra strength. Under the competing convention, where "chain" means nonempty chain, the empty poset satisfies the chain hypothesis vacuously and has no maximal element, so nonemptiness must be assumed outright. Either way, what $(\mathbb{N}, \le)$ isolates is the failure of the chain hypothesis alone.

• Adding a single element $\infty$ above every natural number repairs everything: the chain $\mathbb{N}$ then has upper bound $\infty$, every chain has one, and $\infty$ is the maximal element Zorn's lemma promises.

Refuted claim: the chain-completeness hypothesis of the Bourbaki–Witt fixed point theorem is decoration, that is every progressive map $f : P \to P$ on a poset has a fixed point (Bourbaki–Witt fixed point theorem, Chain-complete poset).

The witness is $(\mathbb{N}, \le)$ (Order on the natural numbers) with the successor map $f(n) = \sigma(n) = n + 1$. It is progressive, and it has no fixed point at all. There is no conflict with Bourbaki–Witt, because $(\mathbb{N}, \le)$ is not chain-complete: $\mathbb{N}$ is a chain (Chain in a poset) with no upper bound in $\mathbb{N}$ ($(\mathbb{N}, \le)$ has no maximal element: Zorn's chain hypothesis fails), hence with no least upper bound (Upper bound, least upper bound, and strict upper bound).

• The failure is sharp, and it is a missing supremum. Adjoin one element $\infty$ above every natural number. The enlarged poset is chain-complete: a subset containing $\infty$ has supremum $\infty$, a subset of $\mathbb{N}$ with an upper bound in $\mathbb{N}$ has a least one by The well-ordering principle, a subset of $\mathbb{N}$ with none has supremum $\infty$, and the empty chain has supremum $0$. Extending $f$ by $f(\infty) = \infty$ keeps it progressive, and the fixed point Bourbaki-Witt promises is $\infty$, precisely the supremum that was missing. Any progressive map on the enlarged poset must fix $\infty$, since $\infty$ is greatest.

• Monotonicity is not the issue. The map $f(n) = \sigma(n)$ is order preserving as well as progressive: $\sigma(m) = m + \sigma(0)$ and $\sigma(n) = n + \sigma(0)$ by the Given, and adding a fixed natural number preserves $\le$ in both directions (Order is compatible with addition), so $m \le n$ gives $\sigma(m) \le \sigma(n)$. So this is not a case of a badly behaved map defeating the theorem; a perfectly well behaved map is defeated by the poset. Conversely Bourbaki–Witt fixed point theorem assumes no monotonicity at all, which is what lets Zorn's lemma apply it to a map built from an arbitrary choice function.

• No iteration argument could have worked. Starting at $0$ and iterating $f$ walks up $\mathbb{N}$ forever without converging, and the fixed point in Bourbaki-Witt is not reached by iterating: it is the supremum of the smallest set closed under $f$ and under suprema of its chains. When that supremum does not exist there is nothing to reach.

• This is the same defect as in $(\mathbb{N}, \le)$ has no maximal element: Zorn's chain hypothesis fails, read one notch higher up the scale of bounds. There the chain $\mathbb{N}$ had no upper bound, which is what Zorn's lemma asks of every chain; here the same chain has no least upper bound, which is what Bourbaki–Witt fixed point theorem asks of every chain through chain-completeness. A least upper bound is in particular an upper bound, so the first failure implies the second, and adjoining one top element repairs both at once.