# Thread: Hilbert's hotel and busses : Injectivity - Surjectivity

1. Hey!!

I look at the problem with hilbert's hotel and the busses. First one bus with infinitely many guests, then four busses with infinitely many guests and then infinitely many busses with infinitely many guests.

At each case we move all the guests that are already in the hotel to the odd room numbers.

So the even room numbers are free for the new guests.

In the first with one bus we use the formula $n = 2(i-1)+2$ where $i\in \mathbb{N}\setminus\{0\}$ is the number of place in the bus and $n$ is the even room number that this guest will get.

In the second case with the four busses we use the following:
\begin{equation*}\begin{matrix} & 1. \text{ Bus } & 2. \text{ Bus } & 3. \text{ Bus } & 4. \text{ Bus } \\ 1. \text{ Person } & \text{ Room } 2 & \text{ Room } 4 & \text{ Room } 6 & \text{ Room } 8 \\ 2. \text{ Person } & \text{ Room } 10 & \text{ Room } 12 & \text{ Room } 14 & \text{ Room } 16 \\ 3. \text{ Person } & \text{ Room } 18 & \text{ Room } 20 & \text{ Room } 22 & \text{ Room } 24 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ i. \text{ Person } & \text{ Room } 8(i-1)+2 & \text{ Room } 8(i-1)+4 & \text{ Room } 8(i-1)+6 & \text{ Room } 8(i-1)+8\end{matrix}\end{equation*}

In the last case with the infinitely many busses we use the formula $2^{i}\left (2(j-1)+1\right )$ where $i$ is the place in the bus and $j$ is the number of the bus.

Using this we get \begin{equation*}\begin{matrix} \text{Place}/\text{Bus} & 1. \text{ Bus} & 2. \text{ Bus} & 3. \text{ Bus} & 4. \text{ Bus} & 5. \text{ Bus} & \ldots \\ 1 & 2 & 6 & 10 & 14 & 18 & \ldots \\ 2 & 4 & 12 & 20 & 28 & 36 & \ldots \\ 3 & 8 & 24 & 40 & 56 & 72 & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \end{matrix}\end{equation*}

I want to describe the injectivity and the surjectivity of the maps, and if the maps for the old and the new guests are injective and surjective.

The map for the old guests is injective, since it means that the new room thet they get either had no previous guest or one.

The same holds also for the map for the new guests. Their new rooms either had no previous guests or one.

As for the surjectivity. As for the rooms of the old guests, only the odd room umbers have a preimage and so the map is not surjective. As for the rooms of the new guests, only the even room umbers have a preimage and so the map is not surjective.

Is that correct?

2.

3. mathmari:
Quote:
At each case we move all the guests that are already in the hotel to the odd room numbers.

i woulndn't. For example, in tne second case where, after all rooms are full, four new buses each containing an infinite (we really need "countably infinite") number of guests come I would move guests in room "n" to room 5n. Then put the guest from the first new bus in rooms 5n+ 1, from the second bus in 5n+ 2, etc.

For the last problem where a (countably) infinite number of busses, each containing a (countably) infinite number of guest, consider the set of rational numbers. That set is countable so we can "number" each rational number. We can think of the original set of guests as correponding to the rational numbers 1/n then the guests from the first new bus 2/n, etc. Put each guest into the integer numbered room corresponding to that rational number. I think that is basically what you have done.

Originally Posted by HallsofIvy
mathmari:
i woulndn't. For example, in tne second case where, after all rooms are full, four new buses each containing an infinite (we really need "countably infinite") number of guests come I would move guests in room "n" to room 5n. Then put the guest from the first new bus in rooms 5n+ 1, from the second bus in 5n+ 2, etc.
So is the idea of my post wrong? Isn't it similar to yours?

Originally Posted by HallsofIvy
For the last problem where a (countably) infinite number of busses, each containing a (countably) infinite number of guest, consider the set of rational numbers. That set is countable so we can "number" each rational number. We can think of the original set of guests as correponding to the rational numbers 1/n then the guests from the first new bus 2/n, etc. Put each guest into the integer numbered room corresponding to that rational number. I think that is basically what you have done.
[/FONT][/COLOR][/LEFT]
I haven't really understood the last part:

