Lesson 1

We do know how to compare the cardinality of finite sets. For example, how to find out which is more—tourists or rooms in a hotel? One can try to assign a room to each tourist. If there are still free rooms, then there are more rooms than tourists. If some tourists don't get rooms, then there are more tourists than rooms. Finally, if each tourist gets a room and no free rooms remain, then the set of tourists and the set of rooms have the same size or the same cardinality. In this last case, we naturally obtain a bijection, which guarantees us that the sets have the same cardinality.

Above, we were able to say when two finite sets have the same cardinality. But can we ask the same question about infinite sets? For example, are the sets \(\mathbb{Z}_{>0}\), \(\mathbb{Z}\), and \(\mathbb{R}\) of the same cardinality? On the one hand, all these sets are infinite, so it seems one might say that they all have the same cardinality, and it simply equals infinity. On the other hand, these sets are nested within each other: \[\mathbb{Z}_{>0}\subset \mathbb{Z}\subset \mathbb{R}\ .\] Does it then make sense to claim that they have the same cardinality? And is this question not too abstract to ask in the first place? Indeed, an infinite set is an abstract object, it does not exist in nature, and it cannot exist in programming.

But natural numbers are also an abstraction. People once worked with the concepts of “two stones” and “two sticks” and only later realized that it would be useful to introduce the number two. At the same time, the number two exists in programming, but, for example, we cannot represent infinite sets like \(\mathbb{Z}\) and \(\mathbb{R}\) in a program. Does it then all equal, are the sets \(\mathbb{Z}\) and \(\mathbb{R}\) of the same cardinality or not?