康托错了：揭穿无限集合层次

一条常见的数学线索认为，不是一种单一的无穷大，实际上存在不同级别的无穷大的无限层次。而整数集的大小是纯无限的，而有理数集和整数一样大(因为你可以通过交错分子和分母的数字将每个有理数映射成一个整数，例如。\(0.456456456..)。=\frac{456}{999}=\frac{152}{333}\right tarrow 135323\))，实数集的大小是某种更大的无穷大，因为没有办法从实数到整数进行类似的映射。

首先，我应该指出，没有映射的说法是错误的，这是相对容易看出的。这里有一张简单的地图。对于一个给定的实数，给我一个(确定性的)python程序，它将打印出它的数字(例如。对于π，这可能是一个使用无穷级数\(\pi=4-\FRAC{4}{3}+\FRAC{4}{5}-\FRAC{4}{7}+...\)计算出越来越好的近似值的程序。我可以将程序转换为数字(使用n=int.from_bytes(open('；program.py'；).read()，；BIG)，然后输出该数字。好了。这就是从实数到整数的映射。

现在，让我们来看看最常见的声称不存在这样的映射的论点，即康托的对角线论点。以下是加州大学丹佛分校的一篇讲解，它很简短，所以我只会截图看整件事的来龙去脉：。

现在，这一论点的根本缺陷在于：实数的小数展开并不是唯一的。要提供精确格式的反例，请考虑用对角线数字加粗的集合(用二进制写成的数字)：

对角线给出：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]值之一，因此可以在有限的时间内计算它。这对许多行业都有影响，尤其是在证明图灵完成区块链实际上是安全的方面。