Lecture Notes on Course Introduction / Hilbert Hotel
Read: Lehman, Leighton, and Meyer: 4.1-4.3, 8.1.2
The Hilbert Hotel
A good introduction to the Hilbert Hotel is given by this video:
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 \(\mathbb{N}, \mathbb{Z}, \mathbb{Z}^+, \mathbb{Q}, \mathbb{R}\), all even numbers, \(\mathbb{S}\) (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!
This is illustrated in the following video :-)
The relevant part starts at 11:30.
We found out that the following sets all have the same size:
the natural numbers \(\mathbb{N}\) and the even natural numbers. (The bijection is f(n) = 2n.)
the natural numbers \(\mathbb{N}\) and the odd natural numbers. (The bijection is f(n) = 2n+1.)
the natural numbers \(\mathbb{N}\) and the strings \(\mathbb{S}\). (We showed this by fitting all strings into the Hilbert hotel.)
This is perhaps surprising. For example, \(\mathbb{N}\) contains numbers that are not even, but there are as many even numbers as natural numbers.
One question we managed to answer in the lecture was this one:
Can all functions \(f : \mathbb{N} \rightarrow \mathbb{N}\) be implemented byy a program P, such that P computes f?
The answer is NO.
Why? We are going to show that there are more functions \(f : \mathbb{N} \rightarrow \mathbb{N}\) than there are programs P. Therefore, there must be functions that do not have a corresponding program that implements them.
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.
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.)
There are way more functions \(\mathbb{N} \rightarrow \mathbb{N}\) than natural numbers. We show this by showing that the functions \(\mathbb{N} \rightarrow \mathbb{N}\) do not fit in the Hilbert Hotel:
Suppose all functions \(\mathbb{N} \rightarrow \mathbb{N}\) fit into the Hilbert Hotel. That means that each room (with number n) contains a function \(f_n : \mathbb{N} \rightarrow \mathbb{N}\), and that all such functions have a room number.
This cannot be the case! Why? We are going to construct a function \(h\) that cannot be in the Hilbert Hotel. Here it is:
\[ h : \mathbb{N} \rightarrow \mathbb{N}\\ h(n) = f_n(n)+1 \]
The function h takes an argument \(n\) and makes sure to produce a different result for \(n\) than the function \(f_n\) that is in room n.
This means that the function h cannot be in any of the rooms! For any room numer n, we have that \(h(n) = f_n(n)+1 \not= f_n(n)\), and thus we have \(h \not= f_n\).
In other words, our assumption (that "all functions \(\mathbb{N} \rightarrow \mathbb{N}\) do fit into the Hilbert Hotel") was wrong, and indeed they don't fit. There must be more functions \(\mathbb{N} \rightarrow \mathbb{N}\) 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 \(\mathbb{N} \rightarrow \mathbb{N}\) that we can define, but we cannot write programs that implement them!