Read: Lehman, Leighton, and Meyer: 4.1-4.3, 8.1.2

A good introduction to the Hilbert Hotel is given by this video:

Hilbert's Infinite Hotel on YouTube

What does this have to do with discrete mathematics and computer science?

A natural question that comes up when dealing with infinite sets such as ℕ, ℤ, ℤ+, ℚ, ℝ, all even numbers, 𝕊 (the set of strings): do they all have the same size? Are some of these sets larger than others?

What we learned in the lecture is what you can do if you want to compare the size of two things that are too large to count.

What we can do to compare the size of two sets A and B, even if they are really large, is to try to pair up every element in A with exactly one element in B, such that every element in B is paired up with exactly one element in A. (In other words, to find a bijection between A and B.) If we can do this, then A and B have the same size!

(Look at this video from Fem myror är fler än fyra elefanter where this idea is illustrated! The relevant part starts at 11:30.)

We found out that the following sets all have the same size:

1. the natural numbers ℕ and the even natural numbers. (The bijection is f(n) = 2n.)

2. the natural numbers ℕ and the odd natural numbers. (The bijection is f(n) = 2n+1.)

3. the natural numbers ℕ and the strings 𝕊. (We showed this by fitting all strings into the Hilbert hotel.)

One question we managed to answer in the lecture was this one:

The answer is NO.

Why? Because we are going to show that there are more functions ℕ -> ℕ than there are programs. Therefore, there must be functions that do not have a corresponding program that implements them.

Step 1: The number of programs is the same as the number of strings. This is easy to see, because a program can be seen as a body of text, which is just a string.

Step 2: There are as many strings as natural numbers. We can see that this is the case by fitting all strings in the Hilbert Hotel. (First all strings of length 0, then all strings of length 1, then of length 2, etc.)

Step 3: There are way more functions ℕ -> ℕ than natural numbers. We show this by showing that the functions ℕ -> ℕ do not fit in the Hilbert Hotel:

Suppose all functions ℕ -> ℕ fit into the Hilbert Hotel. That means that each room (with number n) contains a function f_n : ℕ -> ℕ, and for any function g : ℕ -> ℕ, there exists a room number n such that g = f_n.

This cannot be the case! Look at the following function h:

The function h is a fine function ℕ -> ℕ, but it cannot be in any of the rooms! For any room numer n, we have that h(n) = f_n(n)+1 /= f_n(n), and thus we have h /= f_n.

In other words, our assumption (that "all functions ℕ -> ℕ do fit into the Hilbert Hotel") was wrong, and indeed they don't fit. There must be more functions ℕ -> ℕ than natural numbers.

In this way, we learnt that there are limitations to what kind of things we can implement in a computer as a program. There are functions ℕ -> ℕ that we can define, but we cannot write programs that implement them!