I'm not a mathematician, so my question may look a bit lame to most of you.

In the Infinite Hotel paradox we are dealing with infinite set of pairs (room/guest). A main property of a pair is 50/50 ratio. A set of pairs inherits the properties of its members, right?

So, an infinite set of pairs also have 50/50 ratio.

Now, Hilbert brakes the infinite set of pairs in to two sets in order to insert one guest in the newly created infinite set of guests. But even divided in to two sets, the 50/50 ratio of the broken infinite set of pairs, cannot magically disappear, right? Because even after we take the guests out of the rooms we'll still have 50% rooms and 50% guest.

If my assumption is correct, we will brake the 50/50 ratio by adding one quest, and the rooms will become less than 50%, which will leave no room for the new guest.

Am I missing something here, and if yes, what?

Foreword:

Reiterating what is said in comments and hopefully elaborating on a few key points:

The specific mathematical concepts behind the underlying problem are those of cardinality of sets and bijective functions. These formalized concepts mirror how we think in the finite case and allow us to think beyond that as well in the infinite cases.

The purpose of the "Hilbert's Hotel" example is to show explicitly via way of visualization how our intuition from finite sets does not directly translate to infinite sets.


What is a bijection and what is meant by cardinality?

A bijective function is a function from a domain to a codomain where the following properties are satisfied:

  • It is a function, i.e. every element in the domain maps to exactly one output in the codomain (e.g. each person can be in only one room at a time)
  • It is a surjective function, i.e. every element in the codomain is mapped to by at least one element in the domain (e.g. every room has at least one person in it)
  • It is an injective function, i.e. every element in the codomain is mapped to by at most one element in the domain (e.g. no room may have more than one person in it)

We say that if there exists a bijective function between two sets, that they "have the same cardinality" (i.e. they have the "same number of elements"). If the sets are called $A$ and $B$, we write that they have the same cardinality as $|A|=|B|$. (Other popular options exist, such as $\#A=\#B$ or $A\sim B$, etc... I will stick with $|A|=|B|$ through the rest of this post).

For example, if we have $50$ people and $50$ rooms, then we can come up with a bijective function pairing the people to the rooms so that exactly one person goes in each room.


What are some results for the finite case?

A few properties that you should be well familiar with for finite sets:

If $|A|=|B|$ and $A'\supsetneq A$, then $|A'|\gneq |B|$.

For example, if we have $50$ people and $50$ rooms, then we have a bijective function pairing people to rooms, but as soon as we add a $51$'st person, then we cannot come up with such a pairing. $51$ people and $50$ rooms, we will by the pigeonhole principle be forced to have some room with more than one person in it.

Similarly, if we had $50$ people and $51$ rooms, then we would have at least one empty room.

Indeed, these observations lead us to the following result:

If $A$ and $B$ are both finite sets and there exists an injective function from $A$ to $B$ which is not surjective then $|A|<|B|$ and no bijection exists between $A$ and $B$. Similarly if $A$ and $B$ are both finite sets and there exists a surjective function from $A$ to $B$ which is not injective then $|A|>|B|$ and no bijection exists.

The very point of Hilbert's Hotel is to show that the above result does not hold for infinite sets.


What really is the hotel story meant to portray?

Letting $P=\{p_1,p_2,p_3,\dots\}$ and $R=\{r_1,r_2,r_3,\dots\}$ be (countably) infinite sets and letting $f:P\to Q$ given by $f(p_i)=r_i$ be a bijective function between them...

(here, $P$ represents our set of hotel guests and $R$ our set of rooms, our bijection just says that the $i$'th person is in the $i$'th room)

...and let $P'=P\cup \{p'\}$ where $p'\notin P$...

(if we add another new person to the hotel)

...then the function $g$ between $P'$ and $R$ given by $g(x)=\begin{cases}r_1&\text{if}~x=p'\\r_{i+1}&\text{if}~x=p_i\end{cases}$ is a bijection, thereby proving that $P'$ and $R$ are of the same cardinality despite $P'\supsetneq P$.

(by shifting each person down a room and giving the new person the first room, we successfully pair the rooms and people again leaving no person without a room and leaving no room without a person such that each room has exactly one person)

Note that if we tried to do the same thing in a finite setting, then we would have had the "last person" try to change rooms to the next room, but there would not be a "next room" for him to go to. Since we are working with infinite sets however, such a "last person" does not exist and so this does not present a problem.


Could we do it without making people change rooms first?

Given $P=\{p_1,p_2,\dots\}$ and $R=\{r_1,r_2,\dots\}$ be our infinite sets, letting $P'=P\cup \{p'\}$ where $p'\notin P$, and letting $f~:~P\to R$ given by $f(p_i)=r_i$ be our bijective function between the two, you are asking if there exists a bijective function $g$ from $P'$ to $R$ such that $g(p_i)=f(p_i)=r_i$ for all $p_i\in P$.

