What counting can prove exists

The size that cannot be pinned down showed that the infinities form a tower with no top: every collection has more sub-collections than members. It spent itself on the one question about the tower that has no answer. This essay uses the tower for what it is good at, which is proving that things exist.

The method is old and it is blunt. If a whole collection is larger than some part of it, the rest of the collection is not empty. Georg Cantor used it in 1874, in the paper that began the theory of infinite sizes, to prove that transcendental numbers exist — numbers that solve no polynomial equation with whole-number coefficients — by showing that there are more real numbers than algebraic ones. The same argument, applied to other collections, proves the existence of a great many strange objects at once. And applied to one particular collection it fails, instructively.

The figure sorts familiar collections into three sizes. At the bottom, $\aleph_0$, the collections that can be listed. In the middle, $2^{\aleph_0}$, the size of the line. At the top, $2^{2^{\aleph_0}}$, the size of the collection of all sets of real numbers. Each placement is a counting argument, and the existence proofs are the gaps between the tiers.

More reals than definitions #

The simplest gap is between the bottom tier and the middle one.

Countable and everywhere listed the algebraic numbers: each is a root of a polynomial with whole-number coefficients, the polynomials can be listed by the size of their coefficients, and each has finitely many roots. The real numbers cannot be listed, by the row that is not on the list. So most real numbers are transcendental. Joseph Liouville had exhibited transcendental numbers thirty years earlier, numbers approached too fast by fractions to be algebraic, but only a few, with special shapes; Cantor’s argument says that almost every number is one, and says nothing about any particular number.

The same comparison says more. Every definition of a number — “the ratio of a circle’s circumference to its diameter”, “the smallest positive root of $x^5 - x - 1$” — is a finite string of symbols from a finite alphabet, and the figure shows how to list all such strings: by length, then alphabetically. Each length contributes finitely many, so the list reaches every string eventually. The numbers that have definitions are therefore countably many, and almost every real number has no definition at all, in English or in any other finite language.

That statement needs one caution, and it is exactly the one that the word that cannot describe itself is about. “Definable” is not itself a notion that can be defined in the language whose definitions it counts — trying produces Richard’s paradox, a definition of “the first number not definable in fewer than a hundred words”. The counting argument is sound when it is made from outside the language, about a language whose sentences it can list. It does not produce a definition of an undefinable number, which would be a contradiction; it proves that such numbers exist while making sure never to name one.

A continuous function is a countable list #

The next gap is between the middle tier and the top.

A function from the reals to the reals is an arbitrary assignment of a value to every point, and there are as many of them as there are sets of reals — the top tier. A continuous function is far more constrained: it is determined by its values at the fractions. If two continuous functions agreed at every fraction but differed at some point, their difference would be continuous, non-zero at that point and therefore non-zero on a whole interval around it — which contains fractions, where the difference is nought. The figure shows the constraint at work: broken lines through the values at the fractions with larger and larger denominators close on the curve, and the gap between them and the curve shrinks to nothing.

So a continuous function is a list of numbers indexed by the fractions, and there are as many such lists as there are sequences of reals. A sequence of reals is as good as a single real — a line has as many points as a square, and the same interleaving works for infinitely many coordinates — so the continuous functions are exactly as numerous as the points of a line. Most functions are discontinuous, and not by a little: the continuous ones form a middle-tier sliver of a top-tier collection.

This is the pattern of every argument in this essay. A class of objects is well-behaved exactly when a countable amount of information determines each member, and then the class is no larger than the line. Everything outside it is the price of that economy.

Only as many Borel sets as points #

The sets of reals that analysis actually uses — open sets, closed sets, and everything built from them by complements and countable unions — are called the Borel sets, and the same argument applies to them.

An open set is a union of countably many intervals with fractional ends, so it is fixed by a countable list, and there are as many open sets as points. A closed set is the complement of an open one: the same number. A countable union of closed sets is fixed by a sequence of closed sets: still the same number. The construction continues through a hierarchy of levels, one for each countable ordinal, and at each level the count stays at the size of the line; the levels number $\aleph_1$, which is at most the size of the line; so there are only as many Borel sets as there are points, and almost every set of reals is not Borel.

