Diversions in Mathematics #2: Hilbert’s Hotel

In this instalment, I introduce the concept of infinity in a simple and (hopefully) entertaining way, which puts into practice the counting concepts introduced in the previous Diversion. In fact, Hilbert‘s infinite hotel was one of the ‘stories’ that got me seriously interested in mathematics in the first place, and so it is a pleasure to share it here. This is a very well-known piece of story-driven mathematics. I hope that experienced mathematicians who happen to come across this blog do not tire of hearing (reading) it again, and that they see the value in telling the story to the general public.

Just before we start: I assume knowledge of the definitions and notations introduced in the previous instalment, namely, the very basics of set theory.

In the previous part, we looked at two of the most fundamental objects in all of mathematics: numbers and sets. We ended with the inductive definition of the natural numbers, which consisted of a pair of statements:

  • 0 is a natural number
  • If n is a natural number, then n + 1 is also a natural number

We concluded that infinity is a consequence of this definition, and proved it via a simple contradiction argument: suppose that there is a “largest natural number” N, then by the inductive definition, N + 1 must be a natural number, but this is larger than N. So there is no such “largest natural number”; in other words, the set of natural numbers is infinite.

Before we begin our visit to Hilbert’s Hotel, an important definition to know is the following:

Definition 2.1

The cardinality of a set X is the number of elements in X. It is denoted |X|.

Informally speaking, cardinality is simply the size of the set. For example, if X = {1, 3, 6, 10}, then |X| = 4. If X is the set of all letters of the English alphabet, then |X| = 26.

How do we know this? This seems like a trivial question, but only because we take something very important for granted. Indeed, we were able to compute the cardinalities in the examples above quickly because we can count the number of elements, and counting is inextricably linked to the natural numbers. The importance of this is reflected in the very language that mathmaticians use — this will become clear later! I mentioned in the previous Diversion that the indigenous Australian language Warlpiri can only make a distinction between “one” and “two”, and all quantities greater than two can only be described as “few” or “many”. Nevertheless I imagine that a Walpiri person could still tell which of the following sets contains more elements:

setsab

They could simply take one element of A and match it with some element of B. At the end of this procedure, they will notice that B has “a few” elements with no partner from A, and hence conclude that B contains more elements. This is a seemingly innocuous exercise, but it introduces the concept of a mapping — a relation between sets. In fact, I think I should now introduce the following enormously important definition:

Definition 2.2a

A function or mapping is a relation from one set A to another set B, such that every element of A is uniquely assigned to an element of B. We write:

f: A → B

The set A is then called the domain, and B is the codomain.

If the element a ∈ A is mapped to the element b ∈ B, we denote this:

f(a) = b

Informally, a function is a rule for assigning elements of A uniquely to elements of B. (In high school, we almost exclusively study functions which have a nice, simple formula, but this is not necessary). The “uniquely” bit is very important. Here is an alternative definition (taken, with a slight adjustment, from Michael Spivak’s textbook Calculus, 3rd ed.) which emphasises this point:

Definition 2.2b

A function is a collection of pairs of objects with the following propery: if (a, b) and (a, c) are both in the collection, then b = c.

Using the notation in first definition, this means that if f(a) = b, and f(a) = c, then necessarily b = c. In the diagrams below, the left hand side is a representation of a function, while the right hand side is not, since one of the red dots is mapped to two different elements of B. Notice that not everything in B needs to be paired with something in A.

function_or_not

We also allow elements of B to correspond to multiple elements in A. This actually happens quite a lot: for example, take the function defined by squaring a number, f(x) = x^2. For simplicity, we take both the domain and codomain to be the set of integers, \mathbb{Z}. Then f(3) = 3^2 = 9, and also f(-3) = (-3)^2 = 9, but of course 3 is not equal to -3, despite both being mapped to 9. There is also the trivial example of a constant function, for example: f(x) = 5. For any input value x, the function outputs the number 5 — a perfectly legitimate but otherwise boring function.

  • Thinking time: The image of a function f: A → B is the set im(A) = {f(a) | all a in A}, i.e. the set that you get from applying f to everything in A. (This is also called the range of f ). In the example above, we have f: \mathbb{Z} \to \mathbb{Z}, f(x) = x^2. What is the image of f? Is it the same as the codomain?

OK, with this important knowledge in mind, let’s visit Hilbert’s Hotel!

hilbert_hotel

