Infinity is a concept that grabs the human imagination. There is something both fascinating and futile about the realisation that no matter how large a number you think of, there is always a larger one. You can never, ever reach the end.
So here is an amazing fact: infinity comes in different sizes. Not all infinities are created equal.
Intrigued? So was the mathematical world when this first was discovered and made plain by the German mathematician Georg Cantor in the 1870s. In fact, some were outraged. Leopold Kronecker, another prominent mathematician of the day, called Cantor a “corrupter of youth” for teaching his ideas.
So now that there is a hint of scandal in the air, let’s take a look at how Cantor proved that there is an infinity larger than infinity. To do this, we need a couple of easy definitions.
The counting numbers are the numbers 1, 2, 3,… and so on that we count with.
The real numbers are the set of all decimal numbers. This includes numbers like 1.000, 0.25 and also numbers like 5.3333… or 3.1415… that never terminate. (The three dots indicate that these decimals go on forever.)
There are an infinite number of counting numbers. If you think you have the largest number, you can simply add 1 to it to get an even larger number.
It’s not too hard to see that if there are an infinite number of counting numbers, then there must also be an infinite number of real numbers, because the counting numbers are contained within the real numbers.
The shocking, youth-corrupting result that we are going to get to is that there are actually more real numbers than there are counting numbers. But in order to understand that in all its scandalous glory, we will need to do a couple of other things first.
First, let’s think about how we can know that two sets of things have the same number of things in them, even if we don’t know what that number is. For a moment, imagine that instead of being who you are, you are a shepherd in ancient Sumeria. It’s so far back that people haven’t really worked out numbers yet, so you know that you have some sheep but you can’t say how many. However, you have a need to make sure that all your sheep are present and accounted for. So what do you do? You put notches in your stick, one notch for each sheep. Then you know that if you have one sheep for each notch, then they are all there. You aren’t sophisticated enough to give a name like “seventeen” to the number of sheep you have, but you have enough information to do the job that you’ve set out to do: keep track of your sheep.
This technique is called “one-to-one correspondence”, and all it means is that if you can match up the things in one set (notches) with the things in another set (sheep) so that there is one notch for each sheep, then you have the same number of sheep as you have notches, whatever that number might be.
Luckily for ancient Sumerian shepherds, sheep do not come in infinite numbers. But we’ve moved on a bit since then, and now we must think about how we use one-to-one correspondence to convince ourselves that two sets that are infinite have the same number of things in them.
For this, we’ll need two infinite sets. Set A will be the counting numbers, that is 1, 2, 3,… and so on. Set B will be the even counting numbers, that is 2, 4, 6,… and so on. Now since we are talking about different sizes of infinity, you might think that the number of counting numbers would be larger than the number of even counting numbers… after all it seems obvious that there are half as many even numbers as numbers!
One thing that you will very quickly realise when thinking about infinity is that what seems obvious is often wrong. Actually, the number of even counting numbers is the same as the number of all counting numbers. To convince ourselves that this is true, we need to go back to the notches and sheep; that is, we need to show that there is a one-to-one correspondence between these two sets.
So if we take any counting number (the notch) and multiply it by 2, we get an even counting number (the sheep.) If we take any sheep (even counting number) and divide it by two, we get a notch (counting number). What’s more, by doing this we can flip back and forth between notches and sheep, and in fact we find that there is no notch without a sheep, no sheep without a notch, and moreover there is no sheep that has more than one notch, and no notch that has more than one sheep. So despite that fact that your intuition may tell you that in some way there must be somehow fewer even counting numbers than counting numbers, we’ve shown that there are the same number of each.
A set is often referred to as countably infinite if it can be put into one-to-one correspondence with the counting numbers. We have just shown that the even counting numbers are countably infinite.
Now we finally come to the youth-corrupting dangerous idea: The real numbers are not countably infinite, and cannot be put into one-to-one correspondence with the counting numbers!
One way to convince yourself that a statement like that is true is to assume the opposite and show that you get a contradiction. We did this earlier to convince ourselves that there are infinitely many counting numbers. Assume the opposite, which is that there is a largest counting number. But if there is a largest one, then I can add 1 to it, and make a larger one, so it is not the largest one. Contradiction! My assumption (that there is a largest one) must be false.
So, let’s assume that there is a one-to-one correspondence between the real numbers and the counting numbers. Now we’re going to try to get to a contradiction.
If there is a one-to-one correspondence between them, then we can write a list of counting numbers and the real numbers to which they correspond- to each notch a sheep and to each sheep a notch.
Now remember that whereas counting numbers are nice and neat 1, 2, 3,… and so on, real numbers are more cumbersome beasts that stretch on to infinity and look like 3.14159… So our list is going to look something like this:
1 0.7639234…
2 0.3238452…
3 0.2498539…
etc.
The decimal expansions go on forever off to the right (filled with zeroes if need be) and the list goes on forever downwards. Two dimensions of infinity rather than one… perhaps a whiff of scandal hangs in the air.
Now what follows is one of the most beautiful proofs in mathematics. Like a beautiful piece of music, you can revisit it time and time again and appreciate it’s elegance, simplicity, logic and brilliance.
Remember, we said that we have a one-to-one correspondence between the counting numbers and the real numbers. Our goal is to show that this leads to a contradiction.
Let’s construct a real number using the list that we have written above. For this real number, I’m going to put a 0 to the left of the decimal place and fill the right positions as follows: for position 1, I’m going to take the digit 1 position to the right of the decimal in the real number corresponding to counting number 1. For position 2, I’m going to take the digit 2 positions to the right of the decimal in the real number corresponding to counting number 2. Doing this gets you a diagonal pattern like this, where the digits I choose are marked by parentheses.
1 0.(7)639234…
2 0.3(2)38452…
3 0.24(9)8539…
etc.
Now I’m going to do something to each of the digits. It doesn’t matter what I do as long as I change each and every digit to the right of the decimal in the number that I’ve constructed. Let’s say that we add 1 to each digit, and if it’s a 9 then we replace it with 0.
Now, cover the kids’ ears, here it comes: The number that I have constructed does not exist in the one-to-one correspondence that I assumed! How do I know this? Well, it isn’t the number that corresponds to 1, because the first digit after the decimal is different. It isn’t the number that corresponds to 2, because the second digit after the decimal is different. I think you can see where this is going, my friend, and we have a sheep without a notch!
You may think that this is not a very bad problem, we’ll just tack this rogue sheep onto the end of the list, thus repairing the one-to-one correspondence. But you cannot get away with that, because you can do the same thing again, producing a new number that is not included in your list. The problem does not go away; we have more sheep than notches. We have derived a contradiction and our assumption must be false.
The real numbers are not countably infinite, they are uncountably infinite, and we have a new order of infinity that is more infinite than the counting numbers.
