Uncountable Infinity and Cantor’s Diagonal Argument

In my last post, I talked about why infinity shouldn’t seem terrifying, and some of the interesting aspects you can consider without recourse to philosophy or excessive technicalities. Today, I’m going to explore the fact that there are different kinds of infinity. For this, we’ll use what is in my opinion one of the coolest proofs of all time, originally due to Cantor in the 19th century.

Background

Last time we talked about sets which have infinite size. In particular, a set S is called countable, if its elements can be paired up with the set of positive integers. This is equivalent to saying that you can find a way to list the elements of S, in such a way that every element comes up eventually. It might initially seem as if every set should be countable, but consider the reals between 0 and 1. If we were to put them in a list, what should the first element in the list be; and what should the second be; and so on? Is it obvious that we can make this work? But if we can’t make it work, how can possibly prove that it is impossible, because there are so many potential ways to list the elements?

The Rationals

As a warm up, consider the rationals: . Is this set countable? For simplicity, let’s just think about the rationals between 0 and 1. What is the most sensible way to list them? What about starting with 0 and 1, then 1/2, then the ones with 3 as denominator, ie 1/3 and 2/3. Can we carry on with strategy? First we need to check exactly what we are doing: we are ordering the rationals by increasing size of the denominator, then within that, by increasing size of the numerator. What about 2/4? That isn’t a rational as we’ve described them, so we can just ignore it.

With this algorithm is that every such rational will turn up eventually. We’ve therefore shown that this set of rationals is countable. It’s hard to give a precise ‘formula’ for how the list works. To work out where 2/11 appears, you need to know about the prime factors of the integers less than 11, and keep track of lots of things. It turns out that 2/11 appears 35th in the list, but the easiest way to deduce this is to check up to that point in the list. The important fact is that it must appear at some point, and only once.

The Reals

Theorem (Cantor): The set of real numbers between 0 and 1 is not countable.

Proof: This will be a proof by contradiction. That means, we will assume that the set is countable, then derive a false statement. From this, we can deduce that the set cannot be countable.

Suppose it is countable. This means we can write all the reals in a list. Write them in binary, so it probably looks something like this:

0.00001011001...
0.11001011100...
0.01011101101...

and so on. Now, highlight the first digit of the first element in the list, the second digit of the second element, as shown:

0.00001011001...
0.11001011100...
0.01011101101...

Now assemble a real number from all the highlighted digits:

0.010...

Then, suppose you reverse all the digits. That is, after the point, you turn 0s into 1s, and 1s into 0s:

0.101...

Let’s call this real number x. It is between 0 and 1, and so it must appear in the list. Suppose it appears at position n in the list. But we know, based on how we constructed x, that the nth digit of x is different to the nth digits of the nth element in the list. So this is a contradiction. The only conclusion can be that such a list of the reals does not exist!

So, we have our first uncountable set.

Technical Remark: This isn’t hugely important, but this proof cuts one corner. Like decimal expansions, the binary expansion isn’t always unique. As 0.999…= 1 in decimal, in binary for example 0.1000…= 0.01111… But this only happens when the real number in question is in fact rational, and has denominator a power of 2. It isn’t too hard to fix this problem, because the set of reals for which this is a problem is small, but it requires some technical steps that would distract from the elegance of the main thrust of the proof.

Advertisement