Introduction
It’s often the case that when people try to reason about infinities, they get lost in forests of paradoxes. More precisely, they stop being able to intuitively make their way around the mathematical landscape. You see, infinity isn’t something we deal with in our daily lives. You could probably argue that we are biologically predisposed to have trouble with it; Scott Aaronson wrote a great article that speaks to this.
A few months ago, while I was TAing a class on ideas in mathematics, I was asked to give one of the lectures. I decided to make it about the basics of infinity and in it, I walked through things like what it means for infinite sets to have the same size, Cantor’s diagonalization argument and some other related items of interest (right out of some of my earlier blog posts). I then talked about one of the famous examples of infinity’s mindbending amazingness: Hilbert’s hotel. The students in the lecture seemed into it, so I told myself after that lecture that I would try to write something about it here… this is that something.
A few people
I run a strangely constructed hotel. It has one infinitely long hallway with countably infinite rooms, numbered 1, 2, 3, 4 and on and on and on. There’s just one problem, though: all of the rooms are occupied and I have a guest at the front desk who wants a room. How might I accommodate him?
(Think about this for a minute… what would you do?)
After much thought and consulting some mathematically oriented consultants, I decided to have everyone move over by 1 room. That is, the person in room 1 moves to room 2, the person in room 2 moves to room 3 and so on. Mathematically, the person in room $n$ moves to room $n + 1$. As is hopefully clear, by doing this, room 1 is now open and, after I get some of the staff to clean it, ready for my new guest. Extending this method further, we can actually accommodate any finite number $k$ of guests by just having everyone move over $k$ rooms. For example, if $k = 78$, we would put the guest currently in room 1 in room 79, the person in room 2 into room 80 etc. This would free up the first $k$ rooms and enable us to accommodate the $k$ new guests.
A caravan
Ok, that wasn’t too bad, and the solution seems plausible enough. A few months later, however, I encountered, shall we say, a bigger problem. A countably infinite number of people came to the desk and said they all wanted rooms. Thinking back to how I accommodated a finite number of guests, I quickly realized that this wasn’t going to work. I can’t exactly ask a guest in room 1 to move to room $\infty$ and the person in room 2 to move to room $\infty + 1$; they’d never stop walking down that hallway! What kind of hospitality would that be?! The only acceptable way to accommodate new guests is one that assign each guest that currently has a room a specific new room… can I do this for an infinite number of guests?
Turns out I can. After consulting my friends again, we decided that the easiest way to accomplish this would be to free up all of the odd numbered rooms. Formally, we would move the guests in room $n$ to the room $2n$. Note that no two guests get assigned the same room; the guest in room 7 is the only guest who ends up in room 14. Observe also that after the move, the only occupied rooms are the even numbered rooms because any room that we moved someone to with our rule is even numbered. Thus all of the odd rooms are open and we can put our guests into the odd numbered rooms.
Why did this work mathematically? I’m going to assume some knowledge of the terminology that follows, but the reason is that the function $f : \mathbb{N} \to \mathbb{E}$ (where $\mathbb{E}$ is the set of even numbers) given by $f(n) = 2n$ (our rule) is actually a bijection (or one-to-one correspondence). This means we can match each natural number with exactly one even number and that every even number gets hit (think about this for a minute; try to convince yourself of this). In some sense, the fact that $f$ is bijective tells us that we can fit $\mathbb{N}$ into $\mathbb{E}$ (which is actually itself a subset of $\mathbb{N}$). Doing this frees up any rooms whose labels aren’t in $\mathbb{E}$, namely the odd rooms. What we’ve actually done here is shown that in a mathematically precise way, there are as many even numbers as there whole numbers… cool, no?
Caravans and caravans
At this point, I thought I was good to go. Now that I know how to accommodate an infinity of guests, what more could I possibly need to know? Turns out, my biggest challenge of them all was yet to come. A few years after solving the infinite guest problem, a countably infinite number of caravans each carrying a countably infinite number of guests showed up and said that all of them wanted rooms. This seemed rather daunting… how was I going to tackle this one?
Well, I said, when the going gets tough, the tough get going. So, naturally, I called my friends again ;) This time, they suggested the following scheme:
- Free up the odd rooms (we know how to do this already).
- Label each caravan with the odd primes in ascending order (there are infinitely many of these, so we’ll have enough for all caravans).
- For each caravan, label the people in it 1, 2, 3, 4 etc.
- Put person $n$ from the caravan labeled $p$ into room $p^n$.
Ok, seems simple enough. But does it work?
To show that it does observe the following few simple facts:
- If $p$ is an odd prime, then $p^n$ will also be odd, so I will never assign a
guest to an even room. - A power of $p_1$ will never contain a factor of $p_2$ (e.g. $5^3$ can’t contain any prime factors except for $5$); this means there is no way that I’ll accidentally assign two people from different caravans to the same room.
- $p^i \neq p^j$ for $i \neq j$, so we see that with this rule, I won’t assign any pair of people from the same caravan to the same room.
Given these three facts, we see that this rule successfully gives all of our guest rooms. It even leaves a bunch of rooms unoccupied! Can you see which ones?
(As a technical aside, we just showed that you can match a set of size $\mathbb{N} \times \mathbb{N}$ — our caravans — with a set of size $\mathbb{N}$ — the odd numbers — in a one to one correspondence. Without going into too much detail, by noting that $\mathbb{Q}$, the set of rational numbers, has size $\mathbb{N} \times \mathbb{N}$, the last leg of our journey is actually a proof of the somewhat surprising fact that $|\mathbb{Q}| = |\mathbb{N}|$.)
Conclusion
It’s been a pleasure taking you through some of my experiences as a hotel manager. As of late, business is booming and I couldn’t be happier. You can bring as many friends as you like and I can almost guarantee we’ll be able to make room for all of you. If you bring uncountably many friends, though, I’ll have to send you to Cantor’s hotel down the street.