Lesson 2

It turns out that comparing the cardinalities of infinite sets is an important mathematical question that has direct applications in computer science. This is explained by the fact that the cardinalities of many sets of interest to us—such as the set of all computational problems and the set of all programs—are infinite. By learning to compare them, we find that there are problems that cannot be solved on a computer at all! Moreover, we will construct natural examples of such problems.

How can we compare the size of infinite sets? Infinity is an idea, not a number. And it seems that there exists just one infinity. Later, we will see that this is not the case: not all infinite sets are equally infinite, and there are infinitely many different infinities (whatever that means right now).

The analogy with the hotel and the tourists allows us to extend the concept of equinumerosity to infinite sets. We will call sets \(A\) and \(B\) equinumerous if there is a bijection between \(A\) and \(B\). This definition was introduced by Georg Cantor, who created set theory.

It is important to note that some intuitively correct statements no longer hold. For example, if finite sets \(A\) and \(B\) are equinumerous, and we remove some elements from \(B\), then \(A\) ceases to be equinumerous to it. For example, if there were an equal number of tourists and rooms, and then some rooms closed for repairs, the number of rooms would certainly be smaller than the number of tourists. At this point, we imply that both of these sets are finite, and therefore we use the word “number” (right in the previous sentence!) to denote their cardinalities.

Now, imagine that the number of rooms in the hotel is infinite, and that they are numbered, as is often the case in hotels, with the numbers \(1, 2, \dotsc\). And suppose, as before, all the rooms are occupied. It turns out that we have an infinite number of tourists, and we still have a bijection between the tourists and the rooms: each room has a tourist, and each tourist has their own room. Everything seems fine so far. But then a new tourist arrives at the hotel! Clearly, there is no room for them, right? Well, yes. But then the new tourist himself suggests: let the tourist from room 1 move to room 2, the tourist from room 2 to room 3, and so on. That is, the tourist from room \(k\) moves to room \(k+1\). As a result, each tourist still has their own separate room, and all rooms are occupied except for the first one—into this first room the new tourist will move! This thought experiment is known as Hilbert's paradox of the Grand Hotel.

Formally, we have just established a bijection between \(\mathbb{Z}_{\ge 1}\) and \(\mathbb{Z}_{\ge 2}\). It is given by the function simply: \(\phi(x)=x+1\), and the inverse function is also simple: \(\psi(x)=x-1\). Visually, it also looks quite natural: