The Cantor Set: A Love Story
Hey folks! We’re back! Sorry it's been so long since I've written here; I haven't lost interest in the blog, it's just that these past few weeks have been pretty hectic for me with work. In about a month and a half, I'm taking a set of four qualifying exams that I really need to pass (I have one more attempt after this one but obviously I'd prefer to not have to use it). So my posts are going to be pretty infrequent now through May. (In fact I wrote this one on the bus coming back to State College from spring break, about three weeks ago, and I'm only getting around to posting it now. Oh well.)
Last time, I introduced the idea that some infinities are bigger than others, and how we declare that two sets are the same size, i.e. have the same amount of stuff, if and only if there’s a strategy to match everything up between them in such a way that nothing repeats and everything is accounted for. We called this strategy a “bijection.” If you haven’t read my last blog post, “In(finity)ception,” go do that now. Or reread it. It's been a while.
Let’s recap what a bijection might look like. We found that the set of all positive integers, N, is the same size as the set of all positive and negative integers, Z, by matching up 0 with 1, matching up each positive integer n in Z with the number 2n in N, and matching up each negative integer –n in Z with the number 2n+1 in N. We also had a beautiful and elegant way of matching up every integer with every possible fraction. (I’m allowed to call it beautiful and elegant because I didn’t come up with it.) These are countably infinite sets, because they have the same cardinality as the set N of all positive integers.
Here’s another example I feel obligated to mention. Some of you may have read John Green’s novel “The Fault in Our Stars,” or saw the film adaptation that came out in 2014. If so, you may recall that this "different infinities" issue makes a couple of cameos in the story, but Green oversimplifies it enormously. In particular, the character Hazel mentions at one point that “there’s an infinite number of numbers between 0 and 1 … and there’s an even more infinite number of numbers between 0 and 2.” Actually this is wrong. They’re equally infinite sets, even though it seems at first glance that 0 and 1 have a smaller quantity of stuff between them than 0 and 2. Just consider the bijection that matches every point x between 0 and 1 to the point 2x between 0 and 2. In fact if you take a positive number that’s as big as you possibly want—call it M—you can show that the interval from 0 to 1, denoted (0,1), and the interval from 0 to M, denoted (0,M), are again equally infinite. Taking it even further, you can actually create a bijection from the interval (0,1) to the entire real number line R. In other words, the set of points in the contiguous interval (0,1) is just as infinite as the entire smooth real number line, and in fact more infinite than the set of all positive integers N! You gotta admit, that’s pretty mind-blowing.
(Unfortunately the bijection you typically use between (0,1) and R is slightly tricky to explain, but for my friends and readers out there who have taken calculus, or at least trigonometry, a suitable transformation of the function f(x) = arctan(x) will do the job.)
By the way, this is a little informal, but if you want help telling the difference between the set Q of all possible integer fractions and the set R of all real numbers, think of the decimal expansion of real numbers. Everything in Q has either a finite or an infinitely repeating decimal expansion, but R contains numbers like π and the square root of 2, whose decimal expansions do not end and do not repeat. So R is essentially the set of all possible decimal expansions, including those that do not end or repeat. We call numbers with infinite nonrepeating decimals “irrational” numbers.
A few weeks ago, I was explaining some of this to a friend of mine from the Penn State Christian Grad Association (Hi, Grace!), and she asked me, “If the set of positive integers, the set of positive and negative integers, and the set of all integer fractions are the same size, why is the set of all real numbers the magic jump to a bigger infinity?” There is a subtlety to this question that I’d like to come back to, but first, let me explain why R is more infinite than N, and why R is the first example of what we call an “uncountable” set. (I will try to make this as intuitive as possible but if this becomes too abstract and theoretical, feel free to skip the next four paragraphs and just take my word for it that R is uncountable.)
Start by supposing, as Cantor’s skeptics did, that all infinities are the same, and therefore that we can enumerate every possible decimal expansion, including the nonrepeating ones. Enumerate the real numbers between 0 and 1 that only have 0 and 1 in the decimal expansion, because surely if we can enumerate all possible decimal expansions, we can enumerate the ones that just have 0s and 1s in them. Maybe our enumeration starts out looking like this:
Now, this list goes on forever, and contains every possible infinite string of 0s and 1s. So create the following decimal number, and call it s: for the nth decimal position of our special number s, look at the nth decimal expanded number in our enumeration, choose the digit in decimal position n of the nth number, and write the OPPOSITE number in the nth decimal position of s. To see this, look at the bold digits in our enumeration. The digit of the first decimal place of the first number in our enumeration is 0, in bold, so the first decimal digit of s is 1. The digit of the sixth decimal place of the sixth number is 1, in bold, so the sixth decimal digit of s is 0. And so on, and so on. So the first 10 digits of our number s are
s = 0 . 1 1 0 0 0 0 0 1 0 0
So here’s the question. By assumption, our enumeration includes every possible string of 0s and 1s. So where does s belong in our enumeration? It can’t be the sixth number because the sixth digit of the sixth number is 1, and the sixth digit of s is 0. In general it can’t be the nth number because if the nth digit of the nth number is 0, then the nth digit of s is 1, and vice versa. But this is a contradiction, because s must be somewhere in our enumeration! What’s going on?
What’s going on is that we made an important discovery, the same one that Cantor published in 1891. If we assume we have a way of enumerating all possible decimal expansions of 0s and 1s, then we can construct a decimal expansion of 0s and 1s that cannot be anywhere in our enumeration, which is a contradiction. This is the Cantor Diagonalization Argument, and today it is the standard way of proving that the set of all real numbers—which includes the set of all decimal expansions of 0s and 1s—is uncountable.
I mentioned there was a subtlety in my friend’s question. Why is the set of all real numbers the magical jump to uncountably infinite sets? I’d like to appropriate the question and twist it around a little. We can see why R, the set of all reals, is uncountable. But why does it start with R? Is there an infinity that lies between the countable integers and the uncountable reals? Well Cantor spent the last decade or so of his life trying to answer that question, and in fact died in a mental hospital with the question unanswered. The negative answer—the statement “There is no set whose cardinality is between that of the integers and the real numbers”—is today known as the “continuum hypothesis,” but we cannot confirm if it’s true. Remember how Kurt Gödel showed that in every formal system of logic, there are some statements whose truth or falsehood cannot be determined within that system? In 1963, the logician Paul Cohen demonstrated that the continuum hypothesis could not be proven using the standard ZFC axioms of set theory. Some mathematicians believe it to be true, and others do not. Personally, I think there are interesting spiritual implications for both accepting and rejecting the continuum hypothesis. If you think that God created a well-behaved world that we can easily control and understand, then you will probably accept the continuum hypothesis; but if you believe that the world is too large and complex to be understood by our current axioms of set theory, then you will probably reject the continuum hypothesis.
Now we come to the point of this story where I knew I had fallen in love with mathematics completely. My real analysis professor had taken us on a tour of the Hilbert Hotel, had demonstrated Cantor’s Diagonalization Argument, and had opened up the question of the continuum hypothesis, but there was one more thing up his sleeve during those two lectures: the Cantor Set.
Imagine you have the interval from 0 to 1, including its endpoints. Remove the middle third of the interval, leaving the points 1/3 and 2/3. So now you have two intervals of length 1/3, one from 0 to 1/3 and one from 2/3 to 1. Repeat the process to these new intervals: remove the middle thirds, getting four intervals of length 1/9, one from 0 to 1/9, one from 2/9 to 1/3, one from 2/3 to 7/9, and one from 8/9 to 1. Repeat the process on each of these intervals to get eight intervals of length 1/27. And so on, and so on. See the figure:
If you keep removing these middle thirds forever, you are left with a collection of points called the Cantor Set. Notice that the endpoints of the intervals never get removed, so there’s definitely something left over. But it’s not much. After the first step, we removed an interval of length 1/3. Then we removed 2 intervals of length 1/9. Then we removed 4 intervals of length 1/27. Then we would remove 8 intervals of length 1/81. Adding up what we’ve removed gives us
Try adding this in your calculator. Go as far out into the series as you want. You should notice that the more terms you add on, the closer and closer to 1 you get. It turns out that if you add these terms together for every possible value of n, infinitely many times, you get 1. (For my undergrad math friends, you can easily verify this using an infinite geometric series.) So once we’re done with creating the Cantor set, we’ve removed a total length of 1 from the interval from 0 to 1, so the Cantor set has zero length, or zero measure. But the Cantor set is nonempty, as we’ve established (since the endpoints of each interval always remain). So the Cantor set is a spattering of points of total length 0.
What’s the big deal then? Here’s the big deal: the Cantor Set is uncountable.
Yes. This is a set of measure 0 that is uncountably infinite.
How can this possibly be? Another technical explanation is coming up, but again I'll try to make it intuitive. Suppose the number x is in the Cantor set. We’ll create a unique string of 0s and 1s associated to x. If x is between 0 and 1/3, the first number will be 0; if x is between 2/3 and 1, the first number will be 1. Of course, x can’t be between 1/3 and 2/3 because we deleted this interval when we created the Cantor set in the first step. So x is in some interval, either from 0 to 1/3 or 2/3 to 1. In either case, x cannot be in the middle third of this interval; if it’s in the left third of the interval, the second digit is 0, and if it’s in the right third, the second digit is 1. Now if we focus on the third of the previous interval where x lies, we’re in a new interval, of length 1/9. If x is in the left third, the third digit is 0, and if it’s in the right third, the third digit is 1. Now if we focus on the new third-interval where x lies, we’re in a new interval of length 1/27. Keep going, tacking on either a 0 or a 1 on the end of the string of 0s and 1s associated to x.
Example: suppose our number is 1/4. Then it’s between 0 and 1/3, so the first digit of the string is 0. Now, 1/4 is on the right third of the interval from 0 to 1/3, so it lies in the interval from 2/9 to 1/3. So the second digit in the string is 1. Now considering the interval from 2/9 to 1/3, the number 1/4 lies in the left third of the interval from 2/9 to 1/3, so 1/4 lies in the interval from 2/9 to 7/27. So the third digit in the string is 0. See the figure below. Continuing in this way, the string associated to the number 1/4 in the Cantor set is (0 1 0 1 0 1 0 1 0 1 … ).
So every number in the Cantor set can be assigned a unique string of 0s and 1s, and given any string of 0s and 1s, we can find a corresponding number in the Cantor set by zooming in on appropriate third-intervals. This is a bijection. But we’ve seen that the set of all strings of 0s and 1s is uncountable by Cantor’s Diagonalization Argument! It follows that even though the Cantor set has measure 0, it is in fact uncountable.
Conclusion: There are just as many numbers in the Cantor set, a spattering of points of measure 0, as there are in the entire smooth continuum of the real number line.
If that doesn’t blow your mind, I question if anything will.
This was the moment that I fell in love with mathematics: when my real analysis professor at Hamilton proved that the Cantor set is of measure 0 and yet is uncountable.
Here’s why this stuck with me. If I am to believe in God, I must believe that God is a creator of some kind, and if you’ve read my post “The Fall of the Hilbert Program,” you know that I believe that mathematics exists independently of human thought, and so it follows that God created mathematics. I would even take it a step further and say that God created the physical universe through mathematics.
So when I learned about the magical and beautiful properties of the Cantor set, I was stunned. I had witnessed the power of God and the beauty of God’s creation. If God had created a universe with such incredible secrets as the Cantor set, the extent of God’s abilities were magnified for me a thousand fold. Like Paul in the desert when he was Saul, I was shocked and terrified and in awe, and I found myself asking, “Who are you, God? What other secrets are hidden in Your first creation? What else is lying in wait to be discovered?”
Before this, I was premed. My sights were dead-set on medical school. But as I found myself becoming more anxious and frustrated with the biochemistry courses I was taking, I began doubting my commitment to medicine. Over the next couple months after this real analysis lecture, I realized that mathematics was my true passion, and I wanted the world to know.
This real analysis professor of mine had a habit of writing as the last question on each exam, “How’s the course going?” When we took the last exam before the final, I was still debating whether to leave my premed track and my biochemistry major. But there was no denying that my perception of the universe and my understanding of God was transformed by this course. So when the last question on our penultimate real analysis exam asked how the course was going, I answered honestly.
“When I consider all I have learned, and continue making connections from one field of math to another, it serves as a reminder that while humans discover mathematics, we do not invent it. Regardless of whether I continue my mathematical career beyond Hamilton, I leave this semester having come to the following conclusion: that Music is the language of my Angels, and Mathematics is the language of my God.”