The choice nobody can write down

Four pairs, and one thing to be taken from each. There are sixteen ways to do it, and if the two members of a pair can be told apart there is a rule that names one of the sixteen without anybody deciding anything.

Now suppose the two members of each pair are indistinguishable: two things, genuinely two, with nothing said about either that is not said about the other. There are still sixteen ways, and no rule names one.

For four pairs, four decisions can be made — write them down, and the writing is the choice. The axiom of choice is the assertion that this works for infinitely many pairs, where the writing cannot be finished.

Russell’s illustration, and why it is exactly right #

Russell put it as shoes and socks. Given infinitely many pairs of shoes, a choice function exists and is describable: take the left shoe of each. Given infinitely many pairs of socks, with nothing distinguishing the two socks of a pair, there is no such description — and whether a choice function exists anyway is not settled by the other axioms of set theory.

The point of the illustration is that the difficulty is not about infinity as such. A choice function on infinitely many pairs of shoes needs no axiom, because a rule can be stated once and applied to every pair at once. What needs the axiom is the absence of a rule, and infinity is what makes the absence bite: with finitely many pairs, “no rule” is repaired by listing, and a list is a rule.

So the axiom’s content is precisely: for a family with no describable choice, a choice function exists anyway. It asserts existence without any means of exhibition, and everything strange about its consequences comes from that clause.

Zorn’s lemma, drawn where drawing works #

The axiom is almost never used in the form above. Its working version is Zorn’s lemma, which says: if every chain in a partially ordered set has an upper bound in the set, then the set has a maximal element.

For a finite order the statement is a triviality, and drawing it is worth doing because it shows what the hypothesis is for.

In the finite case the proof is: start anywhere, and if something is above the current element move up to it. The process must stop, because the order is finite and nothing can be visited twice. Where it stops is maximal.

For an infinite order the process need not stop, and the hypothesis about chains is what replaces “must stop”. Having climbed through an increasing sequence of elements, the chain hypothesis supplies something above all of them, and the climb continues past the sequence — through the ordinals, which is exactly what they were built for. The axiom of choice is what licenses the climb: at each stage something above must be chosen, and the choices are indexed by an ordinal rather than by a finite list.

The climb through the ordinals, in outline #

The proof that choice implies Zorn’s lemma is worth sketching, because it is where the axiom is actually spent and because it explains why the finite argument does not simply extend.

Start with an element. If it is not maximal, something is strictly above it; choose one. If that is not maximal, choose again. After all the finite steps, the elements chosen form a chain, so by hypothesis it has an upper bound; take one, and carry on. After all of those, take another upper bound. And so on, indexed by the ordinals rather than by the whole numbers.

The process must halt, and the reason is a counting argument rather than a geometric one: if it never halted, it would produce a strictly increasing family indexed by every ordinal, and there are more ordinals than there are elements of any set. So at some stage nothing is strictly above, and that stage is a maximal element.

Two things are needed and they are different. The chain hypothesis supplies something at each limit stage. The axiom of choice supplies a way of picking one such thing at every stage at once, in advance, so that the recursion is a single well-defined construction rather than a sequence of unmade decisions. Without the axiom the climb has no definition, because “choose one” at uncountably many stages is not a rule.

A sequence that explodes and still stops runs a climb of the same kind for a different purpose — a descending sequence of ordinals must terminate, which is the mirror image of the argument above.

Three statements that are the same statement #

Zorn’s lemma, the axiom of choice and the well-ordering theorem are equivalent over the rest of set theory, and the equivalence is not obvious in any direction.

The well-ordering theorem says every set can be given an order in which every non-empty subset has a least element. For the whole numbers this is the usual order. For the rationals it is not the usual order — there is no least positive rational — but a well-ordering exists and can be described: every fraction exactly once enumerates the rationals, and an enumeration is a well-ordering, since the least element of a subset is the one appearing earliest.

It is worth putting beside a theorem about infinite sets that pointedly does not need any of this.

Two injections make a bijection proves that two sets each injecting into the other are the same size, and the proof builds the bijection explicitly by cutting both sets into chains and matching along them. The contrast with the well-ordering theorem is exactly the contrast this essay is about: one theorem about infinite sets hands over a construction, and the other hands over a promise.

For the real numbers no well-ordering has ever been described, and none can be: it is consistent with set theory without choice that none exists. So the well-ordering theorem asserts the existence of an object that provably cannot be exhibited.

