1
$\begingroup$

To fit an infinite number of coaches each with an infinite number of passengers, we can assign the people in the hotel with the prime number 2, and coach $c$ is assigned with the $c$th odd prime number, and the $p$th person on a particular coach is assigned the room number $c^p$. By the fundamental theorem of arithmetic, every person is assigned a unique room.

However, this leaves some rooms empty, and so we have not produced a bijective mapping from people to rooms. On the wikipedia article for Hilbert's hotel, the presence of empty rooms means that we have proved that the number of rooms is greater than or equal to the number of guests. I would think that this process that the number of rooms is strictly larger than the number of guests, since there are empty rooms, but everyone has a room.

How can it be that the prime powers method hasn't shown that the cardinality of the set of rooms is strictly greater than the cardinality of the set of guests?

$\endgroup$
1
  • $\begingroup$ Note: If you allocate the $r^{th}$ person on the $k^{th}$ bus the room $2^{k-1}(2r-1)$ you should fill all the rooms. The first bus goes to the odd rooms, the second to those which are twice odd, the third to four times odd etc. $\endgroup$
    – Mark Bennet
    Commented Jul 5, 2015 at 16:44

1 Answer 1

Reset to default
5
$\begingroup$

The fact that you found one injective function which is not surjective does not mean that there are no other functions which are injective but not surjective.

For example, $f(n)=n+2$ is an injective function from $\Bbb N$ into $\Bbb N\setminus\{0\}$, but it is not surjective. Does that mean there are not bijections? No, for example $g(n)=n+1$ is a bijection.

Note that this is contrary to the same statement about finite sets. But our intuition, the one we come with before studying mathematics, is very grounded in our finite reality and finite experience. So it kinda sucks for infinite sets. There will simply need to work with the definition, until at some point we develop some rudimentary intuition, and then less-rudimentary intuition.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .