Almost none of it left, and still uncountably many

Start with an interval of length one. Remove its middle third, leaving two pieces of length a third each. Remove the middle third of each of those, leaving four pieces of length a ninth. Keep going forever.

Two questions can be asked about what is left, and they have opposite answers. How much of the interval survives, measured by length? None of it. How many points survive, measured by counting? As many as were there to begin with.

The lengths removed add to one #

The removal at the first stage takes one interval of length ⅓. The second stage takes two intervals of length ⅑ each. The third takes four of length 1/27. The pattern is that stage k removes 2ᵏ⁻¹ intervals of length 3⁻ᵏ, so it removes 2ᵏ⁻¹/3ᵏ of the original length.

Adding those up gives ⅓ + 2/9 + 4/27 + …, a geometric series with first term ⅓ and ratio ⅔, whose total is exactly 1.

So everything has been removed, in the sense that the removed pieces account for the entire length. The same conclusion arrives from the other direction: after k stages the surviving intervals have total length (⅔)ᵏ, which goes to zero. The figure computes both — the surviving total and the removed total — and requires them to add to 1 at every stage.

A set that can be covered by intervals of arbitrarily small total length is said to have measure zero. This one does, and any reasonable notion of length has to give it nothing.

Here is the first awkwardness. The middles are removed and the endpoints are not. The point ⅓ is an endpoint of the first removed interval and survives every stage; so does ⅔, so does 1/9, so does 2/9, and so on. Every stage produces twice as many surviving endpoints as the last, and every one of them is in the set forever.

That already gives infinitely many survivors, and it does not begin to account for how many there are. The endpoints are a countable collection, and the set is not.

Addresses in base three #

The clean description comes from writing numbers in base three.

A number in the unit interval has a base-three expansion 0.d₁d₂d₃… with each digit 0, 1 or 2. The first stage removes the numbers whose first digit must be 1 — the open middle third. The second stage removes those whose second digit must be 1, and so on.

So the surviving set is exactly the numbers with a base-three expansion using only the digits 0 and 2.

The qualification must be matters: the number ⅓ can be written as 0.1000… or as 0.0222…, and since one of those uses no 1 the number survives. That ambiguity is the same one that makes 0.999… equal to 1 in base ten, and it is the reason the endpoints stay.

Counting what is left #

Now the second question. Take a surviving number, look at its address, and replace every 2 by a 1. The result is a string of 0s and 1s — a binary expansion — and every binary expansion arises from exactly one such address.

Binary expansions name every number in the unit interval. So the survivors correspond, one for one, with the whole interval that was started with. Nothing was lost in count while everything was lost in length.

That correspondence has the same small blemish every such correspondence has — the numbers with two binary expansions are hit twice — and the repair is standard: the exceptions are a countable set, and two injections make a bijection, so the exact correspondence follows from the two easy directions.

The uncountability can also be got at directly, by the diagonal argument: given any list of survivors, build a new address disagreeing with the kth listed address in the kth digit, choosing 0 or 2 so as to stay in the set. The new number is a survivor and is not on the list.

Everything it contains, and everything it does not #

Three properties of the set follow from the addresses in a line each, and together they say what kind of object it is.

It contains no interval. Any interval, however short, contains numbers whose base-three expansion has a 1 in some position that cannot be avoided — because after enough digits the interval is longer than 3⁻ᵏ and must straddle a removed middle. So the set is full of gaps at every scale.

It has no isolated points. Every survivor has other survivors arbitrarily close: change a digit far enough along the address and the number moves by an arbitrarily small amount while staying in the set. So it is not a scatter of separated specks either.

It is closed. Each stage removes open middles, so what is left at every stage is closed, and an intersection of closed sets is closed. A limit of survivors is a survivor.

A set with those three properties is called perfect, and the combination is what the intuition has no picture for: no gaps in the sense of isolated points, gaps everywhere in the sense of containing no interval. Every drawing on this page shows an approximation with intervals in it, and the intervals are exactly the thing that does not survive.

Two sizes that disagree #

The set therefore has as many points as the interval and none of its length. That is not a paradox but it is a genuine surprise, and it says something about what length is.

Length is not a count. A count is a matter of pairing off, and the pairing here is exact. Length is a matter of covering, and the survivors can be covered by 2ᵏ intervals of total length (⅔)ᵏ, which is as small as anybody likes.

The two notions disagree because they measure different things, and the disagreement is not an exotic case. The rationals in the unit interval also have measure zero and are dense; the difference is that they are countable, so they are small in both senses. This set is small in one sense and as large as possible in the other, which is what makes it the standard example.

The consequence for integration is direct. The Riemann integral cannot cope with a function that is 1 on a dense set and 0 elsewhere, because every strip contains both. The Lebesgue integral can, and the way it does is by declaring that what happens on a set of measure zero cannot affect an integral. Measure zero is the notion of negligible that made a working theory of integration possible, and a set with as many points as the line is negligible under it.

The precise statement is worth having, since it settles exactly which functions the older definition handles: a bounded function has a Riemann integral if and only if its points of discontinuity form a set of measure zero. Dirichlet’s function is discontinuous everywhere, so it fails. A function discontinuous exactly on the set drawn here passes, because that set has measure zero — which means a function can be discontinuous at uncountably many points and still be integrable in the old sense. The rectangles do not care how many discontinuities there are; they care how much room the discontinuities take up.

