Alex's Adventures in Numberland - Alex Bellos [173]
This is how it’s done. Let’s imagine the first arrival has a T-shirt with the expansion 0.6429657…, the second has 0.0196012…, and the receptionist assigns them rooms 1 and 2. And say he carries on assigning rooms to the other arrivals, thus creating the infinite list that begins (remember, each of these expansions goes on for ever):
Room 1
0.6429657…
Room 2
0.0196012…
Room 3
0.9981562…
Room 4
0.7642178…
Room 5
0.6097856…
Room 6
0.5273611…
Room 7
0.3002981…
Room…
0…
…
…
Our aim, stated earlier, is to find a decimal expansion between 0 and 1 that is not on this list. We do this using the following method. First, construct the number that has the first decimal place of the number in Room 1, the second decimal place of the number in Room 2, the third decimal place of the number in Room 3 and so on. In other words, we are selecting the diagonal digits that are underlined here:
0.6429657…
0.0196012…
0.9981562…
0.7642178…
0.6097856…
0.52736b>11…
0.3002981…
This number is:
0.6182811…
We’re almost there. We now need to do one final thing to construct our number that is not on the receptionist’s list: we alter every digit in this number. Let’s do this by adding 1 to every digit, so the 6 becomes a 7, the 1 becomes a 2, the 8 becomes a 9, and so on, to get this number: 0.7293922…
And now we have it. This decimal expansion is the exception that we were looking for. It cannot be on the receptionist’s list because we have artificially constructed it so it cannot be. The number is not in Room 1, because its first digit is different from the first digit of the number in Room 1. The number is not in Room 2 because its second digit is different from the second digit of the number in Room 2, and we can continue this to see that the number cannot be in any Room n because its nth digit will always be different from the nth digit in the expansion of Room n. Our customized expansion 0.7293922…therefore cannot be equal to any expansion assigned to a room since it will always differ in at least one digit from the expansion assigned to that room. There may well be a number in the list whose first seven decimal places are 0.7293922, yet if this number is on the list then it will differ from our customized number by at least one digit further down the expansion. In other words, even if the receptionist carries on assigning rooms for ever and ever, he will be unable to find a room for the arrival with the T-shirt marked with the number we created beginning 0.7293922…
I chose a list starting with the arbitrary numbers 0.6429657…and 0.0196012…but equally I could have chosen a list starting with any numbers. For every list that it is possible to make, it will always be possible to create, using the ‘diagonal’ method opposite, a number that is not on the list. The Hilbert Hotel may have an infinite number of rooms, yet it cannot accommodate the infinite number of people defined by the decimals between 0 and 1. There will always be people left outside. The hotel is simply not big enough.
Cantor’s discovery that there is an infinity bigger than the infinity of natural numbers was one of the greatest mathematical breakthroughs of the nineteenth century. It is a mind-blowing result, and part of its power is that the result really was quite straightforward to explain: some infinities are countable, and they have size , and some infinities are not countable, and hence bigger. These uncountable infinities come in many different sizes.
The easiest uncountable infinity to understand is called c and is the number of people who