Kenneth H. Rosen. 徐六通, 杨娟 , 吴斌 译. 离散数学及其应用（原书第7版），中文版，机械工业出版社，2015.1。

引用：https://www.sohu.com/a/257182638_814235

希尔伯特旅馆悖论（Hilbert's paradox of Grand Hotel）

希尔伯特旅馆有无限个房间，并且每个房间都住了客人。一天来了一个新客人，旅馆老板说：“虽然我们已经客满，但你还是能住进来的。我让 1 号房间的客人搬到 2 号房间，2 号房间搬到 3 号房间⋯⋯n 号房间搬到 n+1 号房间，你就可以住进 1 号房间了。”又一天，来了无限个客人，老板又说：“不用担心，大家仍然都能住进来。我让 1 号房间的客人搬到 2 号房间，2 号搬到 4 号，3 号搬到 6 号⋯⋯n 号搬到 2n 号，然后你们排好队，依次住进奇数号的房间吧。”

这就是德国大数学家大卫·希尔伯特（David Hilbert）提出的著名悖论。每个学过集合论的学生，都应该“拜访”过这个奇妙的希尔伯特旅馆。虽然人们把它叫做一个“悖论”，它在逻辑上却是完全正确的，只不过大大出乎我们的意料罢了。一扯上无限，有趣的事说也说不完。意大利数学家伽利略（Galileo Galilei）在他的最后一本科学著作《两种新科学》（Two New Science）中提到一个问题：正整数集合 {1, 2, 3, 4, ⋯⋯} 和平方数集合 {1, 4, 9, 16, ⋯⋯} 哪个大呢？一方面，正整数集合里包含了所有的平方数，前者显然比后者大；可另一方面，每个正整数平方之后都唯一地对应了一个平方数，两个集合大小应该相等才对。伽利略比较早地使用了一一对应的思想，可惜没有沿着这个思路更进一步思考下去。最后他得出的结论就是，无限集是无法比较大小的。说到这里，我们不得不提到德国另一位伟大的数学家乔治·康托（George Cantor），他建立了集合论（set theory），并系统地研究了集合（尤其是无穷集合）的大小，只不过这个大小不是简单地叫做“大小”了，而是叫势（cardinality）。如果两个集合间的元素能建立起一一对应的关系，我们就说它们等势，这也是我们比较集合大小的方式。希尔伯特悖论形象地说明了正整数集合和正偶数集合是等势的。一切和自然数集合等势的集合都称为“可数集合”（countable set），否则就叫做“不可数集合”（uncountable set）。

托里拆利小号（Torricelli‘s Horn）

又到几何悖论时间了。上面这个小号状的图形有什么特点？

意大利数学家托里拆利（Evangelista Torricelli）将 y=1/x 中 x≥1 的部分绕着 x 轴旋转了一圈，得到了上面的小号状图形（注意，上图只显示了这个图形的一部分）。然后他算出了这个小号的一个十分牛 B 的性质——它的表面积无穷大，可它的体积却是 π。这明显有悖于人的直觉：体积有限的物体，表面积却可以是无限的！换句话说，填满整个托里拆利小号只需要有限的油漆，但把托里拆利小号的表面刷一遍，却需要无限多的油漆！

类似的二维几何悖论中，最著名的要属“科赫雪花”（Koch Snowflake）了。科赫雪花是一种经过无穷多次迭代生成的分形图形，下图就是前三次迭代的过程，迭代过程的极限便是科赫雪花了。它也有一个类似的性质：它的面积有限，周长却是无限的。用无限的周长包围了一块有限的面积，真是另类的“无中生有”啊！

芝诺悖论（Zeno's paradoxes）

芝诺悖论是由古希腊哲学家芝诺（Zeno）提出的一组悖论。其中的几个悖论还可以在亚里士多德（Aristotle）的《物理学》（Physics）一书中找到。最有名的是以下两个。

阿基里斯与乌龟的悖论（Achilles and the tortoise Paradox）：在跑步比赛中，如果跑得最慢的乌龟一开始领先跑得最快的希腊勇士阿基里斯，那么乌龟永远也不会被阿基里斯追上。因为要想追到乌龟，阿基里斯必须先到达乌龟现在的位置；而等阿基里斯到了这个位置之后乌龟已经又前进了一段距离。如此下去，阿基里斯永远追不上乌龟。

二分法悖论（Dichotomy Paradox）：运动是不可能的。你要到达终点，必须首先到达全程的 1/2 处；而要到达 1/2 处，必须要先到 1/4 处⋯⋯每当你想到达一个点，总有一个中点需要先到，因此你是永远也到不了终点的。其实，你根本连动都动不了，运动是不可能的。

罗素（Bertrand Russell）曾经说过，这组悖论“为从他那时起到现在所创立的几乎所有关于时间、空间以及无限的理论提供了土壤”。阿尔弗雷德·诺斯·怀特海德（Alfred North Whitehead）这样形容芝诺：“知道芝诺的人没有一个不想去否定他的，所有人都认为这么做是值得的”，可见争议之大。无数热爱思考的人也被这些悖论吸引，试图给这些出人意料的结论以合理的解释。

