Subscribe to Computing Intelligence

Sunday, October 5, 2008

The Middle-Thirds Cantor Set

I am not a mathematician. Sometimes I greatly wish I were, but that is not really the point here. Mathematics can still be really fun to think about even for non-mathies like me. Most people find such a statement a little ludicrous, but I am going to attempt to elucidate its merit with an example: the middle-thirds Cantor set.

The Cantor set is created in the following manner:

Take a number line from 0 to 1:


Remove the middle third:

0_________1/3 ... 2/3_________1

Then do the same thing for the remaining sections:

0___1/9 ... 2/9___1/3 ... 2/3___7/9 ... 8/9___1

And continue in that manner, removing the middle of all sections after each step. After doing this an infinite number of times, all the points that remain will form the Cantor set. What is fascinating about this set is that there is an uncountably infinite number of points remaining in the Cantor set, but at the same time the amount removed, when totaled all together, equals 1.

To get the total amount removed, one simply needs to notice the following:

In the first step, 1/3 is removed. In the next, 2/9. In the third, 4/27. In fact, it is not hard to see that in the ith step, the amount removed is 2i-1/3i. The total amount removed is thus the summation over i from 1 to infinity of 2i-1/3i, which can be rewritten as the summation over i from 0 to infinity of (1/3)(2i/3i), which is equal to (1/3)(1/(1-2/3)) = 1. Thus, the entire line is removed, but at the same time an uncountably infinite number of points remain (which I will endeavour to show next).

To show that an uncountably infinite number of points remain, let me first switch from using a decimal system of numbering to a ternary system. Ternary numbers basically use base 3 instead of base 10. For example, if one takes the number 0.467 (written in normal decimal notation), it could equivalently be written as (4/10) + (6/102) + (7/103). Similarly, a number written in ternary notation as 0.102 would be equivalent to (1/3) + (0/32) + (2/33). When writing numbers from 0 to 1 on the number line with ternary notation, only numerals 0, 1, and 2 are used after the decimal point. Visualizing this geometrically, we can see that for a number 0.x1x2..., if x1 is 0, the number must fall somewhere in the first third of the number line (if it is 1 it falls in the middle third, and if it is 2 it falls in the final third). Similarly, if x2 is 0 it falls in the first third of the subsection denoted by x1, if it is 1 it falls in the middle third, and if it is 2 it falls in the upper third. To give an example, take 0.02...:


The first digit is 0, which means it must fall in the first third of our number line:


The second digit is 2, meaning it must fall within the upper third of this section of the number line:


If I had written more digits to the number, we would be able to further hone in on the region of the number line upon which it exists. However, hopefully the example is enough to demonstrate that, if one recalls that we remove the middle third of all sections of our number line, that any number that contains a 1 at any point will be removed. Thus, the Cantor set is made up of all numbers that can be written as 0.x1x2... where all x's are 0 or 2. Since one can have an infinite number of decimal points, there must necessarily be an infinite number of elements in the Cantor set. However, that does not mean there are an uncountably infinite number of elements. That last bit requires one more quick proof:

Assume that there is a countable number of members of the Cantor set and we write them down in the following manner (note, the order I am writing them in is completely arbitrary, since the only necessary thing is that they can all be written together to form a large matrix):

and so on

Then, form a number in the following manner: take the first element of the first number in our matrix and reverse it (0 becomes 2, 2 becomes 0). That becomes the first element of our new number. The second element is likewise the reverse of the second element of the second number, and so on for every number in our set. We thus have formed a new number that is without 1s (so will be in our set), but which necessarily is a novel value because it has at least one digit that is different from every other number, which thereby contradicts the initial assumption that we could enumerate every member of the Cantor set.

Anyway, I just thought that the Cantor set was very interesting. The seemingly contradictory idea that you could remove chunks of a segment of the number line totaling in length to the entire segment, but still leave behind an uncountably infinite number of points is fun to knock about in ones head. I really should stop procrastinating, though, and get back to my work...


Anonymous said...

I think you should get back to work, too. Why do you use "uncountably" instead of "uncountable"?

Mozglubov said...

That is apparently only a math word... does not recognize it, but my professors use it all the time. Anyway, I changed it.

Mozglubov said...

You know what? I changed it back... reading it back over, it sounded funny with uncountable.

It might not be English, but it is math-speak.