That is the sharpest form of the axiom’s character, and it is why Zermelo’s 1904 proof of the theorem caused an uproar rather than satisfaction. Several mathematicians who had used choice-like reasoning without noticing objected to the theorem while continuing to use the axiom in other guises — Borel and Lebesgue among them, which is not a criticism so much as evidence for how invisible the principle is until it is named.

Where it hides #

Once named, the axiom turns up in places where nobody had thought a decision was being made.

A surjection has a right inverse. If $f$ maps $A$ onto $B$, choose for each $b$ some preimage. That is a choice function on the family of preimage sets, and there is generally no rule.

A countable union of countable sets is countable. Each of the sets has an enumeration; to build one for the union, an enumeration must be chosen for each. Without choice this statement can fail — there are models of set theory in which the reals are a countable union of countable sets, which is not a contradiction but is thoroughly disorienting.

Every vector space has a basis. Zorn’s lemma applied to the partial order of linearly independent subsets. For finite-dimensional spaces this is a construction; for the reals as a vector space over the rationals it is an existence claim about an object nobody can name.

König’s lemma — an infinite tree has an infinite path — needs a weak form of choice when the tree’s branching is infinite: at each level one of infinitely many children must be picked. For a finitely branching tree the choice can be made by a rule if the children are ordered, which is why the version used in that essay is the safe one.

The weaker versions, which are what most of analysis needs #

The axiom comes in strengths, and the distinction matters because the strong version is what carries the unwelcome consequences.

Finite choice — a choice function on finitely many non-empty sets — is a theorem, not an axiom. It follows by induction from the fact that a non-empty set has an element, and the tables at the top of this essay are that theorem for four sets.

Countable choice allows a choice function on countably many sets. It is enough for most of elementary analysis: that a sequentially continuous function is continuous, that a countable union of countable sets is countable, that every infinite set has a countably infinite subset.

Dependent choice allows building an infinite sequence where each term is chosen after seeing the previous one. It is what recursive constructions need and it implies countable choice.

Full choice allows a choice function on any family whatever. It implies the three above and nothing above it implies it.

The gradation is the reason Solovay’s model works. Dropping to dependent choice keeps essentially all of analysis and removes the non-measurable sets, so the price of Banach–Tarski is paid for something that is used elsewhere — chiefly in algebra, where the maximal ideal theorem and the existence of bases genuinely need the full strength.

What it costs #

The axiom’s most-discussed consequence is the Banach–Tarski paradox: a solid ball can be cut into five pieces and reassembled, by rigid motions alone, into two balls each the same size as the original.

Nothing about that is a trick with limits or a sleight of hand about volume. The pieces are genuine subsets and the motions are genuine rotations and translations. What the pieces are not is measurable — they have no volume, not even zero, so there is no volume to be conserved and no contradiction to derive.

Such sets exist because of choice. Vitali’s construction, which is much simpler, is the standard example: partition $[0,1]$ into classes by “differ by a rational”, choose one representative from each class, and the resulting set cannot be assigned a length consistently with translation invariance and countable additivity. The choice is exactly the axiom, and the family of classes has no describable representative.

Almost none of it left, and still uncountably many builds a set of measure zero explicitly, by a rule. The contrast is instructive: an explicit construction gives a set whose measure can be computed, and the axiom gives a set whose measure does not exist.

Solovay showed in 1970 that this is unavoidable. There is a model of set theory without full choice — with a weaker version, dependent choice, which is enough for most of analysis — in which every subset of the reals is measurable. So the pathological sets are not discovered; they are admitted, and admitting them is the price of the axiom.

One theorem, two strengths #

The gradation above runs from finite choice up to full choice, and it leaves out the rung that calibrates the scale most precisely. There is a principle strictly between countable choice and the full axiom, and one famous theorem sits on both sides of it depending on a hypothesis nobody would expect to matter.

The principle is the ultrafilter lemma: every filter on a set extends to a maximal one. In algebraic dress it is the statement that every proper ideal of a Boolean ring lies inside a prime one, and it is one of the standard consequences of Zorn’s lemma — proved by the climb of the section above, applied to the order of filters.

It does not imply full choice, which was shown in 1971 and is a genuinely hard result: there is a model of set theory in which every filter extends and some family of pairs still has no choice function. So it names a strength, and the strength is intermediate.

