The choice inside a countable union

The choice nobody can write down introduced the axiom of choice through Russell’s pairs of shoes and socks, and listed some of the places it hides. One of those places was dismissed in a sentence: a countable union of countable sets is countable, which “needs an enumeration chosen for each set”. This essay takes that sentence apart, because it is the place where most mathematicians first use the axiom of choice without noticing, and because the consequences of removing it are stranger than almost anywhere else.

The theorem is used constantly. It is how one proves that the rational numbers are countable, that the algebraic numbers are countable, that a countable union of sets of measure nought has measure nought, and that the first uncountable ordinal cannot be reached by countably many steps. Its proof is one of the first infinite arguments a student sees. The question here is exactly what that proof assumes, when the assumption can be avoided, and what the world looks like when it cannot.

The diagonal walk #

Let $A_1, A_2, A_3, \dots$ be countable sets. “Countable” means that each can be listed: there is a sequence $a_{n,1}, a_{n,2}, a_{n,3}, \dots$ running through all the members of $A_n$. Arrange the listings as the rows of an infinite grid and number the cells along the diagonals: first the cell in row 1, column 1; then row 2 column 1 and row 1 column 2; then the third diagonal, and so on. Every cell is reached after finitely many steps — the cell in row $n$ and column $m$ is reached at step

$$\tfrac12(n + m - 2)(n + m - 1) + m,$$

Cantor’s pairing formula, which the figure checks against its inverse for the first five hundred cells. Walking the grid and skipping members already seen lists the union. It is the same walk more things than boxes used to show that the rationals are countable, and it is completely explicit.

Except at one point. The walk needs the rows to be listings: the grid’s cell in row $n$, column $m$ is “the $m$-th member of $A_n$”, which makes no sense until a listing of $A_n$ has been fixed. The hypothesis says only that each $A_n$ can be listed. It does not say how, and a countable infinite set has uncountably many different listings. The proof silently picks one for every row.

One choice per row, infinitely many rows #

The number of choices involved is easy to underestimate.

For a single set, choosing a listing is harmless: the hypothesis says a listing exists, and “let $f$ be one” is ordinary logic, needing no axiom. For finitely many sets it is still harmless — choose one, then the next, finitely many times. The trouble is the infinite case. The walk needs a single object, a function assigning to every $n$ a listing of $A_n$, and the existence of each listing separately does not, by any finite argument, produce such a function. That function is a choice function on the family of sets of listings, one set for each $n$, and its existence for every countable family of non-empty sets is precisely the principle called countable choice.

It is worth being exact about why the finite case is innocent and the infinite one is not. A proof is a finite object. To choose a listing for $A_1$, a proof writes “let $f_1$ be a listing of $A_1$”, which is justified by the hypothesis that one exists; to choose for $A_2$ it writes another line; and so on. For any fixed number of rows the proof is finitely long. For all the rows at once it would be infinitely long, and the axiom of choice is the device that replaces the infinitely long proof by a single line — “let $f$ be a function choosing a listing for every $n$”. Whether that line is legitimate is not something the other axioms decide, which is the content of the independence results of Gödel and Cohen described in two worlds that both obey the rules: set theory with choice and set theory without it are both consistent if either is.

This is the pattern infinitely many guessers, finitely many wrong exploited in reverse: there, choosing a representative of each class of infinite sequences produced a strategy nobody could carry out; here, choosing a listing of each set produces a proof that looks as concrete as a proof can be. The concreteness is real for every row taken alone and an illusion for all of them together.

When the listings come for free #

Many unions need no choice at all, because their sets arrive with listings attached. The real algebraic numbers are the standard example.

Group the polynomials with whole coefficients by a height: the degree plus the sum of the sizes of the coefficients. For each height there are finitely many polynomials and so finitely many roots, and the real ones can be listed from left to right, a rule that involves no choice. Listing height by height, and left to right within each height, numbers every real algebraic number. That is Cantor’s argument of 1874, the first proof that the algebraic numbers are countable, and it is a countable union of finite sets each with a canonical order. The figure computes the first few heights, removing roots already met at smaller heights, and finds 1, 2, 4, 12, 28 and 72 new numbers.