Here, unlike for transcendental numbers, the existence proof was followed by examples, and the examples are more interesting than the count. Nikolai Lusin and Mikhail Suslin found in 1917 that the shadow of a Borel set in the plane — its projection onto a line — need not be Borel. Henri Lebesgue had claimed in 1905 that it always was, and Suslin, then a student, found the error. The sets that arise as such shadows, the analytic sets, sit just above the Borel sets, and closed sets obey the continuum hypothesis returns to them.

A second notion of most #

Counting separates the tiers and is blind inside one. The continuous functions all sit in the middle tier, and among them the differentiable ones are as numerous as the rest — both collections have the size of the line — so counting cannot say whether a typical continuous function has a slope.

A different measure of “most” can. Call a collection of continuous functions meagre if it is a countable union of sets that are nowhere dense — sets whose closure contains no open ball of functions, measuring distance between functions by the largest gap between their graphs. René Baire proved in 1899 that the whole space of continuous functions is not meagre, so a meagre collection is small in a sense that counting cannot see. Stefan Banach and Stefan Mazurkiewicz proved in 1931 that the continuous functions with a derivative at even one point form a meagre collection. In the sense of category, almost every continuous function has a slope nowhere — the behaviour of the curve with a corner at every point, which Weierstrass exhibited in 1872 and which was received as a pathology, is the typical case.

The two notions of size answer different questions. Counting compares collections that differ in how much information pins down their members; category compares sub-collections of one space by how thinly they are spread. Neither sees what the other sees, and each is the right tool exactly where the other is blind. What both share with counting’s existence proofs is the absence of an example: the category argument proves that nowhere-differentiable functions are typical, and the only ones anyone can write down are the special constructions like Weierstrass’s.

The count that does not help #

Now apply the method to the sets of reals that have a length — the Lebesgue-measurable sets — and ask whether it proves that a set without a length exists.

It does not, and the reason is a single set.

The middle-thirds set is what is left of the interval after removing the open middle third, then the middle thirds of the two pieces that remain, and so on. Its total length is $(2/3)^k$ after $k$ stages, which goes to nothing, so it has length nought. But its points are the numbers whose base-three digits are all $0$ or $2$, one for every infinite sequence of two choices — as many as the points of the line.

Every subset of a set of length nought has length nought, and is therefore measurable. The middle-thirds set has as many subsets as the line has — $2^{2^{\aleph_0}}$ — and every one of them is measurable. The measurable sets are as numerous as all sets, and the counting argument has nothing to push against. There is no gap between the tiers for a non-measurable set to fall into.

What the axioms force, and what they allow #

The failure of the count is not a failure of cleverness. It reflects the fact that the existence of a non-measurable set is not a consequence of the ordinary axioms without the axiom of choice.

A set that has no size at all built one, Giuseppe Vitali’s set of 1905, by choosing one point from each class of reals that differ by a fraction. The choice is essential. Robert Solovay proved in 1970 that if the axioms are consistent together with a large-cardinal assumption, they remain consistent when the axiom of choice is weakened to the form that ordinary analysis needs and the statement that every set of reals is measurable is added. In that world there is no Vitali set; every set of reals has a length.

Compare the Borel sets. Their counting argument needs a little choice too — picking one enumeration from each of countably many collections — but only the weak form that ordinary analysis uses everywhere, and that form holds in Solovay’s world as well. So in Solovay’s world there are non-Borel sets and there are no non-measurable ones. Without even the weak form strange things happen: Solomon Feferman and Azriel Lévy showed in 1963 that it is consistent with the other axioms for the real numbers to be a countable union of countable sets, and then every set of reals is Borel. The difference between the two cases is visible in the figure above: the measurable sets fill the top tier, and the Borel sets fill only the middle one. Counting proves existence exactly when the well-behaved class is smaller than the whole, and when it is not, existence has to come from somewhere else — here, from the full axiom of choice, which can be doubted.

