The Cantor set¶

Level: 201 · for anyone who has met a limit

One line: Delete the middle third of [0, 1], then the middle third of every piece left, forever — what survives has length 0 and as many points as the whole interval, so measure zero is not about how many points a set has.

Why countable was not the end of it¶

Countable sets showed that any set that can be written as a list has measure zero. It is tempting to read that backwards, as if measure zero just meant "few enough points to list". The Cantor set is the counterexample. It cannot be listed, it has exactly as many points as [0, 1], and it still has measure zero.

This is the standard, middle-thirds Cantor set. The same recipe with narrower gaps builds the fat Cantor set, the next lesson, which turns out very differently.

What the program prints¶

Verified output of cantor_set.py — regenerated by tools/run_examples.py, never hand-typed.

1. BUILD IT
   Each step deletes the open middle third of every piece left.
     0 |#################################################################################|
     1 |###########################                           ###########################|
     2 |#########         #########                           #########         #########|
     3 |###   ###         ###   ###                           ###   ###         ###   ###|
     4 |# #   # #         # #   # #                           # #   # #         # #   # #|

     step   pieces   each piece   length left
        0        1   1            1.000e+00
        1        2   1/3          6.667e-01   = 2/3
        2        4   1/9          4.444e-01   = 4/9
        3        8   1/27         2.963e-01   = 8/27
        4       16   1/81         1.975e-01   = 16/81
        5       32   1/243        1.317e-01   = 32/243
       10    1,024   1/59049      1.734e-02
       20     2^20   1/3^20       3.007e-04
       50     2^50   1/3^50       1.568e-09
   Removed after n steps: exactly 1 - (2/3)^n. Removed in the limit:
   exactly 1, the entire length of the interval we started with.

2. SO IT HAS MEASURE ZERO
   Whatever the budget, stop at a step where the pieces left fit in it:
     budget 1/100            step 12: 2^12 pieces,  total length 7.707e-03
     budget 1/1000000        step 35: 2^35 pieces,  total length 6.868e-07
     budget 1/1000000000000  step 69: 2^69 pieces,  total length 7.075e-13
   The pieces at every step cover everything that will ever survive.

3. WHAT SURVIVES? THE ENDPOINTS, FOR A START
     0, 1/9, 2/9, 1/3, 2/3, 7/9, 8/9, 1 ...
   A piece's endpoints are never deleted. But endpoints are fractions
   with a power of 3 underneath, so there are only countably many. If
   nothing else survived, this would be one more countable set.

4. THE BASE-3 TEST
   Deleting a middle third deletes the numbers whose next base-3 digit
   is 1. So x survives exactly when it can be written with only 0s and 2s.
     x      base 3             only 0 and 2?  construction says
     1/4    0.020202020202...  yes            survives 60 steps
     3/4    0.202020202020...  yes            survives 60 steps
     1/10   0.002200220022...  yes            survives 60 steps
     1/13   0.002002002002...  yes            survives 60 steps
     1/3    0.022222222222...  yes            survives 60 steps
     1/2    0.111111111111...  no             deleted at step 1
     1/5    0.012101210121...  no             deleted at step 2
     5/9    0.12               no             deleted at step 1
   1/4 survives, and it is no endpoint -- its denominator is 4, not a
   power of 3. (1/3 = 0.1 in base 3, but also 0.0222..., so it passes.)

5. HALVE THE DIGITS
   Turn every 2 into a 1 and read the result in base 2:
     point  base 3              digits halved, base 2  is
     1/4    0.020202020202... -> 0.010101010101...      1/3
     3/4    0.202020202020... -> 0.101010101010...      2/3
     1/10   0.002200220022... -> 0.001100110011...      1/5
     1/13   0.002002002002... -> 0.001001001001...      1/7
     1/3    0.022222222222... -> 0.011111111111...      1/2
     2/3    0.2               -> 0.1                    1/2

   Now run it backwards. Pick ANY number, write it in base 2, double
   the digits, and read base 3. The result is always in the Cantor set:
     1/3    -> 1/4            which halves back to 1/3
     1/7    -> 1/13           which halves back to 1/7
     5/8    -> 20/27          which halves back to 5/8
     7/10   -> 23/30          which halves back to 7/10
     99/100 -> 530909/531450  which halves back to 99/100
   Every number in [0,1] is hit, so the Cantor set has at least as many
   points as [0,1] itself: UNCOUNTABLY many. (1/3 and 2/3 both land on
   1/2, so some numbers are hit twice -- which costs the argument nothing.)