As you approach the Grand Hilbert Hotel, you are astounded by the magnificence of the building, and cannot wait to check-in to your room and relax. Its location is ideal for your vacation — nestled in a lush Bavarian forest, yet only a pleasant half-hour walk to the banks of the Obersee. Moreover, it was advertised as being infinitely spacious. You had initially thought this to be a strategic exaggeration for marketing purposes, but walking up to the front entrance now, you think perhaps you were too quick to judge.

Just as you are about to step into the revolving doors, you notice a large sign displaying: NO VACANCY (Please enquire within). Unbelievable! Your room had been confirmed some days ago, surely there could not have been a double booking? “So much for ‘infinitely many rooms’,” you grumble as you ring the bell for reception. Within seconds, an elegantly dressed, bearded man with spectacles emerges from the office behind the reception desk. You notice his nametag: Bernhard Riemann, concierge. He speaks quietly, yet somehow with great authority: “Guten morgen, how can I help?” You indicate to the “No Vacancy” sign outside, and ask about your room.

“Ach ja, we are operating at full capacity. But that is no problem! We can certainly accomodate you today, but please wait a little, as I will have to organise for some guests to move around…” Slightly impatient, you interject: “Wait, sir, just how many rooms do you have?”

“Why, we have countably infinitely many! Just as it says on our brochures.”

Countably infinite? How can something be infinite and countable? But you suspend your disbelief for now, as Riemann is rummaging through a pile of papers. He produces a form for you to sign.

“Here you go, I will put you into room 1. It is not the room you booked, but you know how it is, many of the rooms are the same up to isomorphism. And room 1 does have a nice view of the Obersee, as you requested.” 

While you did not understand exactly what was meant by “isomorphism”, nevertheless something has aroused your curiousity. “Herr Riemann, let me get this right,” you enquire, “the hotel is full, but you can accommodate me… just by moving people around?”

“Exactly right. I guess that means Mr. Ramanujan will finally be able to move into room 1729, he should be happy about that!”

Your expression must have betrayed your confusion, as Riemann continues:

“It is a simple affair, my colleague Georg Cantor has devised an excellent procedure to solve such problems. Our hotel contains countably infinite rooms, that is, the number of rooms is the same as the cardinality of the natural numbers. Today we are completely full, so every natural number has been assigned to a guest. But if a new guest arrives, we can simply ask the guest in room x to move to room x + 1. So, the guest formerly in room 1 will move to room 2, and the guest originally in room 2 will move to room 3, and so on ad infinitum, giving you a vacant room 1. Is this not ingenious?” he remarks proudly.

We have just heard from Mr. Riemann the concept of a set being countable. Of course, you know already that any finite collection of things can be counted, but you see now that an infinite set can also be countable!

Definition 2.3

A set X is countable if either:

  • X is a finite set, or
  • |X| is the cardinality of the natural numbers

In the latter case, X is said to be countably infinite.

This is why I wrote earlier that counting is inextricably linked to the natural numbers. Actually, this definition is not quite complete (which is why I haven’t put it in a box). To complete it, let’s analyse how you were able to be accommodated at the Grand Hilbert Hotel, despite it being full. We will put into practice our knowledge of functions! (Note: there is some discrepancy amongst mathematicians whether or not zero belongs to the natural numbers. The following discussion should convince you that this discrepancy does not matter).

Consider the natural numbers \mathbb{N} = {1, 2, 3, …}. This set is also the set of all room numbers at the Grand Hilbert. Initially, before you arrived at the hotel, all the rooms were occupied, so that tells us there were | \mathbb{N} | guests. Now add yourself to the set — for reasons which will be clear very soon, let’s assign you the number zero. So now we need to map the set of guests X = {0, 1, 2, 3, …} to the set of room numbers \mathbb{N} = {1, 2, 3, …}. Can you find a simple rule to do this?

Indeed, the rule that Riemann described is the simplest solution. Let f: X \to \mathbb{N} be a function, and define for every x \in X, f(x) = x + 1. Then you can see that f(1) = 1 + 1 = 2, f(2) = 2 + 1 = 3, and so on, exactly as Riemann stated. In particular, you have been assigned to room 1, or in our function language, f(0) = 1. This function has mapped the set X to the natural numbers, and there is no element left out in either set. Every element in X has a unique partner in \mathbb{N}, and vice versa — that is, every element of the codomain corresponds to a unique element in the domain. This is a special kind of function, called a bijective function, or bijection (or the delightfully clumsy “one-to-one and onto function”). In particular, it tells us that the cardinalities of the two sets are the same! This was probably obvious to you for finite sets — you know when two sets contain exactly 10 elements, for instance — but now we have defined the notion of “same size” for two infinite sets. So let us now complete the definition above:

Definition 2.3

A set S is countable if either:

  • S is a finite set, or
  • |S|is the cardinality of the natural numbers, i.e. there exists a bijection from the set S to the natural numbers.

In the latter case, S is said to be countably infinite.

Here’s where the weirdness of infinity becomes apparent. Intuitively you might think that the set X is “larger” than \mathbb{N}. Indeed, X actually contains all of \mathbb{N}, since X has the element 0 in addition to {1, 2, 3, …}. We can write X = \mathbb{N} \cup \{0\}. But since we have found a bijective function X \to \mathbb{N}, this shows that the two sets have the same cardinality — the same size! We can in fact do better. Suppose you bring along n – 1 other friends on holiday, so you have n people checking in. Then Herr Riemann can simply ask the guest in room x to move to room x + n (for all x = 1, 2, 3, …), leaving the rooms 1 to n vacant. This is another bijective function from the set of guests to the set of rooms, and once again, everyone is happily accommodated. Loosely speaking, as long as n is a finite number, you can “add” n elements to the natural numbers, and its cardinality remains the same! This is the reason why infinity cannot be a number. If you treat it like a number — let’s use its proper symbol, ∞ — it makes no sense to write something like “∞ + 127 = ∞“. There is nothing wrong with infinity or 127 for that matter, but rather, the operation “+” becomes meaningless. However, in the language of sets and functions, there is no problem. Take the set \mathbb{N}, and another set X containing 127 elements, and then you can certainly construct a bijection \mathbb{N} \cup X \to \mathbb{N}, and thus, |\mathbb{N} \cup X| = |\mathbb{N}|. You can now also appreciate why mathematicians insist on precise, rigorous definitions of the objects we study.

  • Thinking time: Can you see why subtracting a finite number of elements from \mathbb{N} also does not change its cardinality?

“Ah yes, I see how it works!” you remark.  “As long as a finite number of new guests arrive, you can always shift along the existing guests by the appropriate number?”

“Well observed, that is correct,” Riemann says with a subtle smile. “I am glad that it is clear to you, many other guests become terribly confused whenever they ask me about such a thing.”

You are distracted by a commotion from outside, which quickly grows louder, until it begins to sound like a busy marketplace. You see an enormous congregration of guests piled up at the front door. Herr Riemann had also noticed, and exclaimed all of a sudden, “Ach Gott, I do apologise! Perhaps you will not object to staying in room 2 instead? I assure you, it is isomorphic to room 1, and…” he trailed off as he went back into his office, but then emerged quickly again with the keycard room 2. “As you have noticed, we have a countably-infinite busload of new arrivals.”

You have only just understood how the Grand Hilbert can accommodate finitely many new arrivals, but how could it possibly fit infinitely many additional guests?

“This is most extraordinary, but surely, you cannot simply use the shifting method again?”

“Again, well observed. Thankfully, Herr Cantor has also solved this problem, and the solution is not any more difficult. We can simply ask the guest in room x to move to room 2x. You were previously assigned room 1, but now you will move to room 2, the person in room 2 will go to 4, and so on.”

You pause for a little while, and suddenly realise the implication. “Aha, so now, all the odd numbered rooms are free, and since there are infinitely many odd numbers, everyone will have a room!”

“That is indeed correct. You are quite astute, I must say. Are you perchance a student of mathematics?” Riemann seems genuinely impressed.

