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. Continue reading →