Small in both senses, for comparison #

The set to compare it against is the fractions, and the comparison is what shows that measure zero and countable are different conditions.

The fractions can be listed — first by denominator, then by numerator — and a listing is all that is needed to cover them cheaply. Put an interval of length ε/2 round the first, ε/4 round the second, ε/8 round the third, and so on; the total is ε, which can be made as small as desired. So the fractions have measure zero, and they are dense in the interval: every gap contains one.

That is the standard picture of a small set, and this essay’s set is not it. Both have measure zero. The fractions are countable and this set is not, and there is no listing of it to build a cheap cover from — the cover has to come from the construction, and the construction supplies one because the surviving intervals halve in total length at each stage.

Reading the two together gives the shape of the classification. Countable implies measure zero, and the converse fails badly: measure zero says nothing at all about how many points there are.

The dimension in between #

There is a third notion of size that gives this set something rather than nothing, and it is the one that made the whole family famous.

Scaling the set by three produces two copies of itself. For an ordinary object, scaling by three multiplies the content by 3 to the power of the dimension — a line by 3, a square by 9, a cube by 27. Solving 3ᵈ = 2 gives d = log 2 / log 3, about 0.6309.

That is not a whole number, and there is no interpretation of it as counting directions. What it does is fill the gap the other two notions leave: length says zero, counting says as many as the line, and dimension says 0.63 — smaller than a line and larger than a countable scatter of points. The set is genuinely between the two, and the exponent is what says by how much.

The set as a machine for building examples #

Once the addresses are understood the set stops being a curiosity and becomes a tool, because its structure is exactly a space of infinite sequences of two symbols.

That is what makes it turn up in places with no removal of middles anywhere in sight. The states a cellular automaton can be in are sequences of symbols, and so are the itineraries of a point under a doubling map — which orbit a point follows is recorded by writing down, at each step, which half of the interval it landed in. Those two subjects study very different objects and both are studying sequences of symbols, which is to say both are studying this set with different coordinates on it.

The technique has a name, symbolic dynamics, and its power is that a question about a continuous process becomes a question about strings. Whether an orbit is periodic becomes whether a string repeats; whether two orbits are close becomes whether two strings agree for a long prefix. The set drawn here is where that dictionary is at its cleanest, because the correspondence between points and strings is exact rather than approximate.

The other standing use is as a source of counterexamples. A construction that removes middles at a chosen rate can be tuned to produce a set of any dimension between 0 and 1, or a set with positive measure and no intervals, or a set whose sum with itself is the whole interval. Nearly every strange object in elementary analysis is one of these with the parameters changed.

What it costs #

The construction is exact at every stage and cheap: stage k has 2ᵏ intervals, each a triple of rational endpoints, so the figures compute the sixth stage’s 64 intervals and their exact total length without approximation.

Going much further is expensive for the obvious reason. The tenth stage has 1,024 intervals of length 3⁻¹⁰, which is under a sixty-thousandth — narrower than a pixel on any drawing. So the picture cannot be pushed past about seven stages before the surviving pieces become invisible, which is a limitation of the drawing rather than of the arithmetic.

Testing whether a specific number is in the set is a different kind of computation: expand it in base three and look for a 1 that cannot be avoided. For a rational number that terminates or repeats, the test finishes; for a number given only as a decimal approximation, it does not, because no finite prefix settles what comes later. Membership is decidable for the numbers that can be written down and undecidable in general, which is the usual state of affairs for questions about real numbers.

What the picture cannot show #

Every drawing stops at a finite stage, and the set is the intersection of all of them. The bars in the first figure at stage six are 64 intervals of positive width; the set has no intervals in it at all, and there is no stage at which that becomes visible.

Nor can any figure show the correspondence with the whole interval. That is a pairing between two uncountable collections, established by a rule about digits, and a picture can show a handful of addresses and no more.

And the drawings are of one construction. Removing middles of a different size — a fifth, say, or a proportion that shrinks from stage to stage — gives sets that look identical on the page and have different dimensions, and one such variant has positive length while still containing no interval. Nothing distinguishes those pictures from this one.

The ladder from here #

Rungs above: the fat Cantor set, built by removing shrinking proportions, which contains no interval and has positive length — and which shows that contains no interval and has no length are different statements. Lebesgue measure defined properly, with the outer measure and the covering argument. The Cantor function, which is continuous, rises from 0 to 1, and has zero derivative everywhere outside a set of measure zero. Hausdorff dimension in general, and the box-counting dimension that is easier to compute. Self-similar sets and the formula for their dimension from the scaling ratios. And the connection to base representations, where the structure of the addresses is what everything above turns on.

The shape of the idea #

The essay is about a disagreement between two ways of asking how big, and the value of the example is that it forces both questions to be asked precisely.

Before it there was one intuitive notion of size doing several jobs. Afterwards there are at least three — counting, measure, and dimension — and they give ‘as many as the line’, ‘nothing at all’, and ‘0.63’ for the same object. None of them is wrong. They are answers to different questions that had not previously been distinguished, and the object that separates them is what made the distinction necessary.

That is the standard service a counterexample performs, and it is worth noticing that this one is not exotic in its construction. Removing middle thirds is a rule a child could follow, and everything strange about the result comes from carrying it out infinitely often — which is the same source as every other surprise in this part of the subject.