Skip to main content
Mathematics LibreTexts

9.4: Hotel Infinity and the Cardinality of Infinite Sets

  • Page ID
    23937
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    The above discussion of cardinality included the following important fact that appeared in Proposition \(9.1.9\):

    Two finite sets \(A\) and \(B\) have the same cardinality if and only if there is a bijection from \(A\) to \(B\).

    Extending this property to all sets (not just the finite ones) is the definition of cardinality for infinite sets:

    Definition \(9.4.1\).

    Two sets \(A\) and \(B\) have the same cardinality iff there exists a bijection from \(A\) to \(B\).

    Two main ideas will be developed in the remainder of this chapter:

    1. Many sets have the same cardinality as \(\mathbb{N}^{+}\). These are the smallest infinite sets, and they are said to be countably infinite.
    2. Not all sets are countably infinite: some sets are more infinite than others! These sets are said to be uncountable.

    Let us begin with an informal discussion of some of the ideas that are involved in countability, rather than looking at the official definition right away. First, a simple example involving finite sets.

    Example \(9.4.2\).

    Suppose a hotel has n rooms, numbered \(1,2,3, \ldots, n\).

    1. If \(A\) is a tour group of \(n\) people \(a_{1}, a_{2}, \ldots, a_{n}\), then the hotel clerk will obviously have no trouble assigning each of the people a room: \(a_{i}\) can be put in room \(i\). There will be no empty rooms left.
      clipboard_e122265d5d1a1bd46a9257cd8250b6136.png
    2. Now, if another person \(b\) arrives who wants a room, then the situation is hopeless. There is no way to give each of these \(n+ 1\) people a room, without making two of them share a room. In general:
      If there are more guests than hotel rooms, then not everyone can have a room.
      This is a restatement of the Pigeonhole Principle \((9.2.1)\)SS.
    Example \(9.4.3\) (Hotel Infinity).

    Now consider a hotel with infinitely many rooms, numbered \(1,2,3, \ldots\). (There is one room for each \(i \in \mathbb{N}^{+}\).)

    1. If \(A\) is a tour group of \(n\) people \(a_{1}, a_{2}, \ldots, a_{n}\), then the hotel clerk will obviously have no trouble giving each of the people a room: \(a_{i}\) can be put in room \(i\). There will be lots of empty rooms left over.
      clipboard_eb3b04728bac7255d2bfa251e7a68d2e6.png
    2. Even if \(A\) is infinite, rather than finite, with people \(a_{1}, a_{2}, \ldots\), the hotel clerk can accommodate all of them, by putting \(a_{i}\) in room \(i\). There will be no empty rooms left.
      clipboard_ed1c5ac7d5dd9d5a766839989fe26cf01.png
    3. Now suppose that, in addition to this tour group, there is another person \(b\) who also wants a room. Even though the hotel is already full, the hotel clerk can handle this situation quite easily, by shifting everyone to the next room, to make space for \(b\). That is, the clerk can put \[b \text { into room } 1 \text { and } a_{i} \text { in room } i+1 \text {. }\]
      Everyone will have his or her own room.
      clipboard_ed72140e3369dada470004e144b0add34.png
    4. The same idea works, even if, instead of just one person, there is a whole group \(B\) of \(n\) people \(b_{1}, b_{2}, \ldots, b_{n}\) that want rooms. The clerk can put \[b_{j} \text { in room } j, \quad \text { and } \quad a_{i} \text { in room } i+n \text {. }\]
      clipboard_e0680c2a2ef92e8bc7fc859158b672342.png
    5. It may seem that there would be a problem if the second group \(B\) consists of infinitely many people \(b_{1}, b_{2}, b_{3}, \ldots\), but a clever hotel clerk can accommodate even this situation. Note that there are infinitely many odd-numbered rooms, so all of \(A\) can be put in those rooms, and there are also infinitely many even-numbered rooms, so all of \(B\) can be put in there. More precisely, the clerk can put \[a_{i} \text { in room } 2 i-1, \quad \text { and } \quad b_{j} \text { in room } 2 j \text {. }\]
      clipboard_eede67c73df7d162d2f8bcb7d3a327411.png
    6. Even if there are several of these countably infinite tour groups, not just 2 of them, they can all be accommodated. Namely, suppose there are \(n\) tour groups \(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\), and make a table (or matrix) with \(n\) infinitely long rows that lists the elements of \(A_{i}\) in the \(i\)th row. That is, if \(a_{i, 1}, a_{i, 2}, a_{i, 3}, \ldots\) is a list of the people in \(A_{i}\), then the table looks like:
      \begin{array}{ccccccc}
      A_{1}: & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & \cdots \\
      A_{2}: & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} & \cdots \\
      A_{3}: & a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} & \cdots \\
      \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
      A_{n}: & a_{n, 1} & a_{n, 2} & a_{n, 3} & a_{n, 4} & a_{n, 5} & \cdots
      \end{array}

    We can assign rooms \(1,2,3, \ldots\) to the entries of this table by counting down the 1st column (from 1 to \(n\)), then the 2nd column (starting at \(n + 1\)), then the 3rd column (continuing from where we left off after the 2nd column), etc., as indicated here:\[\begin{array}{cccccc}
    1 & n+1 & 2 n+1 & 3 n+1 & 4 n+1 & \cdots \\
    a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \cdots \\
    2 & n+2 & 2 n+2 & 3 n+2 & 4 n+2 & \cdots \\
    a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} & \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \cdots \\
    3 & n+3 & 2 n+3 & 3 n+3 & 4 n+3 & \cdots \\
    a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} & \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \cdots \\
    \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \cdots \\
    n & 2 n & 3 n & 4 n & 5 n & \cdots \\
    a_{n, 1} & a_{n, 2} & a_{n, 3} & a_{n, 4} & a_{n, 5} &
    \end{array}\]

    This assigns a different room number to each of the people, so everyone has their own room.

    Remarks.
    1. Another way for the hotel clerk to find this solution is to note that there are infinitely many numbers that are congruent to \(i\) modulo \(n\), so all of \(A_{i}\) can be put in those rooms.
    2. It can be seen that guest \(a_{i,j}\) is assigned to room \(i+ (j −1)n\), but we have no need for this formula.
    1. Going further, even if there were infinitely many infinite tour groups \(A_{1}, A_{2}, \ldots\), they could all be accommodated. (We assume that each tour group is countably infinite, and that the number of groups is countably infinite.) To see this, start by considering an infinitely large table (or matrix) that lists the elements of \(A_{i}\) in the \(i\)th row: \[\begin{array}{ccccccc}
      A_{1}: & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & \cdots \\
      A_{2}: & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} & \cdots \\
      A_{3}: & a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} & \cdots \\
      A_{4}: & a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} & \cdots \\
      A_{5}: & a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} & \cdots \\
      \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
      \end{array}\]
      We can assign rooms \(1,2,3, \ldots\) to the entries of this table as follows:
      • Begin with 1 in the top left corner.
      • Then place 2 at the top of the second column and move diagonally (down and to the left) to place 3.
      • Then place 4 at the top of the third column, and move diagonally (down and to the left) to place 5 and 6.
      • Then place the next number (namely, 7) at the first open spot in the top row (namely, at the top of the fourth column), and move diagonally (down and to the left) to place the following numbers (namely, 8, 9, and 10), until a number (namely, 10) is placed in the first column.
      • Continue by moving to the first open spot in the top row, and repeating infinitely.
        clipboard_efe2ae33b99a17d7ee8d6b38ec6bfbf42.png

    No entries of the table are omitted from the numbering, and no room numbers are repeated, so each guest has his or her own room.

    Remark

    It can be shown that guest \(a_{i,j}\) is put into room ( i+j−1 2 ) + i, but we have no need for this formula.

    It might seem that Hotel Infinity could accommodate every set of tourists, but that is not the case. For example, we will see in Section \(9.6\) that if all of the real numbers want rooms at the hotel, then some of them will have to share. In other words, the set \(\mathbb{R}\) of real numbers is uncountable.

    OTHER TERMINOLOGY.

    Hotel Infinity is often called “Hilbert’s Hotel,” in honour of the German mathematician David Hilbert (1862–1943), who was apparently the first to talk about such a hotel (in lectures in Germany in 1924).


    This page titled 9.4: Hotel Infinity and the Cardinality of Infinite Sets is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

    • Was this article helpful?