Mathematical Musing: The Cantor Set is Uncountably Infinite: A Proof

This post is intended for my Fractals and Chaos students. Other students may find it interesting, but in order to understand its full context, you will have to take my class! For those looking for an explanation of this third property of the Cantor Set, read on.

In class, you learned that there are different types of infinity, and while the natural numbers are “countably infinite” (as are the integers and rational numbers), the real numbers are “uncountably infinite.” See this post if you missed this explanation in class.

At each stage of the Cantor Set, we remove a portion of the interval [0,1]. The endpoints of the portions we leave behind can be mapped to the natural numbers, so in order for us to claim that the Cantor Set is uncountable, there must be other members of the set left over, an uncountable quantity of numbers/points that aren’t endpoints of segments, but also are never within segments that are removed. To see where these numbers are, we have to look at base-3 fractions.

All your base are belong to us…

Our number system is base 10 (or decimal). When we consider a number like 427, what we are describing is a quantity made up of four 100s, two 10s, and seven 1s. Each place value of a number written in base-10 is a power of 10, and there are 10 possible entries for each place value. The same goes to the right of the decimal point as well: if we decrease powers from 10^2 = 100, to 10^1 = 10, to 10^0 = 1, we continue to get 10^-1 = 1/10, 10^-2 = 1/100, and so on. As a result, a fraction like 1/4 can be expressed as the decimal 0.25, which corresponds to 2*10^-1 + 5*10^-2, which is perhaps easier thought of as 2/10^1 + 2/10^2.

If we want to use base-3 fractions, then the principle is the same, but everything is in threes. The denominators of our fractions are powers of three, and we only allow three options for the numerator: 0, 1, and 2. As soon as we hit something like 3/3^2, what we actually have is 3/9 = 1/3 = 1/3^1. So there’s only room for those three digits in the numerator before any fraction reduces to a different fraction with a lower power in its denominator.

Unfortunately, perhaps, this makes fractions like 1/4 much more awkward to express. The base-3 fractional expansion of 1/4 is 0/3^1 + 2/3^2 + 0/3^3 + 2/3^4 + …

Proof: 

0/3^1 + 2/3^2 + 0/3^3 + 2/3^4 + … = 2/3^2 + 2/3^4 + 2/3^6 + …

=2/9 (1 + 1/3^2 + 1/3^4 + 1/3^6 + …), which is a geometric sequence with a1 = 1 and r = 1/9. Thus, this infinite series equals…

=2/9 * 1/(1-1/9) = 2/9 * 9/8 = 2/8 = 1/4.

So what?

Consider some member of the Cantor Set x. We can express x as an infinite series of fractions a1/3^1 + a2/3^2 + a3/3^3 + a4/3^4 + …, where each numerator is a digit 0, 1, or 2. But what if we say no numerator can equal 1?

  • If a1 is not equal to 1, then x is not in the interval [1/3, 2/3] and is therefore not removed in Stage 1
  • If a2 is not equal to 1, then x is not in the interval [1/9, 2/9] nor [7/9, 8/9] (since 2/3 + 1/9 = 7/9), and is therefore not removed in Stage 2.
  • And so on.

So if the numerators of x are nothing but 0’s and 2’s, then x is in no interval that is removed at any stage of the creation of the Cantor Set. This then means that x is a member of the Set (so, for example, the number 1/4 is a member of the Cantor Set!)

The number of ways to arrange 0’s and 2’s among the numerators of this fraction is mappable to the segment [0,1] (via a similar argument to Cantor’s Diagonal Argument), meaning the size of the Cantor Set shares cardinality with the real number segment [0,1], meaning the Cantor Set is uncountably infinite.

QED.

Questions? Comments?

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.