Well, look at you, smarty-pants. Let’s see why this solution is able to accommodate countably infinite new guests into the hotel. Once again, our target set (codomain) is \mathbb{N}, which is also the set of room numbers. This time, our domain contains what is essentially two copies of \mathbb{N}: we have the existing guests at the Grand Hilbert, plus the newly arrived countably-infinite busload. Let’s write this as:

  • Set of existing guests = X_1 = \{1, 2, 3, ...\}
  • Set of new guests = X_2 = \{1', 2', 3', ...\}

and so, we are looking for a bijection f: X_1 \cup X_2 \to \mathbb{N}. This time, let’s try out the Spivak defintion of a function (Defintion 2.2b), and write down the ordered pairs.

Firstly, we move the existing guests according to the rule “guest in room x goes to room 2x“. Thus we obtain this set of ordered pairs {(1, 2), (2, 4), (3, 6), (4, 8), … (x, 2x), …}. Then we accommodate the new guests into the now-vacant odd numbered rooms: {(1′, 1), (2′, 3), (3′, 5), … }. The existing guests are assigned to only even numbered rooms {2, 4, 6, …} and the new guests occupy odd numbered rooms {1, 3, 5, …}. Indeed, the union of these two sets gives us all the natural numbers, and everyone is happy!

  • Thinking time: what is the rule/formula that assigns the new guests to their rooms? You can drop the ‘ from the numerical labels, I used them initially to distinguish the two copies of \mathbb{N}.

How can we check this is a bijection? It is clear that each guest has been assigned to a separate room, but let’s check the “other direction”: given any room number, can you work out which guest has been assigned to it? For example, room 8 is now occupied by guest 4, and only by guest 4, and (verify this!) room 17 is now occupied by guest 9′ from the new arrivals. You should convince yourself that given any room number, it is possible to “reverse” the procedure and work out which guest has been assigned that room.

I mentioned earlier how arithmetic operations are meaningless when dealing with infinities. Naively, what we have just done is essentially “∞ + ∞ = ∞”, which looks ridiculous. In the more precise language of sets and functions, we have created a bijection from a set containing two copies of the natural numbers to the natural numbers themselves. There is no contradiction at all — this reinforces the point that our everyday intuition of concepts such as “size” do not work when dealing with infinity.

“Well, truthfully sir, I was not so keen on mathematics before, but I must admit I am developing an interest,” you say, as Riemann hands you the keys to your room.

“I am glad to hear that! I presume that you will enjoy many of the mathematical treasures this hotel has to offer. May I recommend the Museum of Differential Geometry on the 4th floor, west wing. I curated it myself, you see,” Riemann smiles awkwardly. You get the impression that he really wants to promote his own work, but at the same time feels uncomfortable doing so. “I am always unsure about my own work, but a certain Herr Einstein seems to be very interested in my theories of curved spaces… but I am rambling now.  I must get back to work, lots of new guests to attend to!”

“Evidently! I won’t keep you any longer. It seems you are quite an integral part of this business.” You collect your key and papers, and head towards the elevators.

“Danke, most kind of you! Oh, and dial \pi  for room service.”

Updated version: 2 September 2017

  • Thinking time: Consider the set of integers \mathbb{Z} = \{... -3, -2, -1, 0, 1, 2, 3, ...\} , or in other words, all the natural numbers with their negatives and zero. Show that this set is also countably infinite, i.e. has the same cardinality as the natural numbers.
  • Further reading/Googling: Remarkably, the set of all rational numbers (loosely speaking, anything that can be expressed as a fraction p/q, where p and q are integers) is also countably infinite, but the argument is not so simple. Cantor did pioneering work on this problem of countable and uncountable sets.
  • What I have introduced here is merely the beginning, there are many extensions to this story of the Grand Hilbert Hotel. I am more concerned with introducing a general audience to the language of mathematics. But check out this solution for accommodating countably infinite many busloads each with countably infinite guests!! plus.maths.org/content/hilberts-hotel
  • I wrote above that statements like “∞ + 127” are meaningless — this is only in the context of the basic arithmetic operations, the main point being that ∞ should not be treated naively as a number. In more advanced mathematics, we use what is called the extended real line, where it is perfectly fine to write ∞ + 127 = ∞, but it is still important that infinity or minus-infinity is not treated as a real number. The Wikipedia article has been linked for those who are interested, but I avoided getting into these details for the general reader.

3 thoughts on “Diversions in Mathematics #2: Hilbert’s Hotel”

  1. Nice blog right here! Also your web site a lot up fast! What host are you the use of? Can I am getting your affiliate link to your host? I desire my web site loaded up as fast as yours lol

    Like

    Reply

  2. You actually make it seem really easy along with your presentation however I to find this topic to be actually something which I think I would by no means understand. It seems too complicated and very vast for me. I am having a look forward in your next submit, I’ll attempt to get the dangle of it!

    Like

    Reply

    1. Thanks for your comment!
      In response to your first question, I’m just using WordPress, nothing fancy (since I don’t know much programming anyway). But I am paying for the premium subscription.

      Like

      Reply

Leave a comment