"Put each guest into the integer numbered room corresponding to that rational number."

What exactly do you mean?

5. Originally Posted by mathmari
I want to describe the injectivity and the surjectivity of the maps, and if the maps for the old and the new guests are injective and surjective.

The map for the old guests is injective, since it means that the new room they get either had no previous guest or one.
Hey mathmari!!

We don't look at just the new rooms do we?
Nor does it matter whether a room had a previous guest or not, does it?

I think we are talking about the set of old guests, the set of newly arriving guests, and the set of rooms yes?
If so, then initially all rooms were occupied by exactly 1 old guest.
So the initial map of old guests to rooms is both injective and surjective.
After the old guests were moved to new rooms, each room had either an old guest, or no guest.
So the new map of old guests to rooms is injective.

Or do you have different sets or maps in mind?

Originally Posted by mathmari
The same holds also for the map for the new guests. Their new rooms either had no previous guests or one.
Shouldn't it be that each room either had 1 new guest, or not a new guest?
Does it matter that a room had a previous guest or not?

I guess we might also look at the map of all guests to the rooms.
Afterwards all rooms are occupied by exactly 1 guest, so the map is injective.

Originally Posted by mathmari
As for the surjectivity. As for the rooms of the old guests, only the odd room umbers have a preimage and so the map is not surjective. As for the rooms of the new guests, only the even roomn umbers have a preimage and so the map is not surjective.

Is that correct?
The initial map of old guests to rooms is surjective, isn't it?
After they have moved, the map of old guests to rooms is indeed not surjective.
And the map of new guests to rooms is indeed not surjective either.

I wonder if the map of all guests to rooms is surjective.

Originally Posted by Klaas van Aarsen
I think we are talking about the set of old guests, the set of newly arriving guests, and the set of rooms yes?
If so, then initially all rooms were occupied by exactly 1 old guest.
So the initial map of old guests to rooms is both injective and surjective.
After the old guests were moved to new rooms, each room had either an old guest, or no guest.
So the new map of old guests to rooms is injective.

I guess we might also look at the map of all guests to the rooms.
Afterwards all rooms are occupied by exactly 1 guest, so the map is injective.

The initial map of old guests to rooms is surjective, isn't it?
After they have moved, the map of old guests to rooms is indeed not surjective.
And the map of new guests to rooms is indeed not surjective either.
Ah ok!!

Originally Posted by Klaas van Aarsen
I wonder if the map of all guests to rooms is surjective.
In this case all the rooms are occupied and that would mean that the map of all guests to rooms is surjective, or not?

7. Originally Posted by mathmari
In the last case with the infinitely many busses we use the formula $2^{i}\left (2(j-1)+1\right )$ where $i$ is the place in the bus and $j$ is the number of the bus.

Using this we get \begin{equation*}\begin{matrix} \text{Place}/\text{Bus} & 1. \text{ Bus} & 2. \text{ Bus} & 3. \text{ Bus} & 4. \text{ Bus} & 5. \text{ Bus} & \ldots \\ 1 & 2 & 6 & 10 & 14 & 18 & \ldots \\ 2 & 4 & 12 & 20 & 28 & 36 & \ldots \\ 3 & 8 & 24 & 40 & 56 & 72 & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \end{matrix}\end{equation*}
Originally Posted by mathmari
In this case all the rooms are occupied and that would mean that the map of all guests to rooms is surjective, or not?
I was looking at your formula for infinitely many buses.
It makes me wonder if every even room gets a guest assigned to it.

Originally Posted by Klaas van Aarsen
I was looking at your formula for infinitely many buses.
It makes me wonder if every even room gets a guest assigned to it.
How can we check that?

9. Originally Posted by mathmari
How can we check that?
For surjectivity we have to verify if every even number can be written in the form of your formula, so that there is at least 1 guest that gets the room with that number.
Btw, for injectivity we should also verify that it cannot happen that 2 guests are assigned to the same room with an even number.

Each number can be written uniquely as a power of 2 multiplied by an odd number can't it?
It follows from the fundamental theorem of arithmetic, also known as the unique factorization theorem, doesn't it?

Does it mean that we can always find a bus passenger for an even room?