康托尔对角线论证：为何实数无法被列举
假设有人递给你一份列表，一份无穷列表，声称它包含了 0 到 1 之间的每一个实数。不是样本，不是选集：每一个实数，整整齐齐地编了序号，记作 r1、r2、r3，如此无穷无尽。
格奥尔格·康托尔在 1891 年的回应是这样的：无论你递给我什么列表，我都能读出一个不在上面的数。这个构造只需大约三十秒就能描述完。它的后果却让数学家们消化了数十年，因为它意味着无穷不止一种大小。
计数与列举
在对角线操作之前，有必要精确理解「可数」的含义。一个集合是可数的，当且仅当你能给每个元素分配一个唯一的自然数标签：第一个、第二个、第三个，依此类推，不留任何遗漏。自然数本身按定义是可数的，整数也是（按 0, 1, -1, 2, -2, ... 的顺序列出），甚至有理数也是，虽然列出每个分数需要一种巧妙的之字形路径。
康托尔的论证表明，0 到 1 之间的实数是真正不同的：无论怎么尝试，都不存在这样的标记。这不是想象力的失败，而是一个证明：这项任务根本不可能完成。
假设列表存在
这个论证是反证法。先把对方想要的一切都给他：假设 (0, 1) 中每个实数的完整列表确实存在。把每个数写成无穷小数展开形式。
列表可能是这样开头的：
- r1 = 0.14159265...
- r2 = 0.73205080...
- r3 = 0.00000000...
- r4 = 0.27182818...
- r5 = 0.91415926...
- ...
每一项都无穷无尽，列表本身也无穷无尽。按照假设，0 到 1 之间的每一个实数都出现在其中某处。
现在来看，沿对角线读下去会发生什么。
读取对角线
看 r1 的第一位小数、r2 的第二位小数、r3 的第三位小数，依此类推。在上面的例子中，这些对角线上的数字依次是：1、3、0、2、9……
现在逐位构造一个新数，记作 d。规则：对每个对角线上的数字，选取一个不同的数字，但刻意避开 0 和 9。
| r₁ | 0 | . | 1 | 4 | 1 | 5 | 9 | |
| r₂ | 0 | . | 3 | 3 | 3 | 3 | 3 | |
| r₃ | 0 | . | 5 | 0 | 0 | 0 | 0 | |
| r₄ | 0 | . | 7 | 1 | 8 | 2 | 8 | |
| r₅ | 0 | . | 6 | 0 | 2 | 5 | 9 | |
| new | 0 | . | 2 | 4 | 1 | 3 | 8 | … |
Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.
对角线上的数字是 1、3、0、2、9，应用规则得到 2、4、1、3、8。所以 d = 0.24138...
避开 0 和 9 是一个微小但必要的保护措施。某些实数有两种小数表示：0.4999... 和 0.5000... 指向数轴上同一个点。把某一位翻转成 0 或 9，可能恰好落在列表中某个数的「另一个名字」上，那会让论证变模糊。把每位翻转后限制在 1 到 8 之间，就保证了 d 恰好有一种小数展开，下面的比较也就干净利落。
新数与列表中每一项都不同
这就是收获所在。
d 在第一位小数处与 r1 不同
d 的第一位被选得与 r1 的第一位不同。所以 d 不等于 r1，它们在第 1 位就已分道扬镳。
d 在第二位小数处与 r2 不同
d 的第二位被选得与 r2 的第二位不同。所以 d 不等于 r2，它们在第 2 位就已分道扬镳。
d 在第 n 位小数处与 rn 不同，对任意 n 均成立
按构造，d 的第 n 位与 rn 的第 n 位不同。由于在任意位置数字不同的两个数必然不相等，d 不等于任何你说得出的 rn。
这就是对角线操作：d 被设计成在每个列表条目最暴露的那一位，即它自己的对角线位置，与该条目产生冲突。
d 是 0 到 1 之间的实数，却不在列表上
数 d = 0.24138... 显然是区间 (0, 1) 中的一个实数。但我们刚才证明了，它与 r1、r2、r3，与每一个条目都不同。如果列表是完整的，d 就应该出现在某处，然而它并不在。所以列表并不完整。
矛盾十分尖锐：我们假设列表是完整的，却构造出了一个不在上面的实数。假设必然为假。0 到 1 之间实数的完整列表根本不可能存在。
这实际上说明了什么
数学家说自然数的基数是阿列夫零（用希伯来字母 ℵ₀ 表示，第一个超限基数）。实数的基数严格更大，有时记作 c，或 2 的阿列夫零次幂。康托尔的论证正是确立这两种无穷大小不相等的依据。
这在康托尔发表时引发了强烈争议。一些同行将其视为奇谈或错误。它两者都不是。它坐落在数学家思考集合、基数与实数轴结构的基础之上，并直接连接到关于什么能计算、什么不能计算的问题（另见古德斯坦定理，那是另一个可证为真却超出形式系统边界的例子）。
为什么对角线有效
这个论证的优美之处在于它的精确性。你不是在猜测某个缺失的数，也不是在诉诸「实数有多大」的模糊直觉。你是在读出列表中每一项所「控制」的那一个位置，然后构造一个在恰好那个位置逃脱每一项的数字。
列表自己告诉你该往哪里看。列表上的每一项都交出一个坐标，即它自己的对角线数字，构造过程将这些坐标变成一个列表无法容纳的数。
这种简洁具有迷惑性。这里不需要知道列表上的条目是什么，无论顺序还是选取方式都无关紧要。论证是普适的：取任意一份实数列表，对角线构造都能产生一个不在其中的实数。
禅意
康托尔的对角线论证属于数学中一长串「看起来不该奏效」的结果。你盯着证明，等待把戏、等待隐藏的假设、等待逻辑滑落的地方。它不在那里。证明正如它看起来那么简单。
它要求你接受的东西比证明本身更奇异：「无穷」并非单一的终点。整数和实数都是无穷，却是截然不同的两种无穷。对角线论证是划分它们的那条线。
要更深地感受无穷集合如何诡异地运作，无穷小数的结构是个好的去处，或者看看极限如何工作，序列永远趋近一个值却永远到不了。对角线论证属于同一个家族：在无穷的边缘，精确而耐心地审视那个直觉需要证明才能保持诚实的地方。
无穷不是一件事，这就是消息。传递它的论证，半页纸就够了。
常见问题
- 康托尔对角线论证证明了什么？
- 它证明了 0 到 1 之间的实数是不可数的：无论多聪明地构造列表，都无法把该区间内的每个实数包含进去。实数的数量多到无法与任何列表一一对应。
- 「不可数」是什么意思？
- 如果一个集合的每个元素都可以与一个自然数（1, 2, 3, ...）一一配对且不遗漏，则称它是可数的。自然数、整数，甚至有理数都是可数的。实数则不然：它们太多了，无法放进任何这样的一一对应关系中。
- 为什么不能直接把缺失的数加进列表？
- 可以加，但对角线论证随即对新的更长列表再次适用，又产生另一个缺失的数。对任何列表、无论多长或多精巧的排列，论证都成立，所以列表不可能通过补充变得完整。
- 翻转数字时为什么要避开 0 和 9？
- 某些实数有两种小数表示：0.4999... 和 0.5000... 代表同一个数。如果你把某位翻转成 0 或 9，可能恰好落在列表中某个数的「另一种写法」上。避开 0 和 9 绕开了这个技术细节，让证明更干净。
- 有理数也是不可数的吗？
- 不是。有理数是可数的：你可以系统地列出每个分数 p/q 并为每个分数分配一个自然数编号，不遗漏任何一个。康托尔的对角线论证针对的是实数，而不是有理数。