The answer is no, we can not. Suppose that $g(p')\in R$. Then $g(p')=r_i$ for some $i$. But, since $f$ is a bijection, $f^{-1}$ exists, and so $g(p')=r_i=g(f^{-1}(r_i))=g(p_i)$ and so $r_i$ is mapped to by two elements, $p'$ and $p_i$.

That is to say, if we do not move the people around in the rooms, and tell our new person to find some room to enter, it would necessarily already have someone in it.

Again, this would have in the finite case shown to us that no bijection exists between the sets, but in the infinite case as shown earlier this does not matter, a bijection still exists.


How about that 50/50 ratio thing?

When babies first learn to count, they point to each object they count and say the next number in sequence. So long as they don't accidentally point to the same thing more than once and don't skip or mess up any numbers in their sequence, they are successful at saying how many of an object there are.

Extending this method of counting and taking out the middle man of using numbers, we could also check to see if there are the same number of one type of object as another by pointing to a pair, one of objectA and one of objectB, before taking them away, checking to make sure that we pair each of them up successfully.

That is in essence coming up with a bijection between the set of objects in the first set with the set of objects in the second set.

Further, in the finite case, we notice that if we have $|A|$ elements in set $A$ and we have $|B|$ elements in set $B$ and $A$ and $B$ are disjoint sets, then $\frac{|A|}{|A\cup B|}=\frac{1}{2}=50\%$.

We also notice in the finite case that if $|A|\neq |B|$ then $\frac{|A|}{|A\cup B|}\neq \frac{1}{2}$.

As we move to the infinite case, things can get much weirder. If $A$ is infinite, then $|A|$ is infinity, but arithmetic with infinity is not well defined. We would have had $\frac{|A|}{|A\cup B|}=\frac{\infty}{\infty}$ which could be literally anything. You might try to say that it would be better written as $\frac{\infty}{2\cdot \infty}=\frac{1}{2}$ but that is not entirely correct.

You might try to say for instance that "Only half of all positive integers are even" and so there are "more" positive integers than positive even integers. In terms of that $\{1,2,3,4,\dots\}\supsetneq \{2,4,6,\dots\}$ you are correct, the positive integers strictly contains the positive even integers as a subset. In terms of cardinality however, they are considered to be the same size. That is because the function $f:\Bbb N\to 2\Bbb N$ given by $f(n)=2n$ is a bijection between those sets.

You might also say that there are "more positive integers which are not multiples of 3 than positive integers which are multiples of 3." In terms of relative density when looking at the numbers written in the usual order, $1,2,\color{blue}{3},4,5,\color{blue}{6},7,8,\color{blue}{9},\dots$ you might be correct. But, notice that I could have written the numbers in a different order: $1,\color{blue}{3},2,\color{blue}{6},4,\color{blue}{9},5,\color{blue}{12},7,\color{blue}{15},\dots$ where I alternate between writing the next multiple of $3$ and the next non-multiple of $3$.

Having a convenient way to pair things is nice, but if the pairing you are looking at doesn't have the desired property it does not automatically preclude a different pairing from existing in the infinite case even though it does in the finite case.

  • Wow! @JMoravitz you rock! Thank you sir for the great answer! I'm not mathematician but I could understand most of it. But let's leave the new guest alone. We don't increase the number of the rooms by moving the guests. The rooms are still the same number and percentage and so is for the guests. And since the 50/50 ratio is still present even after moving the guests, there won't be available room. As I earlier said, since ALL ROOMS ARE OCCUPIED, by moving the guests we set them in infinite motion, searching for available room and at least one of them will always be without a room. – Nikolay Sep 16 at 20:01
  • Again, that would be true for the finite case. The last person would be left without a room. In the infinite case there is no "last person" and as such no one is left without a room. This is despite that there is now a room without a person. – JMoravitz Sep 16 at 20:24
  • I strictly keep my thinking away from the finite sets, @JMoravitz. I don't mention end room, but infinite motion in search for a room. We cannot add empty room by mere motion even in an infinite set. Imaginatively there is room, mathematically there is no room, because the percentage is still 50/50 and that applies to infinity too. – Nikolay Sep 16 at 20:48
  • No one is sent in infinite motion. Everyone individually merely moves a few feet down. No one even needs to put much thought in searching for their next room. They know exactly where it is. As for the 50/50 comment, I still think it's the wrong way to think about things. Arithmetic with infinity is always messy. – JMoravitz Sep 16 at 21:51
  • Allow me to respectfully disagree with both your arguments, @JMoravitz: 1. since there is no empty room for the motion to end (infinity of occupied rooms), there will be infinite motion. Knowing infinity so well, you should be able to imagine it. 2. we cannot magically wipe out the 50/50 ratio. It is a set condition - infinity of occupied rooms The infinity is not a magical place where no rules apply and arithmetic has nothing to do here. We are talking logic not calculus. – Nikolay Sep 16 at 23:38

Hi @JMoravitz and all who took part in solving this problem. I'm writing an answer to my question, because it gives me more word space, and because I don't see a need for further discussion. First I'd like to thank you all for the patience and for taking from your precious time to answer.

Thank you!

I did really hope that there is something which I don't see in the problem and I asked the question with the sincere hope to get an answer which defeats all my arguments; I like to learn. If the moderator does not close the topic you can comment and I'll respond, but there is no really much left to be said.

Mathematician have the highest IQ, but in many cases the intelligence lead us to negligence which results in mistakes. I'm not mathematician and probably not as intelligent as you guys, but I work as a hobby on logical problems, language deception (logical problems due to improper use of language and mind stereotypes) and human's psychology. I came to the conclusion that most of the logical fallacies and the paradoxes for that matter come from improper use of properties or missing properties.

After our discussion I can say with greater certainty that Hilbert's paradox is a real solvable paradox and it comes from improper use of properties and deception based on mind stereotypes. I understand the point with the bijection which JMoravitz is making but before we come to the pairing which is the easy part, we have to solve a much difficult problem - the 50/50 percent ratio in set of pairs. Because it is always on our way.

Three points to solve the paradox

1. If we vacate a room, we cannot use it for new guest unless we brake the infinity. How so? Because ∞+1=∞ rooms, and we already have infinite number of guests on the other side of the set (50/50 ratio is still present). Hence the conclusion that although it seams that we have an empty room we don't really have one, because the number on both sides is always equal - infinite.

2. Not taking in account the above, we actually make the number of the hotel guests finite (if there is empty room it is because the guests are finite) which automatically makes the number of the occupied rooms finite + 1 empty room. Now the number of the rooms is with 1 greater than the number of the guests and we can accommodate one guest. But in this case we don't work with infinity, do we? If we don't agree with this then point 1 applies.

3. We can ignore point 1 and use the obvious argument against point 2 (which would be wrong) that after we move the guests we end up with infinite occupied rooms and one empty room in the hotel (!) Well, here is the fallacy - the hotel is defined as infinite countable number of occupied rooms. Let's lose the "hotel" word which is deceiving us and let's use "infinite set of pairs". If we have one element which is not paired, does it belong to the set? Of course not. So, the "empty" room does not belong to the hotel because it is not a member of the set of pairs. And this is what I call the "language deception". The "hotel" word is bringing deception.

Let me explain, why the room does not belong to the hotel.

What happens if we move the guests with one room down, instead of moving them up? The guest from room №1 leaves the room, and the room is taken by the guest from room №2, the guest from №3 goes in room №2, the guest from №4 goes in №3 and so on (it is the opposite of vacating a room) Now one guest left the hotel. Is this person part of the hotel guests? Of course not. So is the case with the empty room - it does not belong to the hotel.

By taking one guest out of the hotel we can create another hotel if we find a room for the guest. And we already know how to create another room for the new hotel, don't we ;)

Every paradox has a solution and if the solution is wrong, there is solution for the wrong solution. By following the "property rule" we can solve any paradox. You guys can try me on that ;)

