# Monday, June 19, 2017

### A story about infinity

**by Daniel Ranard**

Sometimes it's easier to understand abstract math with a story. When I explain bits of math to unsuspecting friends, I'm always happy by how quickly they follow. Even precise definitions and proofs are easy to learn with a little work. But for the uninitiated, eventually the words and symbols start to slip from the mind, the thread of logic lost in a haze.

That's where a story can help. You don't need plot or character development, just a loose narrative frame. Our brain is a logical powerhouse, but it's used to dealing with people, not abstractions. By casting mathematical notions within a narrative about people with intentions, we're more likely to remember them.

Storytelling is not just a crutch for novices. Some imagine mathematicians are a weird breed, better equipped to deal with symbols than with people. But in my anecdotal experience, experts use stories all the time. It becomes automatic, and the stories shrink to scraps of human narrative: anthropomorphized symbols, definitions imbued with intentionality, proofs framed as struggles. Sometimes a student is lost in the fog of abstraction, only to seize at these imagined human elements and successfully finish an argument. It's a skill to be learned, like so much of mathematical "talent." Eventually, the abstractions may become familiar like friends, no longer requiring the imposition of human costume.

I'll share a story about infinity, dreamed up by the mathematician David Hilbert in a 1924 lecture. It's called the Paradox of the Grand Hotel, or Hilbert's Hotel. Although it's more story-like and less precise than the "stories" I mentioned above, it's a nice introduction to the notion of infinity.

Say you run a hotel – the Grand Hotel – with an infinite number of rooms. The rooms are numbered "one," "two," and so on, without stopping. For any whole number you can think of, there's a room. Unfortunately, all the rooms are occupied when a new guest comes along. How should you direct your new guest? You may be tempted to direct her to "the final room," or "the extra room"; with infinite rooms, surely there's an extra? But you need to hand your new guest an actual room number, and there is no "room at infinity." Sure, there are infinite rooms, and each has its own number, but "infinity" is not one of the room numbers.

With no alternative, you decide to shuffle your current guests. You tell Guest 1 in Room 1 to move to Room 2, and you tell Guest 2 to move to Room 3, and so on. Each guest shifts downward, leaving a vacancy in Room 1, where you direct your new guest.

Let me pause before more guests arrive. I admit that the rules of the game – what it means to have infinite rooms, how we're allowed to move the guests – are not rigorously explained within the story. It may seem like an arbitrary language game, and it is, albeit a game that can be formalized within the logic of mathematics. But hopefully the logic will become intuitive as the story proceeds, even without formal definitions.

Say ten new guests want rooms. Of course, they're easily accommodated: you send Guest 1 to Room 11, Guest 2 to Room 12, and so on, leaving 10 vacancies.

However, now a new batch of guests arrives in a bus. Uh-oh: the bus is infinitely long. The task is to assign every current guest and every new guest some room in the Grand Hotel. Fortunately, the new guests are sitting in numbered seats: Seat 1, Seat 2, etc., but it's not immediately clear how to assign rooms. We are allowed to re-assign current guests, and we'll let everyone switch at once – we won't worry about the frenzied hallway. You can't tell the current guests to shift rooms like before: no matter how far they shift, there won't be enough spots for the infinite busload of new guests. And you can't tell them to shift "infinitely far" either – remember, you only succeed when you explicitly assign everyone a new room number.

I'll let you think about it… okay, here's the trick. First re-assign Guest 1 to Room 2, and Guest 2 to Room 4, and Guest 3 to Room 6, and so on, with everyone moving to double their previous number. That leave vacancies in all of the odd-numbered rooms. Now you fill in spots: assign New Guest 1 to Room 3, New Guest 2 to Room 5, New Guest 3 to Room 7, and so on.

Next, two buses of new guests arrive, each infinitely long. How can we fit them? We could tackle this a few different ways, but here's a trick. It's the same trick we just saw, used twice. First, move everyone from the second bus onto the first, using the earlier trick for moving a single bus into the hotel. At that point, we can just move everyone from the first bus to the hotel.

Now an infinite number of buses arrive, each infinitely long. We can identify each new guest by their location among the buses: "Bus 1, Seat 2," say, or "Bus 5, Seat 3." That way, we provide coordinates to label each guest: in this case, (1,2) or (5,3). For simplicity, let's load all of the current hotel guest onto a new bus. We can even pack them onto the first bus, using our trick. So we still have infinite buses, but now the hotel is empty.

Here's how we unload all the buses into the hotel. We could write down a mathematical formula that assigns each pair (X,Y) to a different room number. That's not too hard to do, but we can also think about it a different way. Again, you need to hand each guest a room number. You start at guest (1,1), and you give her Room 1. Next you need to hand someone Room 2, and so on. Crucially, you need a rule for handing out numbers that guarantees *everyone *will get a number at some point. Here's one example of a rule that works. First take all guests who are on Bus 1 or 2 and sit in Seat 1 or 2. That's four guests total – (1,1), (1,2), (2,1), and (2,2) – so assign them to the first four rooms, in any order. Now take all the guests who are in Bus 1 through 3, sitting in Seat 1 through 3. That's nine guests total, minus the four who you already assigned. Assign them to the next five rooms in the hotel. Proceeding like this, you're guaranteed to find everyone a room, no matter their bus number or seat number.

We've seen that an "infinite number of infinities" – an infinite number of infinitely long buses – can fit into a "single infinity," the infinite rooms at the Grand Hotel. But can we conceive of a larger infinity, a quantity of guests that won't fit in the hotel?

A desperate messenger arrives from another planet. Do you have rooms for all my people, he asks? And he describes his planet: each person lives in a town, and each town is in a country, and each country is in a kingdom… the planet is vastly infinite. Luckily, there are only two people per town, and two towns per country, and two countries per kingdom, and two kingdoms per continent, and so on, but the hierarchy of regions is endless. Each resident has a personal ID, like "2112…," an infinite list of numbers that means the resident is the *second* resident within his town, in the *first* town within his country, in the *first* country within his kingdom, in the *second* kingdom within the continent, etc.

With many clever tricks, you've finally devised a scheme to assign each resident a room. The messenger is worried and suspicious; he's never been able to find an adequate hotel. He starts asking you questions. "Can you tell me the first digit of the ID number of the resident assigned to Room 1?" Two, you say. "Ah, well I have a friend whose ID begins with 1. But now I know he's not in Room 1. Are you sure my friend's been accounted for?" he asks. "Of course," you say, "he's just not in Room 1." The messenger persists: "But can you tell me the second digit of the ID number of the resident you've assigned to Room 2?" The digit is one, you answer. "Ah, well I have a friend whose ID begins with the digits 12. And now I know he can't be in Room 1 *or* Room 2. Is he accounted for?" You assure the messenger that all his friends will be assigned, but you lose confidence. Suddenly you realize: the messenger will always have some friend whose ID number has a different *first* digit from that of the Room 1 assignee, and a different *second* digit from that of the Room 2 assignee, and so on. If the messenger know the N'th digit of the assignee to Room N for every N, he can always find a friend whose ID contains the opposite digits, and that friend won't have a room.

Finally, you're forced to admit that the Grand Hotel won't fit the planet full of residents – you must have made a mistake. Your scheme can't possibly work.

The fact that we can't fit the residents into the hotel is essentially the content of an argument published by Georg Cantor in 1891, called the "diagonal argument." It says that certain infinities (like the number of people on the planet) are so large that they can't fit inside certain other infinities (like the number of rooms in the hotel). Though Cantor's work was controversial at the time, it now lies at the foundation of set theory, which underpins much of modern mathematics. Hilbert said of Cantor's work: "From his paradise that Cantor with us unfolded, we hold our breath in awe; knowing, we shall not be expelled." Cantor, meanwhile, suffered depression and criticism from his contemporaries. Maybe with Hilbert's story about the Grand Hotel, infinity may become a bit more familiar.

Posted by Daniel Ranard at 12:35 AM | Permalink