The general lesson is that the theorem needs choice only for its generality. A union of countably many countable sets with specified listings is countable in plain set theory; so is a union of sets that are subsets of a fixed set with a fixed order, like the rationals or the algebraic numbers, because the order supplies the listings. What needs choice is the statement for arbitrary countable sets, given only the knowledge that each can be listed.

Pairs of socks #

The extreme case is the weakest-looking one: countably many sets of two members each.

A two-element set has exactly two listings. Choosing one is choosing which member comes first, and for shoes there is a rule: left before right. For socks there is none. To list the union of countably many pairs of socks, one has to decide, for every pair, which sock is first — countably many independent binary choices — and without the axiom of choice it is consistent that this cannot be done. In such a world the union of the socks is a set that is infinite and has no countably infinite subset: it cannot be finite, since it has a pair for every natural number, but any list of infinitely many of its members would pick out a first sock in infinitely many of the pairs, and the world in question is built so that not even infinitely many of them can be chosen from.

Sets of that kind are called Dedekind-finite. They are as large as any finite set and admit no one-to-one map onto a proper part of themselves; they are infinite without being infinite in the way that the natural numbers are. In ordinary mathematics, with choice assumed, they do not exist. Without it, a countable union of pairs can be one.

How little choice suffices, and how much is too little #

Between full choice and none lies a scale of weaker principles, and the countable union theorem has a definite place on it.

Countable choice — every countable family of non-empty sets has a choice function — proves the union theorem by choosing the listings. The union theorem, in turn, proves countable choice for pairs: given countably many pairs, list their union, and choose from each pair the member that appears first in the list. None of these implications reverses, and each strict gap is witnessed by a model of set theory built for the purpose. The union theorem is therefore strictly weaker than countable choice and strictly stronger than the socks principle; it is a precise amount of choice.

At the bottom of the scale sits the most startling model. Solomon Feferman and Azriel Lévy showed in 1963 that it is consistent with the other axioms of set theory for the set of real numbers to be a countable union of countable sets. Cantor proved the reals uncountable, and that proof uses no choice, so in Feferman and Lévy’s world the reals remain uncountable — and are nevertheless the union of countably many sets each of which can be listed. There is no contradiction: each set can be listed, but no single function lists them all, and so the diagonal walk never gets started. What counting can prove exists noted one consequence: in that world every set of reals is a Borel set, because the reals are too fragmented for the constructions that produce non-Borel sets.

Where the theorem is quietly used #

The union theorem is not a curiosity at the edge of set theory; it holds up large parts of analysis, and following it shows where the choice travels.

In measure theory, a countable union of sets of measure nought has measure nought: cover the $n$-th set by intervals of total length $\varepsilon/2^n$, and the union by all of them. The argument chooses a cover for each set — infinitely many choices — and covering a set from outside used exactly this step. In Feferman and Lévy’s world it fails dramatically: the whole real line is a countable union of countable sets, each of measure nought, so either Lebesgue measure is not countably additive or the line has measure nought, and the usual theory of almost none of it left, and still uncountably many does not survive unchanged.

In the theory of ordinals, the first uncountable ordinal $\omega_1$ cannot be reached as the limit of a countable sequence of countable ordinals. Reached from below or not at all proved this, and the proof is the union theorem: a countable limit of countable ordinals is a countable union of countable sets, hence countable, hence below $\omega_1$. Without choice the argument collapses, and in Feferman and Lévy’s world $\omega_1$ is such a limit — the first uncountable ordinal can be approached in countably many steps. The theory of Borel sets, whose hierarchy is built by transfinite recursion up to $\omega_1$, depends on this fact and falls with it; that is why every set of reals is Borel in that world.

In elementary analysis, the statement that a function continuous along sequences is continuous needs countable choice, and so does the statement that every infinite set has a countably infinite subset. Countable and everywhere relied on several such steps without needing to name them. The union theorem sits among these, one of a family of innocuous-looking statements each of which costs a definite amount of choice.

