希尔伯特旅馆悖论（综述）

贡献者：待更新

　　本文根据 CC-BY-SA 协议转载翻译自维基百科相关文章。

　　希尔伯特的大酒店悖论（口语化：无限酒店悖论或希尔伯特的酒店）是一个思想实验，用来说明无限集合的一个违反直觉的性质。实验表明，即使一个完全占满的酒店有无限多的房间，它仍然可以容纳更多的客人，甚至是无限多的客人，而且这一过程可以无限次地重复。这个想法由大卫·希尔伯特在 1925 年的讲座《关于无限》中提出，并在《希尔伯特 2013 年论文集》（第 730 页）中重印，后来通过乔治·伽莫夫 1947 年的书籍《一二三……无限》得到了广泛传播。[1][2]

1. 悖论

　　希尔伯特设想了一个假想的酒店，房间按 1、2、3 等顺序编号，且没有上限。这被称为可数无限数量的房间。最初，每个房间都已被占满，但新客人到来，每个人都希望拥有自己的房间。一个正常的、有限的酒店在每个房间都已满员时无法容纳新客人。然而，可以证明，现有的客人和新来的客人——即使是无限多的——都可以在这个无限酒店里各自拥有一个房间。

有限数量的新客人

　　如果有一个额外的客人，酒店可以容纳他们和现有的客人，只需要让所有现有客人同时换房。现在在 1 号房间的客人移到 2 号房间，在 2 号房间的客人移到 3 号房间，依此类推，把每个客人从他们当前的房间 n 移到房间 n+1。由于无限酒店没有最终房间，所以每个客人都有新的房间可以去。这样一来，1 号房间就空了，新客人可以被安排到这个房间。通过重复这个过程，就可以为任何有限数量的新客人腾出房间。一般来说，当有 k 个客人需要房间时，酒店可以应用相同的程序，把每个客人从房间 n 移到房间 n+k。

无限多的新客人

图 1：通过将每个客人移动到他们之前房间号的两倍位置，可以容纳无限数量的新客人。

　　同样也可以容纳可数无限多的新客人：只需将占用 1 号房间的人移到 2 号房间，将占用 2 号房间的人移到 4 号房间，通常，将占用 n 号房间的人移到 2n 号房间（n 的两倍），这样所有奇数编号的房间（它们是可数无限的）就会空出来，供新客人使用。

无限多的车厢，每个车厢有无限多的乘客

　　可以通过几种不同的方法容纳可数无限多的车厢，每个车厢有可数无限多的乘客。大多数方法依赖于车厢中的座位已经编号（或使用可数选择公理）。一般来说，任何配对函数都可以用来解决这个问题。对于这些方法中的每一种，考虑乘客在车厢中的座位号为 $n$ ，车厢号为 $c$ ，然后将 $n$ 和 $c$ 输入配对函数的两个参数。

　　 质数幂法

　　将房间 $i$ 的客人送到房间 $2^{i}$ ，然后将第一车厢的乘客放入房间 $3^{n}$ ，第二车厢的乘客放入房间 $5^{n}$ ；一般来说，对于车厢号 $c$ ，我们使用房间 $p_{c}^{n}$ ，其中 $p_{c}$ 是第 $c$ 个奇质数。这个解决方案会留下某些空房间（这些空房间可能对酒店有用，也可能无用）；具体来说，所有不是质数幂的数字，比如 15 或 847，将不再被占用。（因此，严格来说，这表明到达的客人数量小于或等于创造的空房间数量。通过独立的方式更容易证明，到达的客人数量也大于或等于空房间数量，因此它们是相等的，而不是修改算法使其精确匹配。）（如果交换 $n$ 和 $c$ ，该算法同样有效，但无论选择哪个，都必须在整个过程中统一应用。）

　　 质因数分解法

