对角线方法之后的故事

2011 年 12 月 7 日 / 53 条评论

同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：

事实上，实数区间 (0, 1) 就已经是一个不可数的集合了。换句话说，你绝不可能用“第一个数是某某某，第二个数是某某某”的方式把 0 到 1 之间的所有实数一个不漏地列举出来。我们大致的证明思路是，假设你把实数区间 (0, 1) 里的所有数按照某种顺序排列起来，那么我总能找到至少一个 0 到 1 之间的实数，它不在你的列表里，从而说明你的列表并不全。把你的列表上的数全写成 0 到 1 之间的无限小数（如果是有限小数，可以在其后面添加数字 0 ，把它变成无限小数）：

a₁ = 0.0147574628…
a₂ = 0.3721111111…
a₃ = 0.2323232323…
a₄ = 0.0004838211…
a₅ = 0.0516000000…
………

那么我就构造这么一个小数，小数点后第一位不等于 a₁ 的第一位，小数点后第二位不等于 a₂ 的第二位，总之小数点后第 i 位不等于 a_i 的第 i 位。这个数属于实数区间 (0, 1) ，但它显然不在你的列表里，因为它和你列表里的每一个数都有至少一位是不同的。这样，我们就证明了实数区间是不可数的。

经典证明：能否在平面上写下不可数个不相交的Y？

2011 年 11 月 9 日 / 31 条评论

这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题：是否有可能在平面上画不可数个不相交的 8 ？答案是否定的。证明方法非常简单。对于任意一个 8 字形，在两个洞里各取一个有理点 P 、 Q （由于平面上的有理点是稠密的，这是总能办到的），则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交，因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的，因此 8 字形的数量也是可数的。

注意到，平面上显然能够容下不可数个不相交的直线段，也显然能够容下不可数个不相交的圆（比方说一系列同心圆）。在 Mathematical Puzzles 一书里， Peter Winkler 提出了这样一个问题：我们能在平面上写下不可数个不相交的字母 Y 吗？

用选择公理来预测未来

2010 年 5 月 13 日 / 45 条评论

承认选择公理可能给我们带来很多有悖于直觉的结论。最著名的例子可谓 Banach-Tarski 悖论了：你可以把一个三维的实心球分成有限多块，通过刚体移动把它变成两个和原来一模一样的球。本 Blog 还介绍过另外一个有趣的结论，它违背常理的程度也不亚于 Banach-Tarski 悖论。今天，我给大家看一个比这些悖论更加荒唐的结论：利用选择公理，我们可以实现预测未来！

在探讨这个话题之前，我们得先为“预测未来”建立一个合理的数学模型。我们假设，对于任一时刻，宇宙中的所有信息都可以编码为某个状态值，我们就把它叫做宇宙的一个“点状态”。宇宙中所有可能的点状态就组成了宇宙的“状态集合”。以数学的眼光看宇宙，一个宇宙也就无非是一个一元函数 f(t) 。它的定义域是整个时间轴 R ，它的值域是宇宙的状态集合，预测未来也就仅仅是根据已知的函数值来推测未知的函数值罢了。假设我们已经知道在区间 (-∞, t0) 上函数的所有取值，如果你能据此给出 f(t0) 的精确值，我们就说你成功地预测了 t0 时刻的宇宙状态。当然，仅凭借过去的信息你是不可能保证猜对 t0 时刻的点状态的，例如对于两个只在 t0 处有区别的宇宙，算法最多只能猜对其中一个宇宙在 t0 处的状态。但你相信吗，存在一个算法，使得我能正确预测几乎所有时间点的宇宙状态。换句话说，我能构造出这样一个算法，使得除了可数个点以外，给定任意一点以前的全部函数值，我都能套用该算法猜对该点的点状态。再换句话说，利用这个算法预测任意时刻的宇宙状态，成功的概率为 1 。

Sierpinski-Mazurkiewicz悖论：一加一还是等于一

2010 年 3 月 27 日 / 35 条评论

大家或许知道 Banach-Tarski 悖论——把一个三维球分成有限多份并重新拼成两个和原来一模一样大的球——这个悖论告诉我们利用选择公理我们能够推出看上去多么不合逻辑的东西。今天我听说了另一个类似的悖论叫做 Sierpinski-Mazurkiewicz 悖论，它的结论在直观上同样令人难以接受，并且推导不依赖于选择公理。
Sierpinski-Mazurkiewicz 悖论是说，存在平面上的一个点集 S ，我们能把它划分成两个子集 A 和 B ，使得 A 旋转 1 弧度后与 S 完全重合， B 平移一个单位后也与 S 完全相同。换句话说，存在这么一个点集，我们能把它分成两个与自身一模一样的子集！这听上去实在是不可思议，然而构造却极其简单。

经典证明：任何可数集都含有不可数个嵌套子集

2009 年 11 月 14 日 / 19 条评论

你相信吗？对于任意一个可数集，总能找出不可数个子集，使得从中任取两个集合，其中一个都是另一个的真子集。乍看之下，这似乎是不可能的。如果任两个集合之间都具有“其中一个是另一个的真子集”的关系，那它们就能构成一个“集合序列”（准确地说是全序关系），使得每个集合都是由它前面那个集合添加进若干元素得到；换句话说，我们能通过不断往一个空集中添加新的元素依次得到所有这些集合。但是如果这些集合中的元素就只有可数个，那这个“集合序列”中怎么会有不可数个集合呢？然而，涉及到无穷的问题总是那样违背直觉。下面我们只用三行字就能说明，这个命题的的确确是成立的。