In topology, the Baire category theorem — a complete metric space is not a countable union of nowhere dense sets — has a proof that looks like the union theorem’s and needs more. It picks a ball avoiding the first set, then a smaller ball inside it avoiding the second, and so on, each choice made after the previous one and depending on it. That is not one choice for each of countably many sets laid out in advance, but a sequence of choices each of which can see the last: the principle of dependent choice, strictly stronger than countable choice and strictly weaker than the full axiom. Charles Blair showed in 1977 that, over the other axioms, the Baire category theorem for complete metric spaces is equivalent to dependent choice. So two of the most used countable arguments in analysis — that a countable union of small sets is small, measured by length, and that it is small, measured by category — rest on two different levels of the same scale of choice principles.

The constructive reading #

There is a school of mathematics in which the theorem needs no choice at all, because “countable” means something stronger. In constructive mathematics, in the tradition of Errett Bishop, to say a set is countable is to give a listing of it, and a proof that a family of sets is countable must provide a rule producing a listing of each. With that reading the union theorem is immediate: the rule that lists each set, combined with the diagonal walk, lists the union. The choice has been moved into the hypothesis, where it is no longer a choice but a piece of data.

That reading also explains why constructive mathematicians are untroubled by the socks. A pair of socks, constructively, is a pair together with whatever information the problem supplies about it; if nothing distinguishes the socks, then nothing can be proved that requires distinguishing them, and the question of listing their union simply does not arise as a theorem. The proof that says which half showed the same discipline for disjunctions. Classical mathematics, which proves existence without construction, needs the axiom of choice to license the step; constructive mathematics, which never proves existence without construction, never takes it. The countable union is where the two styles part most visibly, over an argument both accept for every example anyone can write down.

What the pictures can and cannot show #

The figures show finitely much of the grid and finitely many heights of algebraic numbers, and on those finite parts no choice is ever needed. That is not a weakness of the pictures but the whole point: choice is needed only for infinitely many simultaneous decisions, and no picture contains infinitely many of anything. The listing of algebraic numbers by height is drawn to six heights; that it continues forever, by the same rule, is what makes it choice-free. The counts themselves are found numerically — roots computed in floating point and identified when they agree to six decimal places — which is safe at these heights, where distinct algebraic numbers of small degree and small coefficients are far further apart than that, and would need exact arithmetic much further out.

The socks are drawn with two identical shapes side by side, and the drawing cannot avoid distinguishing them — one is on the left. A drawing is always a choice of positions, which is exactly what the socks lack. The figure of principles states implications and their failures but cannot show the models that make the failures possible; those are constructions by forcing and by permutation models, which build worlds of set theory in which particular choice functions are missing, and they are beyond what a diagram can carry.

Still open: which weak choices are equivalent to which #

The chain drawn is a line, and the true picture is a tangled order of hundreds of choice principles, many of them related to countable unions. Paul Howard and Jean Rubin’s catalogue of consequences of the axiom of choice records the known implications and non-implications between them and leaves many cells of its vast table unresolved: for numerous pairs of weak principles it is not known whether one implies the other. Some of those questions concern exactly the statements here — for instance, how the union theorem for countable unions of finite sets of bounded size relates to choice principles for families of sets of that size — and they are settled family by family rather than by any general method.

There is also a question about strength in analysis. The union theorem is what makes Lebesgue measure countably additive in the usual development, and in Feferman and Lévy’s world measure theory as normally practised breaks down. How much of analysis survives on countable choice alone, how much needs dependent choice, and how much of what analysts assume needs no choice at all is mapped in outline by the work on constructive and choice-free analysis, and the boundary is still being drawn.

A proof with an invisible step #

The diagonal walk is one of the most transparent arguments in mathematics, and the choice in it is invisible because every individual piece of it is concrete. Every row can be listed. Every cell gets a number. The single step that is not concrete is the decision to list all the rows at once, made in the space between “each $A_n$ is countable” and “let $a_{n,m}$ be the $m$-th member of $A_n$”.

Removing that step does not merely weaken the theorem; it lets the real numbers come apart into countably many countable pieces that cannot be reassembled into a list, and it lets countably many pairs of socks form an infinite set too shapeless to count. The axiom of choice is often defended as obvious, and the countable union is the case that best explains why: the alternative is a world in which a two-line proof everyone believes is false, and the reason is that nobody said which sock comes first.