　　每个乘客根据其座位 $s$ 和车厢 $c$ 可以被安排到房间 $2^{s} 3^{c}$ （假设对于已经在酒店的客人， $c = 0$ ，对于第一车厢的乘客， $c = 1$ ，依此类推）。由于每个数字都有唯一的质因数分解，可以很容易地看出所有人都会有自己的房间，且没有两个人会被安排到同一个房间。例如，房间 2592（ $2^{5} 3^{4}$ ）的客人原本坐在第四车厢的第五个座位。像质数幂方法一样，这种解决方案也会留下某些空房间。

　　这种方法也可以很容易地扩展到无限晚、无限次进出等情况（ $2^{s} 3^{c} 5^{n} 7^{e} \dots$ ）。

　　 交错法

　　对于每个乘客，将 $n$ 和 $c$ 的长度进行比较，采用任何位置数字系统，如十进制。（将每个酒店住客视为车厢 #0 的乘客。）如果某个数字较短，则在前面加零，直到两个数字的位数相同。将这些数字交错排列以生成房间号：其数字将是 [车厢号的第一位数字] - [座位号的第一位数字] - [车厢号的第二位数字] - [座位号的第二位数字] - 依此类推。酒店（车厢 #0）中房间号为 1729 的住客将被转到房间 01070209（即房间 1,070,209）。车厢 789 中座位 1234 的乘客将转到房间 01728394（即房间 1,728,394）。

　　与质数幂方法不同，这种方法将完全填满酒店，并且我们可以通过逆向交错过程重建乘客的原始车厢和座位号。首先，如果房间号的数字位数是奇数，则在前面加零。然后将该数字解交错为两个数字：车厢号由奇数位数字组成，座位号由偶数位数字组成。当然，原始编码是任意的，两个数字的角色可以互换（座位号为奇数位，车厢号为偶数位），只要一致地应用即可。

　　 三角形数法

　　酒店中已经住客的房间号将被移动到 $n^{2} + n / 2$ ，即第 $n$ 个三角形数。车厢中的乘客将被安排在房间号 $(c + n - 1)^{2} + c + n - 1 / 2 + n$ ，即 $(c + n - 1)$ 个三角形数加上 $n$ 。通过这种方式，所有的房间都将被填满，并且每个房间只会有一个住客。

　　这个配对函数可以通过将酒店结构化为一个深度为一层、无限高的金字塔来直观展示。金字塔的最顶层是一个房间：房间 1；第二层是房间 2 和 3；以此类推。由最右侧房间组成的列将对应于三角形数。一旦这些房间被填满（通过酒店住客的重新分配），剩余的空房间将形成一个与原始形状完全相同的金字塔形状。因此，整个过程可以对每个无限集合重复进行。虽然一次处理每个车厢需要无限的步骤，但通过使用先前的公式，乘客可以确定他们的房间 “将会是” 哪个房间，一旦他们的车厢到达该过程，就可以直接前往。

　　 任意枚举法

　　令 $S := {(a, b) ∣ a, b \in N}$ 。由于 $N$ 是可数的，因此 $S$ 也是可数的，因此我们可以对其元素进行枚举 $s_{1}, s_{2}, \dots$ 。现在，如果 $s_{n} = (a, b)$ ，则将第 $a$ 个车厢的第 $b$ 个客人分配到第 $n$ 个房间（将酒店中已经入住的客人视为第 0 个车厢的客人）。这样我们就得到了一个将每个客人分配到房间的函数；此外，这种分配不会跳过任何房间。

更高层次的无限

　　假设这家酒店旁边有一片海洋，无限多的汽车渡轮到达，每艘渡轮上都有无限多的车厢，每个车厢内有无限多的乘客。这是一个涉及三个 “层次” 无限的问题，可以通过扩展前述的任何解决方案来解决。

　　质因数分解法可以通过为每增加一个无限层次而添加一个新的质数来应用（如 $2^{s} 3^{c} 5^{f}$ ，其中 $f$ 是渡轮的编号）。

