In my post about the countability of the rational numbers, I said that I’d come back to the topic and prove that the real numbers are uncountable. That’s the plan for today. If you’re not familiar with the definition of countability, please read that post first: this really is part two of that post. I may as well state the theorem immediately, and then we’ll think about what it actually means.
Theorem The real numbers are uncountable.
What does this mean? It means there’s no way of listing the real numbers (we saw last time that saying that a set is countable is the same as saying that the elements can be written in a list). So our aim is to prove that it’s impossible to do something (write the real numbers in a list). How could we possibly do that?
We’ve had a previous example of a proof that something is impossible, when we saw that the square root of 2 is irrational. That is, we showed that it’s impossible to write as the ratio of two whole numbers. There, our strategy was to use proof by contradiction. We supposed that it is possible to write as the ratio of two whole numbers, and we went on to derive a contradiction from that: we got to something that was simply absurd. That meant that the square root of 2 couldn’t possibly be rational, so it must be irrational.
We’re going to use a similar sort of strategy here. We’re going to suppose that it is possible to list the real numbers. Then we’ll somehow derive a contradiction from that, which will mean our original supposition must have been wrong. That is, we’ll have shown that it’s impossible to list the real numbers. Let’s go!
So, we’re supposing that we can list the real numbers. In that case, we can certainly list the real numbers between 0 and 1. Let’s imagine that we’ve done this, and we’ve written them all out in order, using their decimal expansions. (Slightly annoyingly, some numbers have two expansions, since 0.99999999999999… = 1, but let’s say we always write the finite version rather than the one ending in infinitely many 9s.) So they look something like
Our plan is to derive a contradiction. How are we going to do that? We’re going to build another real number between 0 and 1, one that isn’t on our list. Since our list was supposed to contain all such real numbers, that will be a contradiction, and we’ll be done. So let’s think about how to build another real number between 0 and 1 in such a way that we can be sure it isn’t on our list. Let’s say this new number will be , where we’re about to define the digits .
We want to make sure that our new number isn’t the same as the first number on our list. So let’s do that by making sure they have different numbers in the first decimal place. Say if then and otherwise . (I really mean: define to be any digit apart from , but I want to make sure that we don’t get a number that ends in infinitely many 9s, because of this irritating fact that 0.99999999999999… = 1, so I want to make sure we never choose to be 9.)
Now we want to make sure that our new number isn’t the same as the second number in our list. We can do this by making sure that the second digit of our new number isn’t the same as the second digit of the second number. So let’s put if and otherwise.
And so on. At each stage, we make sure that our new number isn’t the same as the th number on the list, by making sure that isn’t the same as .
And that defines our new real number, one that is definitely not on our list (because we built it that way)!
The argument we have just used is called Cantor‘s diagonal argument, because we worked our way down the diagonal. It can be used in other proofs of uncountability too; the Wikipedia page talks more about this.
Having seen that the reals are uncountable, I think that two natural questions come to mind. One is to ask how many reals there are, and the other is to wonder whether there are still larger sets (in the way that the set of reals is larger than the set of naturals). Thinking about the second of those first, there certainly are still larger sets. In fact, it turns out that for any set , the set of all subsets of is bigger than . (Wikipedia calls this Cantor’s theorem. It can be proved using a version of the diagonal argument that we’ve just seen.) So the set of all subsets of the reals is larger than the set of reals, and the set of all subsets of the set of all subsets of the reals is larger than the set of all subsets of the reals, and so on. This gives an infinite chain of larger and larger infinities! There’s a theory of cardinal numbers to help describe this sort of thing.
Returning to the first question, how large are the reals? Are there any infinite sets that are larger than the naturals but smaller than the reals? The continuum hypothesis says there aren’t, but, remarkably, it turns out that this statement can neither be proved nor disproved using the usual axioms of mathematics. Fascinating stuff, but this post is getting too long so I think I’m going to stop here!