6. Sets of the same cardinality

Hilbert’s hotel

Imagine a hotel with some number, e.g. five, single rooms. Assume that all the rooms are occupied. So if a new guest arrives, receptionist has to tell him that no rooms are available.

But what will happen if the hotel is infinite? Infinitely many rooms numbered 0, 1, 2, etc. single rooms (we will call such a hotel Hilbert’s hotel) and all those rooms are taken, and a new guest appears. Should the receptionist tell him that there are no free rooms? Wise receptionist do not have to. But if not he has to disturb all the guests: he can ask all the guest to step out to the corridor and move to the room with a number greater by one. From 0 to 1, from 1 to 2, from 2 to 3, and so on. All the guest will get a new room and the room 0 will stay free and can be given to the new guest! So Hilbert’s hotel can actually accommodate one more guest then the number of guest that can fill the whole hotel.

An what will happen if to an empty Hibert’s hotel arrives an infinite group of men and and infinite group of women? If the receptionist accommodates the women first, they will take all the rooms, and there will be no rooms for men. Wise receptionist will accommodate women and men alternately. Women to the rooms with even numbers and men to the rooms with odd numbers and therefore all people will fit in. Therefore Hilbert’s hotel can accommodate twice as many people as can fill the whole Hilbert’s hotel!

Sets of the same cardinality

How to check that two sets have the same number of elements? E.g. a set of some women and a set of some men. We can count elements in each of the sets. But there is also a second method. It suffices to match elements of both sets into pairs. If it is possible the two sets have the same number of elements. This is a very nice method, since it can be also applied to infinite sets. In the language we have developed, matching elements into pairs, means finding a bijection (function onto and 1-1) between those sets.

We will say that sets A and B are of the same cardinality, if there exists a bijection between them. This fact will be denoted as |A|=|B|.

Examples

The above considerings about Hilbert’s hotel, were actually considering whether the set of rooms and the set of guests are of the same cardinality. In the first case we have actually considered the following bijection between the sets of guests actually \mathbb{N}\cup \{-1\} — the additional guest will be denoted here as -1) and the set of rooms (enumerated with elements of \mathbb{N}): f(x)=x+1.

In the second case (with women and men) we can think about a bijection between integer numbers \mathbb{Z} (non-negative numbers are men, and negative — women) with set \mathbb{N} (rooms). This bijection is defined as follows:

    \[g(z)=\begin{cases} -2z & \text{for }z<0\\ 2z+1 & \text{for }z\geq 0 \end{cases}\]

One more example. Let us find a bijection between [0,1] and [0,1). It is not very straightforward, we will need set A=\{\frac{1}{n}\colon n\in\mathbb{N}, n>0\}, which will help us construct an appropriate bijection:

    \[h(x)=\begin{cases} \frac{1}{n+1} & \text{for } x=\frac{1}{n},n\in\mathbb{N}, n>0$\\ x & \text{for } x\in [0,1]\setminus A \end{cases}\]

Are all infinite sets of the same cardinality?

So maybe all infinite sets are of the same cardinality and we are we do things without any sense? No! Not all infinite sets have the same cardinality. For example \mathbb{N} and \mathbb{R}. Let us give some arguments why real numbers, even only those in the interval [0,1], cannot be accommodated in Hilbert’s hotel, in other words there does not exist a bijection f\colon \N\to [0,1].

Assume otherwise, that such a bijection exists, so every point on the interval can be accommodated into Hilbert’s hotel, so [0,1]=\{x_0, x_1, x_2,\ldots\}, where f(n)=x_n. Now let us divide [0,1] into three intervals [0,\frac{1}{3}], [\frac{1}{3},\frac{2}{3}], [\frac{2}{3},1]. Choose this interval out of the three, which does not include x_0. We divide the chosen interval into three parts and we choose the one that does not include x_1. Again, we divide the chosen interval into three parts and choose those which does not include x_2 and so on. In effect we will find a point which in not equal to x_0, not equal to x_1, not equal to x_2, and so on. Therefore it is not accommodated in Hilbert’s hotel, which is a contradiction, because we have assumed that all the points are accommodated.