Theorem 36: the Cantor set is an uncountable set with zero measure

This week’s post is by Laura Irvine, who is just about to start her second year reading Mathematics at Murray Edwards College, Cambridge.  Thanks very much, Laura!

First of all, what is the Cantor set?

To form the Cantor set, start with the closed interval [0,1] (this means 0 and 1 are included in the interval) and remove the middle open third of the interval (i.e. remove (\frac{1}{3}, \frac{2}{3}) where the curved brackets mean the interval is open, so \frac{1}{3} and \frac{2}{3} are not themselves in the interval).  You should be left with two disjoint closed intervals: [0, \frac{1}{3}] and [\frac{2}{3}, 1].  I’m going to call this step the first iteration.

Then do the same thing to each of these intervals: remove the middle third of each to get the new intervals as [0, \frac{1}{9}], [\frac{2}{9}, \frac{1}{3}], [\frac{2}{3}, \frac{7}{9}], [\frac{8}{9}, 1].  Then remove the middle third of each of these intervals.  Keep repeating this process and the Cantor set is the set of all the points in the interval [0,1] that are never removed.  So the first few steps of the process look like this:

The Cantor set

Do you understand how this set is formed?  Can you think of some points that are in the Cantor set?

Well, 0 will never be removed: the first closed interval after the n^{\textrm{th}} iteration would be [0, \frac{1}{3^n}] so 0 will be in the infinite intersection of the first interval of each step.  The other interval endpoints are points in the set too.  It turns out that there are also points that are in the set that aren’t interval endpoints.

An interesting and, in my opinion, rather surprising property of the Cantor set is that it has measure 0, despite being an uncountable set!  The fact it is uncountable means there is no way of writing all the numbers in the Cantor set in a list.

So, intuitively, this is saying that if all the points in the Cantor set were lined up next to each other, the line would have length 0 and yet there are infinitely many points in the set.  How weird is that?!

How can we show the Cantor set is uncountable?  Well, it would be good if we could show that there’s a surjection from the set to another set that we already know is uncountable.  This would show that there are at least as many points in the Cantor set as there are in this other uncountable set.  We know that there are uncountably many real numbers so how about trying to construct a surjection from the Cantor set to the real numbers?

First, we need to work in a ternary system.  This is a similar idea to the binary system (which is where numbers are written using just the digits 0 and 1) or the decimal system (where you use the digits 0 to 9).  However, in a ternary system there are three digits that can be used: 0, 1 and 2.

To write a number in the decimal system, you might imagine column headings of units, tens, hundreds etc. (i.e. 1, 10, 10^2, 10^3, …).  In binary, you would imagine column headings of 1, 2, 4, 8, 16, etc. (i.e. 1, 2, 2^2, 2^3, …).

In ternary, the column headings would be (from right to left) 1, 3, 9, 27, ….

So, to write a given number, say 66, in ternary, think what the biggest power of 3 is that is still less than, in this case, 66.  So that will be 2727 goes into 66 twice so in the `27 column’, write 2.

66-2\times 27 = 12 so we now see what the largest power of three that is less than 12 is.  It’s 9 and 9 only goes into 12 once so write 1 in the `9 column’.

Carry on in this way.

12 - 9 = 3 so in the `3 column’ write 13 -3 = 0 so put 0 in the final column.

So, in ternary, 66 = 2110.  Does that make sense?  What would 32 be in ternary?

For numbers between 0 and 1, the column headings will be \frac{1}{3}, \frac{1}{9}, \frac{1}{27}, etc.  So \frac{1}{3} would be 0.1 and \frac{2}{3} would be 0.2.  Just as another example, \frac{1}{2} = 0.111111111... in ternary.  Can you see how I calculated that?

In the first iteration when forming the Cantor set, all numbers which don’t have 0.0 or 0.2 as their beginning in ternary are removed.  You might think: but what about 0.1?  But that’s alright, because in ternary, 0.1 is the same as 0.0222222....  Then, in the second iteration, get rid of all the numbers that don’t have 0 or 2 in the second position after the decimal point.  And so on, so we can see that in the Cantor set, every number is made up of 0s and 2s.

Now, what we have to do is to map every 2 in any number in the Cantor set to a 1.  So, for example, 0.20002 would become 0.10001.  This will give the full set of numbers in the interval [0,1] in binary.  This means there is a mapping which has its image as the whole of the interval [0,1].  That is, there is a surjection from the Cantor set to all the real numbers in the interval [0,1].  Since the real numbers are uncountable, so the Cantor set must be!

Here comes the cool part!

Theorem The Cantor set has measure 0.

OK, so how can we prove that?  Well, how about calculating how much of the interval [0,1] is removed when forming the Cantor set.  Then we could subtract this number from 1:

Measure of Cantor set = (Measure of the interval [0,1]) – (All the stuff removed from [0,1] to get the Cantor set).

So, to form the Cantor set, we started with an interval of measure 1 and subtracted \frac{1}{3}.  Then of each of the remaining thirds, we took the middle thirds of each away (so we subtracted \frac{2}{9}).  Then there were 4 intervals, each of which had its middle third removed so \frac{4}{27} was subtracted.  Then \frac{8}{81} were removed, then \frac{16}{243} and so on.

Can you see what the difference between the measure of the n^{\textrm{th}} and the (n-1)^{\textrm{th}} iteration would be?

Well, the size of each interval being removed is a third smaller than in the previous step so the denominator will be 3^n.  The numerator, on the other hand, doubles with each step as each interval splits into two new intervals.  So it is 2^{n-1}.

Therefore, all these intervals that we’re removing add up to \sum_{n=1}^{\infty} \frac{2^{n-1}}{3^n} = \frac{1}{2} \sum_{n=1}^{\infty} (\frac{2}{3})^n.

Now \sum_{n=1}^{\infty} (\frac{2}{3})^n is a geometric progression with starting value a = \frac{2}{3} and where each term is \frac{2}{3} of the previous term so the common ratio is r = \frac{2}{3}.  The formula for the sum to infinity of a geometric progression is \frac{a}{1-r} = \frac{2/3}{1/3} = 2 so \frac{2^{n-1}}{3^n} = \frac{1}{2} \times 2 = 1.

1 - 1 = 0 so the measure of the Cantor set is 0.  So the theorem is proved!

Further reading

I found this site and the Wikipedia page had some other interesting things to say about the Cantor set.

9 Responses to “Theorem 36: the Cantor set is an uncountable set with zero measure”

  1. theoremoftheweek Says:

    If you haven’t come across these ideas before, in addition to reading Laura’s very nice post you might also like to have a look at some resources on NRICH:

    The Cantor Set (which includes the opportunity to listen to the Cantor set!)

    How Long is the Cantor Set?

    and

    How Many Elements Are There in the Cantor Set? (which also includes an interactivity).

  2. Xiaoning Wu Says:

    Hi Laura! It’s nice to see your work – very interesting post! I’m working on an environmental project in Plymouth at the moment and would like to just say Hi! Drop me an email if you come across this comment somehow. Enjoy your Maths at Cambridge and hoping to see you sometime! x

  3. Troels Says:

    very nice work but it does not conflict with the idea of a measure.

    Borel:
    Every set whose measure is not zero is uncountable.

    But yes maybe it can seem suprising in the old days before Borel.

    \Troels

  4. Franciscus Rebro Says:

    It doesn’t conflict with Borel’s result (no one said it does), but it is probably the easiest to understand example of an uncountable set with measure 0. Matter of fact, I don’t know of a different example…

  5. ehnoj_21 Says:

    Reblogged this on The Coolest Anti-Stereotypic, Nerdy, Geeky Statistics Guy and commented:
    And because of the take home portion of an exam… I luckily found this nerdy but awesome blog

  6. Daniel Says:

    gr8t job laura keep it up

  7. Abdul Haq Khan Says:

    very nice way to explain that how the cantor set is uncountable. other things are also well. so keep its up

  8. Sani Kassim Says:

    Your article is very helpfull but I still not much clear about comparing the closed interval from 0 to 1 and the set of real numbers as you mentioned!

  9. mike Says:

    what is the measure of a cantor middle fifth set ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 145 other followers

%d bloggers like this: