The plane cut by a list

The size that cannot be pinned down described the continuum hypothesis: the statement that every infinite set of real numbers is either countable, like the whole numbers, or as large as the whole line. Kurt Gödel and Paul Cohen showed between them that the usual axioms of set theory neither prove nor refute it. Closed sets obey the continuum hypothesis then found it true for every set simple enough to be described by a closed condition, which is as far as it can be proved for definable sets of a natural kind.

Stated that way, the hypothesis is about sizes, and sizes are hard to picture. In 1919 Wacław Sierpiński found an equivalent statement about the plane that can almost be drawn: the continuum hypothesis holds if and only if the plane can be split into two sets $A$ and $B$ such that every vertical line meets $A$ in a countable set and every horizontal line meets $B$ in a countable set. This essay draws the countable version of that split exactly, and follows it to the strangest consequence Sierpiński drew from it.

A list, and a triangle #

The construction starts with a list. Every rational number between nought and one can be put in a single list: first $\tfrac12$, then the fractions with denominator 3, then 4, and so on, each fraction in lowest terms appearing once at a finite position, as every fraction, exactly once did by a different route. Call the list $q_0, q_1, q_2, \ldots$.

The list jumps about: $\tfrac12$, then $\tfrac13$ and $\tfrac23$ on either side of it, then $\tfrac14$ and $\tfrac34$ further out, and every later denominator fills in finer. Its order has nothing to do with the order of the numbers along the line. That is the point: the construction below uses the list’s order and ignores the line’s. Any other list containing every rational exactly once would do as well, and would produce a different split with the same properties.

Now split the pairs of rationals. Put the pair $(q_i, q_j)$ in $A$ when $j \le i$ — when the second coordinate comes no later in the list than the first — and in $B$ otherwise. Every pair lands in exactly one of the two.

A vertical line, $x = q_i$, meets $A$ in the pairs $(q_i, q_j)$ with $j \le i$: exactly $i + 1$ points, a finite number fixed by $q_i$’s position, however far the list is continued. A horizontal line, $y = q_j$, meets $B$ in the pairs with $i < j$: exactly $j$ points. So the rational square splits into a part that is finite on every vertical line and a part that is finite on every horizontal line. The hero figure plots the first ninety rationals’ worth of pairs in their true positions, and the two sets are thoroughly intermingled. The vertical line through $\tfrac25$, the seventh rational in the list, meets $A$ in exactly seven points.

Placed by their positions in the list instead of by their values, the pairs show what the split really is: a triangle. $A$ is the part on and below the diagonal of the list against itself, $B$ the part above, and a column of the triangle holds as many cells as precede its index. The scattering in the hero figure is this triangle with its rows and columns shuffled into the order of the line. Nothing about distances or the arithmetic of fractions was used; only the list.

From the rationals to the reals #

To split the real plane the same way, the reals need a list in which every real has only countably many predecessors, so that each vertical line meets $A$ in a countable set. A list of the ordinary kind, indexed by the whole numbers, cannot hold all the reals — Cantor’s diagonal argument rules it out — but longer lists can. Every set can be well-ordered, by the axiom of choice, and the shortest well-ordering in which every element has only countably many predecessors is the one of order type $\omega_1$, the first uncountable ordinal, whose every proper initial segment is countable. It is the set of all countable ordinals, arranged in their natural order, and reached from below or not at all described the property that makes it useful here: no countable sequence of countable ordinals reaches the top of it, so every element sits at a countable distance from the start while the whole is uncountable. A list of that type is the longest list in which no element has to wait behind uncountably many others.

Whether the reals can be listed in order type $\omega_1$ is exactly the continuum hypothesis. The reals can be listed in type $\omega_1$ precisely when there are exactly $\aleph_1$ of them, which is what the hypothesis says. So if the hypothesis holds, list the reals in type $\omega_1$, put $(x, y)$ in $A$ when $y$ is listed no later than $x$, and every vertical line meets $A$ in the countable set of reals listed no later than $x$, while every horizontal line meets $B$ in the countable set of reals listed before $y$. That is half of Sierpiński’s theorem, and it is the triangle again, with $\omega_1$ cells along each side.