The theorem that straddles it is Tychonoff’s, which says a product of compact spaces is compact however many factors there are. In full generality that statement is equivalent to the axiom of choice — Kelley proved it in 1950, and the proof is a small shock, since compactness looks like a statement about coverings and choice looks like a statement about picking. Restrict the factors to be Hausdorff, which excludes almost nothing anybody uses, and the theorem drops to being equivalent to the ultrafilter lemma instead.

One theorem, two hypotheses, two axiom strengths. The difference between them is whether the spaces can have points that no open set separates, and that difference is exactly the difference between needing to pick an element and needing only to extend a filter. Nothing about the statement announces which version is being used, which is the essay’s standing point about how invisible the principle is.

And the paradox does not go away at this level. Dropping from full choice to the ultrafilter lemma keeps the Hahn–Banach theorem, and the Banach–Tarski decomposition follows from Hahn–Banach — a result of Pawlikowski’s from 1991, and an unwelcome one. So a reader hoping to keep the useful consequences and shed the alarming one by weakening slightly is out of luck: the ball still comes apart.

Solovay’s model is therefore not a mild retreat. It goes all the way down to dependent choice, abandoning the ultrafilter lemma along with everything above it, and what it buys — every set of reals measurable — costs the maximal ideal theorem, bases for arbitrary vector spaces, and Hahn–Banach in the generality functional analysis uses.

Which is the honest shape of the trade. The strengths form a genuine hierarchy, several of them are known to be strictly separated, and the pathologies do not sit at the top. They begin well below it, and the only place they are absent is far enough down that a good deal of ordinary mathematics is absent too.

Where it stands #

Gödel showed in 1938 that adding the axiom of choice to set theory cannot introduce a contradiction that was not there already. Cohen showed in 1963 that its negation cannot either. So it is independent: neither provable nor refutable from the other axioms, in the same sense that two worlds that both obey the rules shows the parallel postulate independent of Euclid’s others.

Cohen’s method — forcing — was invented for the question and is now the standard tool for independence in set theory. The comparison with geometry is exact in structure and quite different in reception: after 1868 nobody argued about whether the parallel postulate was true, because both geometries turned out to describe something. There is no comparable settlement here, and working mathematicians take the axiom as a matter of practice rather than conviction.

The practice is nearly unanimous. Almost all of analysis, algebra and topology as normally presented assumes it, usually through Zorn’s lemma and usually without remark. The places where it is avoided deliberately are the places where the object is wanted explicitly rather than abstractly — constructive mathematics, where the middle that is not excluded applies the same scepticism to a different principle, and computability, where an object that cannot be exhibited is not an object.

What the pictures cannot show #

Everything drawn here is finite, and everything difficult about the axiom is infinite. The sixteen choice functions can be listed; the point of the axiom is the family whose choice functions cannot. The forty-two chains of a nine-element order can be enumerated; the point of Zorn’s lemma is the order where they cannot.

So the figures illustrate the statement and can never illustrate the content. That is not a limitation of these particular drawings but of drawing: the axiom’s whole subject is what happens beyond any finite listing, and a finite listing is what a page is.

The indistinguishable pairs are drawn with subscripts, which distinguishes them. There is no way around this either — two things drawn on a page are at different places, and being at different places is a difference. The socks in the figure are labelled $a_1$ and $a_2$ and the caption says the labels are not available to the rule, which is an instruction to the reader rather than a property of the picture.

The ladder from here #

Below: two injections make a bijection, a theorem about infinite sets that pointedly does not need choice, and an infinite tree has an infinite path, which needs a weak form of it. Sideways: two worlds that both obey the rules, independence demonstrated by exhibiting two models, and a list that cannot contain itself, the argument that made set theory need axioms at all. Above: the well-ordering theorem, transfinite recursion, the Banach–Tarski construction, dependent choice and the countable axiom of choice, and Solovay’s model.

What is worth carrying away #

The axiom asserts that something exists and supplies no way to point at it. That is unusual: most existence theorems in mathematics either exhibit the thing or give a procedure that would.

Whether that is objectionable depends on what existence is taken to mean, and the century of argument about it has not converged. What has converged is the practice, and the reason is worth stating plainly: the axiom is used because the theorems it gives are the ones that make the subjects work, and a mathematics without bases for every vector space, maximal ideals in every ring or products of non-empty sets being non-empty is a mathematics in which the standard theorems acquire hypotheses nobody wants to carry.

The bill comes as a ball cut into five pieces. Most people decide that is a fair price and stop thinking about it, which is a defensible position and worth knowing is a position rather than a fact.