当古希腊哲学家第欧根尼（Diogenes）听到芝诺的“运动是不可能的”这个命题时，他开始四处走动，以证明芝诺的荒谬，可他并没有指出命题的证明错在哪里。

亚里士多德对阿基里斯悖论的解释是：当追赶者与被追者之间的距离越来越小时，追赶所需的时间也越来越小。他说，无限个越来越小的数加起来的和是有限的，所以可以在有限的时间追上。不过他的解释并不严格，因为我们很容易举出反例：调和级数 1+1/2+1/3+1/4+…… 的每一项都递减，可是它的和却是发散的。

阿基米德（Archimedes）发明了一种类似于几何级数求和的方法，而问题中所需的时间是成倍递减的，正是一个典型的几何级数，所以追上的总时间是一个有限值。这个悖论才总算是得到了一个过得去的解释。直到 19 世纪末，数学家们才为无限过程的问题给出了一个形式化的描述。

尽管我们可以用数学方法算出阿基里斯在哪里以及什么时候追上乌龟，但一些哲学家认为，这些证明依然没有解决悖论提出的问题。出人意料的是，芝诺悖论在作家之中非常受欢迎，列夫·托尔斯泰在《战争与和平》中就谈到了阿基里斯和乌龟的故事，路易斯·卡罗尔（Lewis Carroll）写了一篇阿基里斯和乌龟之间的对话，阿根廷作家豪尔赫·路易斯·博尔赫斯（Jorge Luis Borges）也多次在他的作品中谈到阿基里斯悖论。

球与花瓶（Balls and Vase Problem）

我们有无限个球和一个花瓶，现在我们要对它们进行一系列操作。每次操作都是一样的：往花瓶里放 10 个球，然后取出 1 个球。那么，无穷多次这样的操作之后，花瓶里有多少个球呢？

有人或许会说，这个问题显然是荒谬的——这个过程需要耗费无穷的时间，我们不可能等到那个时候。那么，我们不妨换一个问法，避开所需时间无穷的问题：在差一分钟到正午 12 点时进行第 1 次操作，在差 30 秒（1/2 分钟）到正午 12 点时进行第 2 次操作，在差 1/2 n-1 分钟到 12 点时进行第 n 次操作。那么，12 点的时候，花瓶里有几个球呢？

看似简单的描述，经过数学家的解释，却出现了千奇百怪的答案。最直观的答案当然就是花瓶里有无限个球了，因为每次都增加了 9 个球，无限次之后，当然有无限个球。数学家 Allis 和 Koetsier 却不这么认为。他们认为，12 点时瓶子里没有球，因为我们第 1 次放进 1 至 10 号球，然后取出 1 号球，第 2 次放入 11 至 20 号球，然后取出 2 号球⋯⋯注意到，n 号球总是在第 n 次操作时被取出来了，因此无限操作下去，每个球都会被取出来！细心的读者会发现，这个说法也有问题：前面的证明假设我们取出的依次是 1 号球、2 号球、3 号球等等，如果我们改成依次取 10 号球、20 号球、30 号球，那么最后瓶子里又出现了无限个球了。哪种观点是正确的呢？于是逻辑学家詹姆斯·亨勒（James M. Henle）和托马斯·泰马祖科（Thomas Tymoczko）认为，花瓶里有任意个球。他们还给出了具体的构造方法，说明最终花瓶里的球可以是任意数目。

1953 年，这个悖论由英国数学家利特尔伍德（John Edensor Littlewood）在他的书《一个数学家的集锦》（A Mathematician‘s miscellany）中首先提出，1976 年谢尔登·罗斯（Sheldon Ross）在他的《概率论第一课》（A First Course in Probability）又一次介绍了这个问题，所以它又被称为“罗斯·利特尔伍德悖论”（Ross-Littlewood Paradox）。

无限长的杆（Infinite Rod）

有一张无限大的桌子，上面竖直地插着一根有限长的支柱。然后取一根无穷长的金属杆，把它的一头铰接在支柱顶端，另一头则伸向无穷远处。金属杆可以绕着支柱顶端自由地上下转动。假设金属杆和桌子都是无比坚硬的刚体。你会发现，这根无限长的金属杆根本不会往下转动！因为金属杆和桌子都很坚硬，如果它们相交，必然会损坏一个，所以唯一的办法就是金属杆与桌面平行。那么我们看到的现象就是一根无限长的金属杆，在空中仅仅靠一个点就保持水平！

这个有趣的问题是由数学家雷蒙德·斯穆里安（Raymond Smullyan）在一本庆祝马丁·加德纳 90 岁生日的书中介绍的。另外，如果我们把铰接的点移到金属杆的中部，那么金属杆就动弹不得，稳稳地和桌面平行了