　　质幂解法可以通过对质数进行进一步的指数运算来应用，这会导致即使是小的输入也会得到非常大的房间号码。例如，第二艘渡轮上第三辆巴士的第二个座位上的乘客（地址 2-3-2）将把第二个奇质数（5）提高到 49，这个数字是第三个奇质数（7）提高到他的座位号（2）的结果。这个房间号码将有超过三十个十进制数字。

　　交错法则可以通过三个交错的 “线程” 而不是两个来使用。地址为 2-3-2 的乘客将被分配到房间 232，而地址为 4935-198-82217 的乘客将被分配到房间 #008,402,912,391,587（可以去掉前导零）。

　　为了预见到任何层数的无限乘客到达，酒店可能希望分配房间，以确保无论后来有多少客人到达，现有的客人都不需要搬动。一个解决方案是将每个到达的客人的地址转换为二进制数字，其中 1 用作每个层次的分隔符，而每个层次中的数字（例如客人的车厢编号）则用相应数量的零表示。因此，一个地址为 2-5-1-3-1（五个无限层次）的客人将被分配到房间 10010000010100010（二进制，十进制为 295458）。

　　作为此过程的附加步骤，可以从每个数字部分中去掉一个零；在这个例子中，客人的新房间是 101000011001（二进制，十进制为 2585）。这样做确保了每个房间都可以被一个假设的客人填满。如果没有无限多的客人到达，那么只有那些编号为二的幂次的房间会被占用。

2. 分析

　　希尔伯特的悖论是一个真实悖论：它导致了一个反直觉的结果，但这个结果是可以证明的。“每个房间都有一个客人” 和 “无法容纳更多的客人” 这两个陈述在存在无限多个房间时并不等价。

　　最初，这种情况可能看起来是反直觉的。无限集合的性质与有限集合的性质是非常不同的。希尔伯特的 “大酒店” 悖论可以通过使用康托尔的超有限数理论来理解。因此，在一个普通（有限）的酒店中，如果有多个房间，那么奇数号房间的数量显然小于房间的总数。然而，在希尔伯特的大酒店中，奇数号房间的数量并不小于所有房间的 “数量”。用数学术语来说，包含奇数号房间的子集的基数与所有房间的基数是相同的。事实上，无限集合的特点就是它们有与自身基数相同的真子集。对于可数集合（与自然数集合基数相同的集合），这个基数是ℵ₀（阿列夫零）。

　　换句话说，对于任何可数的无限集合，都存在一个双射函数，将可数的无限集合映射到自然数集合，尽管该可数集合包含自然数。例如，有理数集合——可以表示为整数商的数——包含自然数作为子集，但它的大小并不超过自然数集合，因为有理数是可数的：从自然数到有理数之间存在一个双射。

3. 另见

悖论列表 – 一系列看似自相矛盾的陈述
巴拿赫–塔尔斯基悖论 – 几何定理
伽利略悖论 – 集合论中的悖论
集合论的悖论
鸽巢原理 – 如果物品的数量超过了容纳它们的盒子数量，则至少有一个盒子必须包含两个以上的物品

4. 参考文献

Kragh, Helge (2014). "The True (?) Story of Hilbert's Infinite Hotel". arXiv:1403.0059 [physics.hist-ph].
Gamow, George (1947). *One Two Three... Infinity: Facts and Speculations of Science*. New York: Viking Press. 第 17 页.
Rucker, Rudy (1984) [1982]. *Infinity and the Mind. The Science and Philosophy of the Infinite*. Paladin. 第 73–78 页. ISBN 0-586-08465-7.

Hilbert, David (2013), Ewald, William; Sieg, Wilfried (编辑), *David Hilbert's Lectures on the Foundations of Arithmetics and Logic 1917-1933*, Heidelberg: Springer-Verlag, doi:10.1007/978-3-540-69444-1, ISBN 978-3-540-20578-4.