The size that cannot be pinned down

The last four rungs have been about one infinity and what it absorbs. This one is about the ones above it, and about the single question concerning them that turned out to have no answer — not no answer yet, but a proved absence.

The ladder never stops #

No collection has as many members as it has sub-collections. This is Cantor’s theorem, proved by the diagonal argument, and it applies to infinite collections as much as to finite ones.

So from any collection there is a strictly larger one — its sub-collections — and from that a larger one again. The sizes do not stop. There is no largest infinity, and any argument that produced one would have to be wrong.

The figure checks the finite shadow of that rather than asserting the infinite statement. For every $n$ up to twelve, $2^n > n$; and at the smallest interesting size it does something stronger, trying every possible listing of $n$ subsets of an $n$-element set — $2^{n^2}$ of them, all $512$ at $n = 3$ — and confirming that in each the complemented diagonal is on no row. That is an exhaustion rather than an illustration, which is this field’s standing discipline.

Naming the rungs #

The countable size is written $\aleph_0$ — the size whose arithmetic absorbs everything. The next size up the ladder of alephs — the smallest infinite size strictly bigger than $\aleph_0$ — is written $\aleph_1$, and it exists: the sizes are well ordered, so among those bigger than $\aleph_0$ there is a smallest.

Separately, the size of the sub-collections of a countable set is written $2^{\aleph_0}$, and by the rungs below it is the size of the line, of the plane, of the irrationals and of a great many other things.

These are two different descriptions and there is no reason yet given to think they name the same size. $\aleph_1$ is the next one; $2^{\aleph_0}$ is the size of the line. Cantor’s theorem says $2^{\aleph_0} > \aleph_0$, so $2^{\aleph_0} \ge \aleph_1$; whether equality holds is the question.

The continuum hypothesis #

Is there a collection of real numbers that is neither countable nor of the same size as the whole line?

Equivalently: is $2^{\aleph_0} = \aleph_1$? Cantor asked it in 1878, believed the answer was yes, and worked on it for the rest of his life without settling it. Hilbert put it first on his list of problems in 1900.

The answer arrived in two halves, forty years apart.

Gödel, 1938. If the axioms of set theory are consistent, they remain consistent with the hypothesis assumed. He built a model — the constructible universe, in which every set is obtained by an explicit definition from earlier ones — and showed the hypothesis holds in it. So the hypothesis cannot be disproved.

Cohen, 1963. If the axioms are consistent, they remain consistent with the hypothesis denied. He invented forcing, a method for extending a model of set theory by adding new sets carefully enough that the axioms survive, and used it to add so many real numbers that the hypothesis fails. So the hypothesis cannot be proved.

Together: the axioms of set theory settle the question in neither direction. It is independent of them.

What independence is, and is not #

The shape of the conclusion is one this site has met before and is easy to misread.

It is not that the question is too hard. The Riemann hypothesis is unsettled and might be settled tomorrow. This one has been settled, and the settlement is that no proof exists either way from these axioms.

It is not that the answer is unknowable in principle. Independence is relative to a list of axioms. A different or larger list may decide the question, and several do — the axiom of constructibility settles it yes, various large-cardinal and forcing axioms settle it no. What is proved is that this list does not.

It is not the same as Gödel’s incompleteness. The sentence that says it has no proof is constructed to be undecidable and is about provability; the continuum hypothesis is a natural mathematical question that was asked long before anybody suspected independence was possible. That a question people cared about turned out to be independent is what made the result shattering rather than technical.

It is the same shape as the parallel postulate, and that comparison is the most useful one. A statement is independent of a list of axioms when there is a structure obeying the axioms where it holds and another where it fails. Beltrami’s disc did that for geometry in 1868; Gödel’s and Cohen’s models did it for set theory. The method is one method.

The two halves are not symmetric #

Gödel’s result and Cohen’s are usually stated as a matched pair and they are not, and the difference explains why one took twenty-five years longer.

Gödel restricts. He builds a universe with as few sets as the axioms allow: at each stage, only the sets definable from what is already there. In that universe every real number has a definition, the reals turn out to be well ordered in a way the axioms alone do not provide, and the continuum hypothesis holds — with room to spare, since so little was admitted. Restricting is comparatively easy, because throwing sets away cannot make an axiom fail unless the axiom demanded them.

