David Hilbert imagines a hotel with an infinite number of rooms. In this hotel, each room can only be occupied by one guest, and each room is indeed occupied by exactly one guest. What happens if more guests show up? Can they be accommodated for?
PAUSE: WHAT DO YOU THINK AND WHY?
Suppose we propose they cannot be accommodated for, since all the rooms are occupied. Hilbert then claims that he can define the functions and where is a set containing all current guests, and simply maps each guest to a room in the set , and maps each room in to a new one in . Notice that these functions must be injective, since if a room contains two different guests, those two different guests must be the same guest; recall . is similarly an injection too. Then, we define a function that essentially takes each current guest and maps them to a new room in . We can define however we want. Notice too that must also be an injection. Since and by defn . Apply on both sides, you get: . But is injective, so , so it follows h is injective.
To bring some level of intuition to this, we can define to be a function that takes every guest and moves them to an even numbered room. We’ve just freed up infinitely many odd numbered rooms that can be occupied by our new infinitely many guests. We can repeatedly do this. Suppose we get a call again from the Math department asking for infinitely many rooms to accommodate infinitely many mathematicians attending a conference nearby. To make these mathematicians feel right at home, we can define to now be a function that maps every current guest in a prime numbered room to the closest composite numbered room, and now I have infinitely many prime numbered rooms available.
Now, I hope you are convinced Hilbert’s hotel of infinitely many rooms can accommodate infinitely many people even though it already has infinitely many guests already. This idea will serve crucial to understanding the Cantor–Schröder–Bernstein theorem.
But before we move onto the theorem, let us define a few properties.
Suppose we have two sets and and we want to compare their cardinalities. It is quite straightforward to do this if the sizes of each set are finite. We can just assert or , or . But what if and both had infinitely many elements. For this case we define is a bijection. A bijection is a function that is both injective and surjective. Surjective is then defined as . In words, simply put that every value in the codomain of the function has at least one value from the domain that maps to it.
It’s also worth noting the pigeonhole principle and how it relates to injective and surjective functions. Suppose I had pigeons and pigeonholes, where . This means that if I were to fit each pigeon into a different pigeonhole, provided it’s not occupied, then I would have some additional pigeonholes left. Notice that in such a scenario each pigeon gets mapped to a unique pigeonhole, hence the mapping is injective. This means that given sets and . Now what if I had more pigeons than holes? Then a surjection would surely exist, between the two sets, formally . Notice that these facts apply for finitely sized sets. How do they fair on infinitely sized sets though? Can we even think of them in the same way? Hilbert’s hotel teaches us to not think of it in a similar way. Infinities are too strange for that. For sets with infinite elements, only the injective pigeons argument remains by definition. Furthermore we state that but no .
So, Cantor claimed the following without proof:
Let be sets. If injection and injection bijection . This would then imply that . I hope one realises that this is equivalent to saying . This equivalence follows from the properties we’ve defined above.
Now, back to Hilbert’s hotel. Let’s define the functions and to both be injective. Furthermore, let’s define the sets and . Think of as guests in the hotel, and as rooms in the hotel. is the image of onto . In other words a function that tells us who’s occupying a certain room. We then define , that is to say are guests who aren’t allocated rooms. To , we can apply , i.e. which you can think of as assigning rooms to the roomless. But we have a problem. Each room has to to only have exactly one guest, and may or may not respect this. To find out, we reapply to , so we have , which gives us our new roomless guest. We repeat the cycle infinitely many times and we do this through a new function we call . More formally:
Claim: is a injection:
Required to show
is injective since is injective by defn.
is injective since is injective, which makes injective.
Applying on both sides
This is a contradiction since we assumed . So we cannot have this case.
This then implies that is injective.
Now we need to show that is a surjection. Recall, that for to be a surjection, we need to have
First recall the functions we are working with in are and . So, consider .
If for some , since i.e. for some . Think of this part as saying that if a guest is one of the guests who are going to be moved then they aren’t the first ones who were moved i.e. since we defined to be written as a value that pops out from
That is to say, if x is displaced, then x’ occupies the room.
AND THE PROOF IS COMPLETE.
Please see this video which helped me understand this proof by drawing parallels with Hilbert’s hotel. What I’ve done in this post is mostly elaborate further on parts he might’ve jumped and added in more information to facilitate better understanding. Furthermore, see The Book Of Proof which contains its own unique way of framing the proof.