The sizes of infinity

Last week a student visited the Drop-In Centre to talk about the different sizes of infinity. His lecturer had been talking about the sizes of sets and had made an off-hand comment that there were different sizes of infinite sets, and he wanted to know what the hell that meant.

So I explained it. It's not the simplest explanation, because you have to define some new ideas in order for it to make sense. But it is one of my favourite things about the families of number that some are the same size and some are different sizes, even though they are all infinite.

So I want to explain it again here...

The key to the whole thing is to realise that when talking about infinite sets, that counting is not really a useful way to find the sizes of sets. When you have a lovely finite set, such as the letters in the word "sluiced", you can simply count the members of the set and you know how many there are (7 in this case). But the process of counting works because at some point you stop, and the number you're up to is the number of objects there are.

But what if you can't stop? If your set has infinitely many objects in it, you'll never get to a final number where you can stop and say "this is how many". We need a new way to talk about the sizes of sets, and the way that we use is in some sense even more fundamental than counting.

If you had two piles of things and were asked which pile has more, you'd probably count both and whichever had the bigger number would be bigger. But there's another way: you could pair them off, one object in each pile, and if one pile runs out before the other one does, then you know that the other pile must be bigger. And if you are able to pair off everything in both piles, you know they must be the SAME size. THAT is the solution to our problem.

We DEFINE that two sets are the same size when you can pair them off exactly. That is, there is some way to attach to each object in Set 1 a different object in Set 2, and in this way to cover all the objects in Set 2. If this is impossible, then the two sets are different sizes.

So let's look at the five families of number: the natural numbers, the integers, the rational numbers, the real numbers and the complex numbers – N, Z, Q, R and C. (Actually I'm going to ignore C, sorry.)

The natural numbers, being the set of numbers {1, 2, 3, 4, ...}, is what most of us think of when we think of an infinite set. We start counting how many objects it has, but we can never stop because the numbers don't stop. So we have infinitely many. But it's quite close to the finite sets, because we can at least try to count them. They call the size of N the countable infinity.

Now let's compare the sizes of N and Z. If they were the same size, it would be possible to find a way to line them up next to each other. That is, you could find one integer to call 1, one to call 2, one to call 3, and so on in such a way that you cover all the integers.

Well, look at this:
1 ↔ 0
2 ↔ 1
3 ↔ -1
4 ↔ 2
5 ↔ -2
6 ↔ 3
7 ↔ -3
etc

We have given every integer a different natural number and covered all the integers and all the natural numbers, so by our definition, this means that N and Z are the same size.

Cool huh?

What about N and Q? Well, if they were the same size, we'd be able to line them up next to each other like with N and Z. This time the trick takes two steps.

First we'll consider just the positive rational numbers. I need a way of organising them into a list so that I can line them up next to the natural numbers and cover all the rational numbers. Well, the denominator and the numerator of a fraction must add to something, so why don't I organise them into the ones that add up to 1, the ones that add up to 2, the ones that add up to 3 etc. Within each of them, I can organise them in order of the numerator. So if I do this I'll get a list like this:

1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 2/4, 3/3, 4/2, 5/1, etc

Of course, I've included some of them twice (since for example 2/2 = 1/1 and 2/4 = 1/2), so I'll just remove those ones:

1/1, 1/2, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 5/1, etc

And now I have a neat list of all the rational numbers with a clearly-defined way of getting to each of them. Now I'll line them up with the natural numbers:

1 ↔ 1/1
2 ↔ 1/2
3 ↔ 1/3
4 ↔ 3/1
etc

In this way I can cover all of the rational numbers exactly once, so by our definition, this means that N and the positive numbers in Q are the same size.

But now we can do the same trick we did with Z. We've got a list of positive rational numbers, and a list of negative ones (and 0 as well) and we'll just start with zero and flip-flop between the positive list and the negative list and we'll be good:

1 ↔ 0
2 ↔ 1/1
3 ↔ -1/1
4 ↔ 1/2
5 ↔ -1/2
etc
So N and Q are the same size.

But what about N and R? I'd need to think of a way of putting R into a decent order so I can line it up next to N. I can't think of a good way, but just because I can't, it doesn't mean it's impossible – I'll only know for sure it's impossible if I prove it. And the best way to prove that something is impossible is to pretend you've done it and try to show that this concept is stupid – that is, a proof by contradiction.

It's way too hard to do this with all the real numbers, so I'll just look at the ones between 0 and 1. All these numbers (except 1) will be "0.something", and the "something" is a decimal expansion which may stop or may go on forever. For those that don't go on forever, we'll just say that it is infinite, but all the digits at the end are zeros. So we can represent each of the numbers from 0 to 1 as "0.something", where the something is an infinite string of digits. (For the pedants, I'm ignoring here the possibility of having a number ending in an infinite string of 9's.)

Suppose we managed to line them up next to the Natural Numbers like this:

1 ↔ real number
2 ↔ real number
3 ↔ real number
etc

All these real numbers have a decimal expansion, so let's write down what that might look like:

1 ↔ 0 . d11 d12 d13 d14 ...
2 ↔ 0 . d21 d22 d23 d24 ...
3 ↔ 0 . d31 d32 d33 d34 ...
etc

Supposedly, we have covered all the numbers from 0 to 1 in this way. I'm going to show that in fact we haven't covered all of them, by making a new number that's not in the list we have.

Look at the first digit in the first number: d11. Let's pick some digit different to d11 and call it a11. (We should probably have a rule that says how to pick this different digit – let's say that if d11 isn't zero then we'll pick a11 = 0, but if d11 is zero we'll pick a11 =1.)

Now look at the second digit in the second number: d22. Again we'll pick a22 so that it's different to d22. And we'll continue this process for d33, d44, and so on.

Consider the number 0.a11 a22 a33 ...

This number is not equal to the first number in our list, because its first digit is different. It's not equal to the second number in our list, because its second digit is different. It's not equal to the third number in our list, because the third digit is different. And so on. So our new number can't be equal to any of the numbers in the list! So we didn't cover all of the real numbers from 0 to 1 after all. But even if we include this number in the list, the same argument would show that there would always be at least one more, so the set of real numbers from 0 to 1 is not a countable infinity. Since the Real Numbers are bigger than just this little section, they can't be a countable infinity of numbers either.

So in a very real sense, the Real Numbers are bigger than the Rational Numbers, which means we have at least two different sizes of infinity!