So Cantor started to think. Hilbert's hotel had an infinite amount of rooms, each denoted by its own room number. The first was number 1, the next number 2, and so on — all the way to infinity. Basically, there was a room for every possible positive (whole) number. How could he design more rooms than that? Hmmm... what if, maybe, his hotel was to include rooms for all negative numbers as well? A list of all rooms would then go on indefinitely in both the positive and the negative direction! Surely he would then have twice as many rooms as Hilbert did.
Cantor soon realized it was not going to be that easy. Infinity times two? That's still infinity. Just arrange the rooms so that you can match them, and you'll see:
| Cantor's Room Number | 1 | -1 | 2 | -2 | 3 | -3 | 4 | -4 | ... | ∞ |
|---|---|---|---|---|---|---|---|---|---|---|
| Hilbert's Room Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... | ∞ |
The idea sounded good at first, but the above shows that Hilbert's hotel would still be able to house every potential guest in Cantor's hotel. It doesn't matter if you change the labels on the doors; the number of rooms is still infinite.
Let me elaborate on this. If in the hotel the room numbers can be matched to the counting numbers, then infinity is still infinity. There is no such thing as ‘half’ infinity or ‘double’ infinity. So even if you only count the odd (or even) numbers, or if you include the negative numbers in your count, it doesn't matter. All three methods result in the exact same total number of rooms.
| Room Number | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | ... | ∞ |
|---|---|---|---|---|---|---|---|---|---|---|
| Room Number | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | ... | ∞ |
| Room Number | 1 | -1 | 2 | -2 | 3 | -3 | 4 | -4 | ... | ∞ |
| Running Count | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... | ∞ |
Since Hilbert simply had as many rooms as one could count, Cantor's hotel would not be bigger after all. He had to think of something else.
It slowly dawned on him that using whole room numbers would never be enough. There was always a method to make that fit. But there had to be a way to beat Hilbert. And then it hit him. Fractions!
Thanks to fractions, for each pair of adjacent rooms in Hilbert's hotel, Cantor could design extra rooms in between. For example:
- between room number 1 and room number 2 would be room number 1/2;
- and between 1 and 1/2 would be 1/4;
- and between 1/4 and 1/2 would be 3/8...
Slam dunk, right? So Cantor started working on a floor plan... and soon found that once again, this would not work. Fractions too, can be counted.
Then all you have to do is leave out repetitions (fractions that represent the same number), and voilà, there's your count. Like so.
| Room Number | 1/1 | 2/1 | 1/2 | 1/3 | 3/1 | 4/1 | 3/2 | 2/3 | 1/4 | 1/5 | 5/1 | 6/1 | 5/2 | 4/3 | 3/4 | 2/5 | … | ∞ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Running Count | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | … | ∞ |
If Cantor built his hotel with fractional room numbers, the net amount of rooms would still match the amount of rooms in Hilbert's hotel. This was infuriating. What else was there to do, decimal numbers? Those can have a complete variable number of digits after the decimal point. But would that make any difference compared to fractions, which can also easily be written as decimal numbers?
Cantor set himself to the task to find out whether decimal room numbers would finally deliver more rooms. So. The question is: can you count all the decimal numbers? Cantor decided that if one could, it would be a list just like the ones encountered before. Let's take a random snippet of such a hypothetical list (rotated for clarity):
| Running Count | Room Number |
|---|---|
| 576209190832 | 1.36073572132490832... |
| 576209190833 | 9.38534872398735293... |
| 576209190834 | 4.26264790710702356... |
| 576209190835 | 7.10985423987690371... |
| 576209190836 | 2.31287985691084908... |
| 576209190837 | 1.10910547667218755... |
The numbers after the decimal point go on forever. Now imagine that every possible decimal number is on this list! That for one would prove that decimal numbers can be counted in the same way as fractions and whole numbers can.
But as Cantor soon found out, there was a catch. He could in fact generate a number that was not on the list.
Simply start at the top number and at its first decimal digit. Change that digit into something else: in this case let's change the 3 into a 4. Write down the 4 and move onto the second number and its second decimal digit. Once again change the digit and write it down. Let's say we increase this one as well so the 8 becomes a 9. Continue onto the third number's third digit, and so on. From the above sample, we could have generated the following number:
0.493986... (going on forever)
Now here's the thing. This number will not be on the list. It can't be the first number because it has a different first digit. It can't be the second number because it has a different second digit. It can't be any of the other numbers, because for each one there's a digit we changed. And what this means is that a list of all decimal numbers can never be constructed. And if no such list can be constructed, its entries cannot be counted. The imaginary list of decimal numbers is uncountable.
To summarize:
- Hotel Natural: An infinite hotel with only whole, positive room numbers. Since each of these match up one-to-one with the counting numbers, its rooms can be counted.
- Hotel Integer: An infinite hotel with both positive and negative (whole) room numbers. It has just as many rooms as Hotel Natural. It is not twice as big as Hotel Natural, it is the same size.
- Hotel Rational: An infinite hotel with fractional room numbers (a division between any two whole numbers). Yet it too has the same number of rooms as Hotel Natural. And it too is the same size!
- Hotel Real: An infinite hotel with decimal room numbers. This hotel has many more room numbers than Hotel Natural. So many, that its rooms cannot be counted. And while intuitively it would not seem much bigger than Hotel Rational, it is in fact far, far bigger in size.
Cantor was pleased. He had finally got it. The idea looked great on paper. Unfortunately the actual building part, he eventually decided, was too impractical. For starters, he could only acquire a countably infinite number of bricks.
Author's note: You should definitely read this excellent explanation, which surely helped me understand this stuff, and no doubt subconsciously provided the underlying basis for this post.
Change the first three "much"es into "many"s. Since this article is talking about counting things, you need to use the adverb that describes counting nouns ("rooms" is a counting noun, since you can count them, as opposed to "vacancy", which refers to an unspecified amount of space not being used, like empty rooms). For instance, you can have a hotel with many rooms, or a hotel with much vacancy. It is directly tied to the less/fewer rule. Hilbert's hotel can have fewer rooms than Cantor's, with less vacancy in it. Never will it have less rooms, since you can count rooms. "Fewer" is used with count nouns. "Less" is used with mass nouns, talking about abstract quantities that cannot be counted, such as vacancy.
ReplyDeleteAnd who says language arts and mathematics never cross paths? Not me!
Very observant! Indeed that's lot better. I updated it, thanks!
DeleteAnd once Cantor's Hotel was finally built, the two hoteliers started to wonder: of course there can be an even bigger hotel than Cantor's. But can there be a hotel with a number of rooms in between the two? They thought about it day and night, and weren't able to find an answer; finally, many years later, it has been discovered that there's in fact no answer. It can be assumed that there is such a size (cardinality), and this doesn't lead to a contradiction (as long as the set theory axioms themselves are consistent). But likewise, it is possible to assume that no such size exists, and this doesn't lead to a contradiction, either.
ReplyDelete