康托尔错了：拆穿无穷集合的层级

作者：Vitalik Buterin，巴塞尔大学博士

一种常见的数学说法认为：无穷不是只有一种，而是存在一个无穷多层级的、不同等级的无穷。整数集合的大小就是单纯的"无穷"，有理数集合和整数一样大（因为你可以把每个有理数映射到一个整数——把分子分母的数字交错排列即可，例如 0.456456456… = 456/999 = 152/333 → 135323）；而实数集合的大小则是某种"更大的无穷"，因为根本无法在实数和整数之间建立类似的映射。

首先我得指出：要看出"不存在这种映射"这一说法是错的，其实相当容易。这里就有一个简单的映射。对于一个给定的实数，给我一个（确定性的）python 程序，它会逐位打印出这个数（例如对 π，可以是一个用无穷级数 π = 4 − 4/3 + 4/5 − 4/7 + … 计算出越来越好的近似的程序）。我可以把这个程序转换成一个数字（用 n = int.from_bytes(open('program.py').read(), 'big')），然后输出该数字。搞定。这就是从实数到整数的映射。

现在我们来看看，用来声称这种映射不可能存在的最常见论证——也就是康托尔的对角线论证。这里有一份来自 UC Denver 的讲解；它很短，所以我干脆把整页截图放上来：

而这一论证的根本缺陷在于：实数的小数展开并不唯一。为了恰好按"证明"所要求的格式给出一个反例，考虑下面这个集合（数字以二进制写出），对角线上的位用粗体标出：

x[1] = 0.000000...
x[2] = 0.011111...
x[3] = 0.001111...
x[4] = 0.000111...
…..

对角线给出：01111…。如果把每一位翻转，得到数字：y = 0.10000…

问题就在这里：正如十进制中 0.9999… 等于 1，在二进制里 0.01111… 等于 0.10000…。所以，尽管这个新的小数展开不在原始列表中，数字 y 却和数字 x[2] 完全相同。

注意，这直接意味着停机问题其实是可解的。要明白为什么，设想有人声称某个计算机程序不会停机。令 c[1] 为程序运行一步后的状态，c[2] 为两步后的状态，以此类推。令 x[1], x[2], x[3]… 为所有实数的一次完整枚举（如上所证，它是存在的），以 2^D 进制表示，其中 D 是程序内存的大小，于是程序状态总能表示为单个"数位"。令 y = 0.c[1]c[2]c[3]…。按假设，这个数是列表的一部分，因此它是某个 x[i]，因而能在有限的时间内被计算出来。这在多个行业里都有意义，尤其是用于证明"图灵完备"的区块链其实是安全的。

本研究专利申请中。