Once again, thank you! It was a great pleasure for me.

  • Ok, you call hotel the bijection and build a new hotel with the rooms of the first and one host more than before. – N74 Sep 18 at 10:58
  • I don't know which bijection you're talking about, @N74, but as far as I know we cannot have a loose element with bijection. But anyhow, read again my answer carefully and try to understand the logical point in the problem. We all know that mathematics serves as a tool for proving logic. We cannot change the logic to fit the mathematics ;) – Nikolay Sep 18 at 14:12
  • Oh, I think that your comment gave me the hint of where is the deception in your thinking, @N74. You are trying to do bijection in the set by including the new guest in it. But hold on. Before you do add the guest you must find a room for him. The guest is not an element of the set yet. Moving the guests with one room up, or the rooms with one down is the same thing, and it produces an element which does not belong to the set. And this is only one side of the fallacy. And then with your idea of bijection with element which does not belong to the set, you add even more to the problem. – Nikolay Sep 18 at 14:26
  • 1
    You said Let's lose the "hotel" word which is deceiving us and let's use "infinite set of pairs". This is the usual definition of a relation. If it is injective (each guest has at most a room) and surjective (each room contain at least a guest) it is a bijection. So you called the hotel a bijection. In this very case your one to one ratio has to be kept, and as everyone here told you, when you move a guest you destroy a bijection and create a new one, in fact you say By taking one guest out of the hotel we can create another hotel – N74 Sep 18 at 14:29
  • And there is no deception in my thinking, I'm trying to make you use the right name for the right things. Hilbert with this paradox wanted people to think how much it is difficult to treat uncountable elements using sets, while it is straightforward using bijections. Criticising his paradox you confirmed what he was saying. – N74 Sep 18 at 14:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.