6. HOW BIG IS IT?
     total length          0
     number of points      as many as the whole interval [0,1]
     contains an interval  no -- every piece gets cut at the next step
     dimension             log 2 / log 3 = 0.6309
                           more than a point's 0, less than a line's 1

Building it¶

Start with [0, 1]. Delete the open middle third, (1/3, 2/3), leaving two closed pieces, [0, 1/3] and [2/3, 1]. Delete the open middle third of each of those. Keep going forever. The Cantor set is what is never deleted.

After n steps there are 2ⁿ pieces, each 1/3ⁿ long, so the length left is (2/3)ⁿ: 32/243 after five steps and about 1.6 × 10⁻⁹ after fifty (section 1). The deleted gaps add up to

1/3 + 2/9 + 4/27 + 8/81 + ⋯  =  1

which is the entire length of the interval we started with.

It has measure zero¶

This part is almost free. The 2ⁿ pieces at step n contain everything that will ever survive, and their total length is (2/3)ⁿ. Go far enough and that fits any budget: step 12 fits inside 1/100, step 35 inside one millionth (section 2). That is the definition of measure zero, and this set does not even need an infinite list of intervals to meet it.

So is anything left at all?¶

A piece's endpoints are never deleted: 0, 1/3, 2/3, 1/9, 2/9, 7/9, 8/9, and so on. But every endpoint is a fraction with a power of 3 on the bottom, and those can be listed. If the endpoints were all that survived, the Cantor set would be one more countable set, and this page would be over.

They are not all. Section 4 shows that 1/4 survives every step, and 1/4 is no endpoint: its denominator is 4.

The base-3 test¶

Write numbers in base 3. The first deletion removes (1/3, 2/3), which is exactly the numbers whose first base-3 digit must be 1. The second deletion removes those whose second digit must be 1, and so on down. So:

x is in the Cantor set exactly when x can be written in base 3 using only the digits 0 and 2.

"Can be written" matters for the numbers with two expansions. 1/3 is 0.1 in base 3, which fails the test, but it is also 0.0222…, which passes — and 1/3 is an endpoint, so it should pass.

Section 4 checks the test two independent ways, by reading the digits and by running the construction for 60 steps, and the program stops if they ever disagree. 1/4 = 0.020202…₃ passes both. 1/2 = 0.1111…₃ is deleted at step 1, and 1/5 = 0.0121…₃ at step 2.

Uncountably many points¶

Here is why the Cantor set is as big as [0, 1]. Take a Cantor point, whose base-3 digits are all 0s and 2s. Halve every digit — each 2 becomes a 1 — and read the result in base 2 (section 5):

1/4   = 0.020202…  in base 3   →   0.010101…  in base 2   = 1/3
3/4   = 0.202020…  in base 3   →   0.101010…  in base 2   = 2/3
1/13  = 0.002002…  in base 3   →   0.001001…  in base 2   = 1/7

Now run it backwards, where nothing can go wrong. Take any number in [0, 1], write it in base 2, double every digit, and read the result in base 3. It has only 0s and 2s, so it is a Cantor point — one that halves back to where you started. 7/10 comes from 23/30; 99/100 comes from 530909/531450.

So every number in [0, 1] is hit by some Cantor point, and the Cantor set has at least as many points as [0, 1]. [0, 1] is uncountable — no list can contain all of its numbers, which is Cantor's diagonal argument — so the Cantor set is uncountable too.

One wrinkle, which costs nothing: the matching is not one-to-one. 1/3 = 0.0222…₃ halves to 0.0111…₂, and 2/3 = 0.2₃ halves to 0.1₂, and both of those are 1/2. Some numbers are hit twice. Hitting every number at least once is all the argument needs.

How thin is it?¶

Measurement	The Cantor set
total length	0
number of points	as many as [0, 1]
contains an interval?	no — every piece is cut at the next step
dimension	log 2 / log 3 ≈ 0.6309

The last row says how thin. The Cantor set is two copies of itself, each shrunk by a factor of 3. A line segment is three copies of itself shrunk by 3, so its dimension is 1 (3¹ = 3); a dimension d with 3ᵈ = 2 gives d = log 2 / log 3. More than a scatter of points, less than a line.

The lesson¶

How many points a set has, and how much room it takes, are different measurements. Countable implies measure zero; measure zero does not imply countable.

What the Cantor set does have is gaps everywhere, and no interval inside it at all. It is tempting to think that is the real reason its length is zero. The fat Cantor set shows it is not.

Run it yourself¶

From the root of your clone of this repository:

python3 02_Measure_Zero/cantor_set/examples/cantor_set.py