How many infinities?

The usual way to decide if one set is bigger than another is to count the elements of both and see which is the higher total. You might have a bag of apples and a bag of oranges, count both, and find there are 20 apples and 17 oranges. But that won't work for infinite sets.

Suppose you have a whole truckload of apples and another truckload of oranges, and you are not confident in your ability to count such large sets accurately. An alternative approach would be to try pairing off each apple with an orange. If you end up with apples left over, you know you have more apples, even if you don't know how many that is.

So let's try that with numbers themselves. Are there more positive integers than even positive integers? You'd think so, because after all, all the odd ones are missing from the second set. But you actually can pair them up:

1 2 3 4 5 6 ... 101 102 ...

2 4 6 8 10 12 ... 202 204 ...

Everything in the first set is paired with something in the second set, and vice versa, so the two sets must be the same (infinite) size. We can use the same trick to show there the same number of positive rational numbers as positive integers. For example, we write the positive integers in ascending order on the top row as before. On the bottom row, we first write all rationals p/q where p and q are at most 1; then all rationals where one of p and q is 2 and the other is 2 or less; then all the ones where one of p and q is 3 and the other is 3 or less, and so on. Here is the pattern we get:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

1/1 1/2 2/1 2/2 1/3 2/3 3/1 3/2 3/3 1/4 2/4 3/4 4/1 4/2 4/3 4/4 ...

Every rational number will eventually appear in the bottom row and will be paired with a unique integer, so there are the same number of positive rationals as positive integers (and we could actually drop the "positive" qualification from either or both sets). This is perhaps surprising, because there are an infinite number of rationals that are not integers, and there are even an infinite number of rationals between any two integers.

So can we extend this further? Are there, perhaps, as many real numbers as integers? No, we can't, and we can prove that by contradiction. Suppose it is possible; then there would be an ordering of all the real numbers so that every real number is paired with a unique integer. I will write the lists vertically this time, showing the real numbers as (infinite) decimal expansions:

1 0.376937295054983...

2 6.592729505859672...

3 3.141592653589793...

4 2.718281828459045...

But here's the clever bit. What if we construct a real number according to the first digit after the decimal point from the first real number, the second from the second, and so on? Here are the digits we'd use:

1 0.376937295054983...

2 6.592729505859672...

3 3.141592653589793...

4 2.718281828459045...

We construct our new number by making sure the first digit after the point was different from that of the first number, the second was different from the second, and so on. For example, we could add 1 to each digit, and use 0 when we got 10. So from the bold sequence above, 0.3912..., we would get 0.4023...

And that number would be different from every number in the list: for every n, it would be different from the nth number in at least the nth decimal place (and probably many more). But we assumed in the first place that all real numbers would appear in the list - so we have our contradiction. There really are more reals than integers (or rationals).

So we have at least two infinities. Is there a limited number of them, or an infinite number? And if it's an infinite number - which infinite number?

Since I'm a careful driver, I'm going to leave it there. But if you sign up for some maths tutoring and want to know the answer, we can explore together, perhaps starting from here. I will, however, point out that you won't come across this stuff until you get to university, so you should probably concentrate on the A-level syllabus for now.