Cohen extends. He starts with a model and adds sets to it — enough new real numbers to push the continuum past $\aleph_1$ — and the difficulty is that adding almost anything breaks an axiom. The added sets must be generic: sufficiently unlike anything the original model can describe that no formula in it can pin them down, and yet controlled enough that every axiom survives.

Forcing is the machinery for doing that, and it works by naming what is to be added before it exists: a partial order of finite approximations, and a forcing relation saying which statements are guaranteed by which approximations. What the extended model satisfies is decided inside the original one, which is the trick that makes the whole thing possible.

Restricting is a construction and extending is an invention. Cohen’s method turned out to be general — it has since decided dozens of independence questions across set theory, topology and analysis — and that generality is why it, rather than the particular answer about the continuum, is what he is remembered for.

What it says about what a set is #

There is a reading of the result that is worth resisting and one that is worth taking, and telling them apart is most of what the result means.

The reading to resist: there is no fact of the matter, so the question is meaningless. That does not follow. The axioms fail to decide many things they were never designed to decide, and a statement’s independence from one list says nothing about its truth.

The reading to take: the axioms do not pin down what a set is. They constrain it — enough to develop nearly all of mathematics — and they leave room for universes with wildly different collections of real numbers. In Gödel’s universe the reals are as sparse as the axioms permit; in Cohen’s they can be made as plentiful as desired. Both obey every axiom.

That is a strong claim about the axioms rather than about sets, and it is the reason the search did not stop in 1963. If the axioms leave the question open, the project becomes finding further axioms with independent justification that settle it — and that project is alive, with the current candidates coming from the theory of large cardinals and from determinacy.

Gödel himself expected the hypothesis to be false and thought the right further axioms would show it, which is a position rather than a proof and is worth knowing about because it undercuts the flat reading above. Somebody who believed the question meaningless would not have had a preferred answer.

What would follow if it were settled #

A statement is worth caring about in proportion to what it decides, and this one decides a great deal — which is why its independence was a blow rather than a curiosity.

Assume it. Then every uncountable set of real numbers has the size of the whole line, so the hierarchy of infinite sets of reals has exactly two levels. Sierpiński collected over eighty statements equivalent to it, most of them in analysis and geometry rather than in set theory: there is a set of points in the plane meeting every horizontal line in a countable set and every vertical line in all but countably many; the plane can be covered by countably many curves; and there exist Luzin sets, which are uncountable and meet every meagre set in a countable piece.

Deny it. Then there is a set of reals of intermediate size, and questions about which properties such a set can have become the subject. Martin’s axiom, one of the standard alternatives, asserts that sets of size below the continuum behave like countable ones in a precise sense — and it is consistent with the hypothesis failing, so it is one of the ways of denying it that has consequences worth having.

The pattern in the equivalents is worth noticing. Almost every one is a statement about decomposing the line or the plane into countably many well-behaved pieces, and what the hypothesis buys is exactly the transfinite induction of length $\aleph_1$ that such decompositions need. The hypothesis is a construction principle, and the reason it was believed for eighty years is that it makes so many constructions possible.

Two statements that sound alike and are not #

The hypothesis has a variant and a neighbour, and keeping them apart is worth a section because both are frequently muddled with it.

The generalised continuum hypothesis says $2^{\aleph_\alpha} = \aleph_{\alpha+1}$ for every $\alpha$ — the same claim at every rung rather than only the first. It is strictly stronger, it holds in Gödel’s universe as well, and it implies the axiom of choice, which the ordinary hypothesis does not. That last is a genuine surprise: a statement about sizes forces a statement about selections.

The well-ordering of the reals says the real numbers can be arranged in a sequence in which every non-empty subset has a least member. That follows from choice and has nothing to do with the continuum hypothesis; it is what makes $\aleph_1$ a sensible thing to talk about at all, since without some form of choice the size of the line need not be an aleph.

Without choice, the situation is worse than undetermined. There are models in which the reals cannot be well ordered, so $2^{\aleph_0}$ is not comparable to $\aleph_1$ — not bigger, not smaller, not equal. The question the continuum hypothesis asks presupposes a comparison that is itself an axiom.

How much is undecided, and it is more than one gap #

The independence is not confined to the first step. Once forcing was available it became clear that the value of $2^{\aleph_0}$ is almost entirely unconstrained.

Easton’s theorem says that, for regular cardinals, the function taking $\kappa$ to $2^{\kappa}$ can be almost anything: the axioms require only that it increases and that $2^{\kappa}$ has cofinality above $\kappa$, and any assignment obeying those two is consistent. So $2^{\aleph_0}$ can consistently be $\aleph_1$, or $\aleph_2$, or $\aleph_{17}$, or $\aleph_{\omega_1}$.

That is the general form of the result and it is more disquieting than the single question. The hypothesis is not one stubborn statement among a settled landscape; the whole of cardinal exponentiation above the first infinity is undetermined by the axioms, and the continuum hypothesis is simply the first instance anybody asked about.

One thing is not undetermined, and it is the sole exception worth naming. $2^{\aleph_0}$ cannot be $\aleph_{\omega}$, because a cardinal of the form $2^{\kappa}$ cannot have cofinality $\kappa$ — König’s theorem, and it is the only constraint the axioms impose beyond monotonicity.

Cantor’s own attempt, and what he actually proved #

Cantor believed the hypothesis and spent two decades trying to prove it, and what he got instead is worth knowing because it is a genuine theorem and it is often mistaken for the hypothesis itself.

Every closed uncountable set of real numbers has the size of the whole line. That is the Cantor–Bendixson theorem, proved by repeatedly stripping away the isolated points of a set and continuing through the ordinals until nothing more is removed. What is left is a perfect set, and a non-empty perfect set has the size of the continuum.

So the hypothesis holds for closed sets. Cantor’s programme was to extend the argument class by class — closed sets, then countable unions of them, then the whole projective hierarchy — and each extension is a real theorem. The Borel sets were settled by Alexandrov and Hausdorff; the analytic sets by Suslin.

Every one of those results holds. What does not follow is the hypothesis, because the classes never exhaust the sets of reals — and the sets that escape them are exactly the ones no definition reaches, which is where the independence lives.

There is a moral about research programmes in the shape of it. Cantor’s assault on the hypothesis failed and produced the theory of ordinals, the Cantor–Bendixson analysis, and the beginnings of descriptive set theory — three subjects that outlived the question they were built for. The independence proof settled the original question by showing it had no answer, and every tool built along the way is still in use.

What the picture cannot show #

The figure draws four rungs of a ladder that has no top, so the drawing is a window and the theorem is about the whole. That the ladder continues is asserted by the diagonal argument, which is prose here and has its own essay.

The gap is drawn as a gap, which is the best available and is not right. What is being claimed is that the axioms neither put something there nor rule it out — a statement about proofs, not about a region — and a drawn gap says there is a space here, which is one of the two answers rather than the absence of both.

And the ladder is drawn as though the rungs were reached by repeated exponentiation, which is one way up and not the only one. The alephs are indexed by the ordinals and there are limit stages; the relationship between the aleph ladder and the exponentiation ladder is exactly what is undetermined, and a picture with one ladder in it cannot show two.

Where the ladder goes next #

Above: large cardinal axioms, which extend the list upward and settle a great deal without settling this; the axiom of determinacy, which is inconsistent with choice and gives the reals a much better-behaved theory; and the ongoing programme of finding a principled reason to prefer one answer.

One debt, and it is the largest this ladder leaves. Forcing is named here and not explained, and it is the single most important technique in the subject. A drawable account of it — a partial order of finite conditions, a generic filter meeting every dense set, and the model built from the names — is a real possibility and is not attempted here.

What was actually proved #

A natural question about sizes has no answer from the axioms, and that absence is itself a theorem.

Everything on this ladder up to here was a construction: a pairing, a listing, a weave. This rung is the one where the constructions run out, and what replaces them is a proof about proofs. The result is not that the continuum’s size is unknown; it is that the axioms were never strong enough to have an opinion, and finding that out required building two universes in which they do not.