The other half says the split is impossible if the hypothesis fails, and the argument is a counting trick. Suppose the plane splits into $A$ and $B$ as described. Take any set $X$ of exactly $\aleph_1$ reals — there is always one — and look at the vertical lines through its points: on each, $A$ has countably many points, so all of them together cover only $\aleph_1$ heights. If the line has more than $\aleph_1$ points, some height $y$ is missed by all of them: the horizontal line at height $y$ meets every one of those $\aleph_1$ vertical lines in a point not in $A$, so in a point of $B$. Then that horizontal line meets $B$ in at least $\aleph_1$ points, which is uncountable, a contradiction. So the line has at most $\aleph_1$ points, which is the hypothesis.

Nought by columns, one by rows #

Sierpiński used the split to prove something about area, and the countable analogue shows the mechanism.

Fix a vertical line and list more and more rationals. The line acquires more and more points, while its points in $A$ stay at a fixed number, so $A$’s share of the column falls towards nought. Fix a horizontal line instead: its points in $B$ stay fixed, so $A$’s share of the row rises towards one. Average over columns, and $A$ seems to occupy none of the square; average over rows, and it seems to occupy all of it.

For the real plane under the continuum hypothesis this stops being an analogy. Each vertical section of $A$ is countable, so it has length nought, and integrating those lengths across the square gives an area of nought. Each horizontal section of $A$ misses only a countable set, so it has full length, and integrating across gives an area of one. If $A$ had an area in Lebesgue’s sense, the theorem of Guido Fubini would make the two iterated integrals agree. They do not, so $A$ has no area — it is non-measurable, like the set of a set that has no size at all, but built in a completely different way. The paradox is not that the two calculations disagree; it is that each is correct for its own order of summing, and only a set with an area obliges them to agree.

What Fubini’s theorem needs #

The clash between columns and rows is a clash with a theorem that is usually stated without its hypothesis. Fubini’s theorem says that the area of a region can be computed by integrating the lengths of its vertical sections, or of its horizontal sections, and that the two answers agree. The proof needs the region to be measurable — to have an area in Lebesgue’s sense in the first place — and which functions can be added up explained what that means and how much it excludes. For every region anybody draws, and every region defined by a formula, the hypothesis holds without comment.

Sierpiński’s set is where the hypothesis bites. Its vertical sections are countable and its horizontal sections co-countable, so both iterated integrals exist and are perfectly well defined: one is nought and the other is one. Neither calculation is wrong. What is missing is a single number that both are computing, and the theorem’s hypothesis is precisely the guarantee that such a number exists. The countable picture makes the same point with counting in place of integrating: a finite grid of pairs has a definite count, and the counts by columns and by rows agree; the infinite list has no total count, and the shares by column and by row go to opposite limits.

There is a further surprise in the converse direction. Chris Freiling, in 1986, turned Sierpiński’s argument into an argument against the continuum hypothesis: if a dart thrown at random at the plane should land, for any reasonable split, in the part whose relevant section is small, then no split of Sierpiński’s kind can exist, and the hypothesis fails. Freiling’s “axiom of symmetry” makes the intuition precise, and it is equivalent to the hypothesis being false. Whether the intuition about darts is a good guide to sets nobody can describe is exactly what is in dispute, and the dispute is not about the mathematics, which is agreed, but about which axioms describe the real line.

Half of every square #

The countable analogue also shows how evenly the split is spread.

In every one of the 64 small squares, $A$ holds close to half the pairs — between 48 and 52 per cent. The list orders the rationals by denominator, so which of two rationals comes first is essentially unrelated to their sizes, and within any small square of the plane the pairs split nearly evenly. There is no region where $A$ is concentrated and no region it avoids. For the real version that is the signature of non-measurability: a measurable set must, at almost every point, have density close to nought or close to one in small squares around it — Lebesgue’s density theorem — and a set that is half of every square, at every scale, can satisfy that nowhere.

Why an order type, and not a size #