The same argument with finite numbers #

The method does not need infinity, and its most consequential use has none.

A Boolean function of $n$ inputs assigns true or false to each of the $2^n$ rows of a truth table, and one connective is enough to build every such function as a circuit of gates. How many gates are needed? Claude Shannon counted in 1949. There are $2^{2^n}$ Boolean functions of $n$ inputs. A circuit of $s$ gates is described by saying, for every one of its gates, which two earlier wires it reads — about $s^2$ choices each — so there are at most about $s^{2s}$ circuits of $s$ gates. For those circuits to compute every function, $s^{2s}$ must reach $2^{2^n}$, which forces $s$ to be at least about $2^n/n$. Almost every Boolean function needs a circuit exponentially large in the number of its inputs.

It is exactly the argument of this essay: a well-behaved class — functions with small circuits — is fixed by a small amount of information, so it is small, and most of the whole collection lies outside it. And it has exactly the same weakness. Nobody can exhibit a specific function, defined by a short rule, that is proved to need even a circuit of five times $n$ gates. The problem of proving any such lower bound for an explicit function is the heart of the question whether problems whose solutions are easy to check are also easy to solve, and after seventy years the counting argument still proves the only exponential bounds there are, for functions nobody can name.

What the tiers cannot show #

Nothing infinite is drawn. The tiers are labels, the listing of words shows its first thirty entries, the broken lines use four denominators and the middle-thirds set is drawn to its sixth stage. What the figures compute are the finite shadows the arguments rest on: that each word length contributes finitely many words, that the gaps between the broken lines and the curve shrink, that the middle-thirds set’s length at stage $k$ is $(2/3)^k$.

No undefinable number is shown, and none could be. The argument that they exist is a comparison of sizes made from outside the language; exhibiting one would require a definition of it, which is exactly what it lacks.

The Borel hierarchy’s length is stated, not derived. That the construction closes after $\aleph_1$ levels is the standard argument about countable families in a well-ordered hierarchy, and the figure lists the first few levels and the fact.

Still open: whether new axioms will settle the size of the line #

The top two tiers in the figure are $2^{\aleph_0}$ and $2^{2^{\aleph_0}}$, and the question the size that cannot be pinned down showed undecidable is where $2^{\aleph_0}$ sits among the alephs — whether it is $\aleph_1$, the smallest uncountable size, as the continuum hypothesis says. The usual axioms do not decide it.

Whether any new axioms, justified by the same kind of reasons that justify the usual ones, will decide it is an open question, and it is sharper than it sounds. Large-cardinal axioms settle an enormous amount about the sets of reals that can be defined — including their measurability, as Solovay’s theorem hints — and leave the size of the line untouched. W. Hugh Woodin has proposed a precise conjecture, the Ultimate-L conjecture, stating that under strong large-cardinal assumptions there is a canonical model of set theory in which the continuum hypothesis holds; whether the conjecture is true, and whether it would make the continuum hypothesis a settled fact or a choice, are both open.

An argument that finds what it cannot name #

The habit worth keeping is the comparison of tiers.

Every existence proof in this essay has the same shape: a class of well-behaved objects is determined by countable information, so it is no larger than the line; the whole collection is larger; so something is left over. The argument names nothing. It produces transcendental numbers without a formula, discontinuous functions without a graph and undefinable numbers without — necessarily — a definition. Size is information, and a class whose members are fixed by less information than the whole collection carries must leave most of the collection out. The same arithmetic runs from the transcendental numbers of 1874 to the hard Boolean functions of 1949, and in both it delivers existence and withholds the example — an honest trade, as long as it is not mistaken for a construction.

The measurable sets are the case that shows the limit of the method. Their members are not fixed by countable information, since every subset of the middle-thirds set is one of them, and so counting cannot find a set outside them. Whether such a set exists turned out to depend on an axiom, which is the most a size argument can ever tell anyone: where the tiers do not separate, the question is not about counting.