Knowledge this posts assumes: What is a set, set cardinality, a function, an image of a function and an injective (one-to-one) function.

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 f:A \mapsto B, and g:B \mapsto C, where A is a set containing all current guests, and f simply maps each guest to a room in the set B, and g maps each room in B to a new one in C. 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 f(a) = f(b) \rightarrow a = b. g is similarly an injection too. Then, we define a function h = g(f(x)), x \in A that essentially takes each current guest and maps them to a new room in C. We can define h however we want. Notice too that h must also be an injection. Since h(x) = g(f(x)) and by defn g(f(a)) = g(f(b)) \rightarrow a = b. Apply g^-1 on both sides, you get: f(a) = f(b). But f is injective, so a = b, so it follows h is injective.
To bring some level of intuition to this, we can define h 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 h 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 A and B 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 |A| > |B| or  |A| < |B|, or |A| = |B|. But what if A and B both had infinitely many elements. For this case we define |A| = |B| \iff \exists f: A \mapsto B, s.t. f is a bijection. A bijection is a function that is both injective and surjective. Surjective is then defined as \forall b \in B, \exists a \in A s.t. f(a) = b. 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 n pigeons and n+k pigeonholes, where n,k \in ( \mathbb{N} \cup \{0\} ). 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 A, B and |B| \geq |A| \rightarrow \exists injection f: A \mapsto B. Now what if I had more pigeons than holes? Then a surjection would surely exist, between the two sets, formally |A| \geq |B| \rightarrow \exists surjection f: A \mapsto B. 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 |B| < |A| \rightarrow \exists injection f: A \mapsto B but no   g bijection:A \mapsto B.

So, Cantor claimed the following without proof:
Let A,B be sets.  If \exists injection f : A \mapsto B and injection g: B \mapsto A \rightarrow  \exists bijection h : A\mapsto B. This would then imply that  |A| = |B|. I hope one realises that this is equivalent to saying |A| \geq |B| and |B| \geq |A| \rightarrow |A| = |B|. This equivalence follows from the properties we’ve defined above.

 

Now, back to Hilbert’s hotel. Let’s define the functions f: A \mapsto B and g: B \mapsto A to both be injective. Furthermore, let’s define the sets A  and B. Think of A as guests in the hotel, and B as rooms in the hotel. g[B] is the image of  B onto A. In other words a function that tells us who’s occupying a certain room. We then define A_{0} = A-g[B], that is to say A_{0} are guests who aren’t allocated rooms. To A_{0}, we can apply f, i.e. f[A_{0}]  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 F may or may not respect this. To find out, we reapply g to f[A_{0}], so we have A_{1} = g[f[A_{0}]], which gives us our new roomless guest. We repeat the cycle infinitely many times and we do this through a new function we call h(x). More formally:

We define

A_{0} = A-g[B]

A_{n+1} = gf[A_{n}], n=0,1,2,...

A_{n \rightarrow \infty} = \bigcup_{n=0}^{\infty} A_{n}

h(x) = \left\{ \begin{array}{ll} f(x) & \quad x \in A_{n \rightarrow \infty}  \\ g^{-1}(x) & \quad otherwise \end{array} \right.

Claim: h is a injection:

Required to show h(x_{1}) = h(x_{2}) \rightarrow x_{1} = x_{2}

x_{1}, x_{2} \in A_{n \rightarrow \infty} \rightarrow h is injective since f is injective by defn.

x_{1}, x_{2} \notin A_{n \rightarrow \infty} \rightarrow h is injective since g is injective, which makes g^{-1} injective.

x_{1} \in A_{n \rightarrow \infty} and x_{2} \notin A_{n \rightarrow \infty}.

h(x_{1}) = h(x_{2})

\rightarrow f(x_{1}) = g^-1(x_{2})

\rightarrow x_{2} = g(f(x)) Applying g on both sides

\rightarrow x_{2} \in g[f(A_{n})]

\rightarrow x_{2} \in A_{n+1}

\rightarrow x_{2} \in A_{n \rightarrow \infty} This is a contradiction since we assumed x_{2} \notin A_{n \rightarrow \infty}. So we cannot have this case.

This then implies that h is injective.

Now we need to show that h is a surjection. Recall, that for h to be a surjection, we need to have \forall z \in B, \exists x \in A s.t. h(x) = z

First recall the functions we are working with in h(x) are g^{-1}(x) and f(x).  So, consider x = g(z).

If x \notin A_{n \rightarrow \infty} \rightarrow h(x) = g(x)  = z

If x \in A_{n \rightarrow \infty} \rightarrow x \in A_{n} for some n > 0, since x \in g[B] \rightarrow x \in g(f(A_{n-1})) i.e. x = g(f(x')) for some x' \in A_{n-1}. 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. x \in A_{0} since we defined x to be written as a value that pops out from g(z)

\rightarrow z = g^{-1}, but x = g(f(x')) \rightarrow g^{-1} = f(x') \rightarrow z = f(x') = h(x')

That is to say, if x is displaced, then x’ occupies the room.

\rightarrow h(x) is surjective

\rightarrow h(x) is bijective

 

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.

 

 

 

How clear is this post?