The theorem’s surprise is that a statement about sizes is equivalent to one about the plane’s lines, and the triangle shows why. What a vertical line meets is the set of predecessors of a point in some list, and the size of a set of predecessors is not a property of the set being listed but of the list’s order type. A countable set has lists of many order types — $\omega$, but also $\omega + 1$, $\omega \cdot 2$ and all the countable ordinals one step in front of infinitely many drew — and in every one of them each element has only countably many predecessors. For the reals the question is whether some list has that property, and the answer is yes exactly when the shortest possible list is the shortest possible uncountable one.

So Sierpiński’s split converts the continuum hypothesis from a statement comparing two infinities into a statement about the existence of a single kind of list, and the plane is where the list’s property becomes visible. A list of type $\omega$ gives finite columns, a list of type $\omega_1$ countable columns, and any longer list has some columns at least as large as $\aleph_1$, uncountable. The figure of three triangles is the whole theorem with the details removed.

Generalisations, and a hierarchy of planes #

Kazimierz Kuratowski extended the idea in 1951 to higher dimensions and higher infinities. The number of reals is at most $\aleph_n$ exactly when the space of dimension $n + 2$ can be split into $n + 2$ sets, the $k$-th meeting every line parallel to the $k$-th axis in only finitely many points. For $n = 0$ that is a statement about countable sets and the plane, and finite sections replace countable ones; for $n = 1$ it says that the continuum hypothesis is equivalent to splitting three-dimensional space into three sets, each finite on every line in its own direction. The higher the infinity, the more dimensions the split needs.

The countable case of three dimensions can be built by hand, and it shows what extra room a third coordinate gives. List the rationals as before, and put a triple $(q_i, q_j, q_k)$ in the first set if $i$ is the smallest of the three indices, in the second if $j$ is, and in the third otherwise. A line parallel to the first axis fixes $j$ and $k$, and meets the first set only where $i \le \min(j, k)$: finitely many points. The same holds for each set in its own direction. With three coordinates the rule “the coordinate listed earliest” does the work that “the second listed no later than the first” did in the plane, and Kuratowski’s theorem says that one more coordinate lets the construction survive one more step up the alephs.

Each of these constructions begins by listing a set, and for the reals the list is a well-ordering that exists only by the choice nobody can write down. Without the axiom of choice the real line need not be well-orderable at all, and then neither half of Sierpiński’s theorem can be stated in its usual form; the equivalence is a theorem of set theory with choice, and the triangle needs choice before it needs the continuum hypothesis.

These statements are of the same kind as a line with as many points as a square, which showed that dimension cannot be detected by counting points: the plane and the line have the same number of points. Sierpiński’s and Kuratowski’s theorems show that dimension can, all the same, interact with cardinality in a precise way — not through the number of points but through how the points’ sections along lines can be arranged.

What the countable picture can and cannot show #

Every figure here is exact for the rationals: the list is explicit, the split is computed pair by pair, and the counts of points on lines are what they are. The rationals are a faithful model of the construction’s logic, with “finite” in place of “countable” and “the list” in place of “the well-ordering of type $\omega_1$”, and the triangle and the Fubini clash carry over word for word.

What cannot be drawn is the real version. A well-ordering of the reals of type $\omega_1$, if it exists, cannot be written down: no explicit, definable well-ordering of the reals can be proved to exist from the usual axioms, and in the most natural models of set theory where one does exist it is very far from anything a picture could show. The set $A$ for the reals is therefore a set whose existence follows from the continuum hypothesis and which no one will ever see, and the figures are the only kind of picture it has: a countable shadow with the same logic.

Still open: the plane without the hypothesis #

The continuum hypothesis cannot be settled from the usual axioms, so neither can Sierpiński’s split. What remains open are its relatives under other assumptions. If the reals have size $\aleph_2$, the plane cannot be split Sierpiński’s way but three-space can be split Kuratowski’s way; which other statements about the plane — about sets with prescribed sections, or about colourings of the plane with prescribed behaviour on lines — are equivalent to particular values of the continuum, and which are independent of it in a stronger sense, is a large and active area, in which some natural statements have been settled only recently and others not at all. And for definable sets, where closed sets obey the continuum hypothesis, the analogous question is clean: no Borel set, or analytic set, can be Sierpiński’s $A$, because such sets are measurable and Fubini’s theorem applies to them. The split exists only among the sets nobody can describe.