康托尔对角线论证

康托尔对角线论证是一种数学证明方法，通过构造一个与给定枚举中的每个对象都不同的对象来完成证明。其关键步骤是改变第 $n$ 个对象的第 $n$ 个位置上的值，从而确保构造出的对象不等于列表中的任何对象。这一方法由格奥尔格·康托尔提出，确立了不可数集的存在；其一般形式则证明，每个集合的基数都严格小于其幂集的基数。(onepagepapers.com)

历史起源

康托尔首次证明实数无法被枚举是在 1874 年，当时采用的是另一种构造方法。他的对角线方法出自论文《论集合论中的一个初等问题》（Über eine elementare Frage der Mannigfaltigkeitslehre），该论文与德国数学会于 1891 年 9 月在哈雷举行的会议有关。它通常被引为 1891 年的论文，但实际刊载于该学会在 1892 年印行的报告中。(plato.stanford.edu)

最初的论证针对的是由两个不同符号组成的无限序列，而非十进制展开。随后，康托尔将这一推理推广到任意集合上的二值函数所构成的集合。这一推广得出了如今所称的康托尔定理。(onepagepapers.com)

可数性与枚举

可数集是有限集，或是能够与自然数建立一一对应的集合。对于无限集而言，可数性意味着其元素可以列为

x_1,x_2,x_3,\ldots

且每个元素都出现在某个有限的位置上。这样的列表是在数学上为每个索引指定一个对象，并不是一个必须在现实中完成的过程。枚举也可以允许重复，只要它包含所有元素。(builds.openlogicproject.org)

不可数集不存在这样的枚举。对角线论证通过考虑任意给定的列表，并找出它遗漏的对象来证明这一点。关键在于，该论证适用于所有可能的列表，而不仅仅是某一种特定的排列顺序。(builds.openlogicproject.org)

二进制序列的证明

设

B=\{0,1\}^{\mathbb N}

为所有无限二进制序列组成的集合。假设给定了一个由 $B$ 中元素组成的列表，以 $a_{ij}$ 表示序列 $s_i$ 的第 $j$ 项：

\begin{array}{c|ccccc} &1&2&3&4&\cdots\\ \hline s_1&a_{11}&a_{12}&a_{13}&a_{14}&\cdots\\ s_2&a_{21}&a_{22}&a_{23}&a_{24}&\cdots\\ s_3&a_{31}&a_{32}&a_{33}&a_{34}&\cdots\\ s_4&a_{41}&a_{42}&a_{43}&a_{44}&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots \end{array}

定义一个新序列 $d$ ，使得

d_n=1-a_{nn}.

也就是说， $d$ 将主对角线上的每个值取反。对于每个 $n$ ，它的第 $n$ 项都与 $s_n$ 的第 $n$ 项不同，因此 $d\ne s_n$ 。然而， $d$ 本身也是一个无限二进制序列。因此，给定的列表遗漏了 $B$ 中的一个元素，由此证明 $B$ 不可数。(onepagepapers.com)

这一构造可以表述为反证法：假设列表包含所有二进制序列，再构造出一个被遗漏的序列。等价地，它也直接表明，从 $\mathbb N$ 到 $B$ 的任何映射都不是满射函数。(openlogicproject.org)

对实数的应用

一种常见的论证版本假设，区间 $(0,1)$ 中的所有数都已按十进制形式列出：

x_n=0.a_{n1}a_{n2}a_{n3}\ldots.

定义

y=0.b_1b_2b_3\ldots, \qquad b_n= \begin{cases} 2,&a_{nn}=1,\\ 1,&a_{nn}\ne1. \end{cases}

于是 $y$ 位于 $(0,1)$ 中，并且对于每个 $n$ ，它都在第 $n$ 个小数位上与 $x_n$ 不同。因此，任何给定的枚举都无法包含该区间内的全部实数。(cs.stanford.edu)

处理十进制表示时必须谨慎，因为不同的数字串可能表示同一个数，例如 $0.5000\ldots=0.4999\ldots$ 。在构造的数中只使用数字 $1$ 和 $2$ ，就能避免这种歧义：其展开既不终止，也不会从某一位起全为 $9$ 。如果只是改变数字，却不处理同一数的不同表示，就会在证明中留下漏洞。(cs.stanford.edu)

二进制序列也可以通过以下映射嵌入实数：

(a_n)\longmapsto \sum_{n=1}^{\infty}\frac{2a_n}{3^n}.

如果两个序列首次在第 $k$ 项出现差异，该项造成的差值 $2/3^k$ 大于后续各项可能产生的最大反向抵消量 $1/3^k$ 。因此，它们的像不同。这给出了一个到康托尔集的单射函数，也提供了另一条由二进制序列集的不可数性推导实数集不可数性的途径。(builds.openlogicproject.org)

推广到幂集

对于任意集合 $A$ ，其幂集 $\mathcal P(A)$ 由它的所有子集组成。给定任意函数

f:A\longrightarrow\mathcal P(A),

定义对角子集

D=\{a\in A:a\notin f(a)\}.

对于每个 $a\in A$ ，都有

a\in D\quad\Longleftrightarrow\quad a\notin f(a).

因此 $D\ne f(a)$ ：这两个子集在是否包含 $a$ 这一点上不同。由于 $D\in\mathcal P(A)$ ，函数 $f$ 不是满射。于是， $A$ 与 $\mathcal P(A)$ 之间不可能存在双射函数。另一方面， $a\mapsto\{a\}$ 是从 $A$ 到 $\mathcal P(A)$ 的单射，因此

|A|<|\mathcal P(A)|.

这一证明适用于有限集、可数集和不可数集；它不需要实际画出表格，也不要求用自然数进行枚举。(builds.openlogicproject.org)

推论与相关方法

在集合论中，反复应用康托尔定理，可以得到基数依次增大的集合：

|A|<|\mathcal P(A)| <|\mathcal P(\mathcal P(A))|<\cdots.

因此，不存在最大的集合基数。这个结论可以在策梅洛—弗兰克尔集合论中证明，无须使用选择公理。(builds.openlogicproject.org)

在可计算性理论中，类似的对角线推理确立了停机问题的不可判定性。假设存在一种算法，能够正确判断任意程序在任意输入上是否停机。构造一个程序，使它在接收到程序描述 $p$ 作为输入时，若上述算法预测 $p$ 以自身为输入会停机，就进入无限循环；否则就停机。当这个新程序以自身的描述为输入时，无论算法给出哪种预测，都会产生矛盾。这里的对角线论证涉及自我应用和相反的行为，而不是无限数字串。(builds.openlogicproject.org)

适用范围与常见误解

补上遗漏的对象，并不能使列表完整。 对角线对象取决于给定的枚举。将它插入修订后的枚举后，同样的构造又会产生一个被新列表遗漏的对象。该定理并不是找出一个被所有可能的列表共同遗漏的对象。(onepagepapers.com)

这一构造未必是有效的计算过程。 根据相应的对角线项来定义一个值，并不保证存在能够获取这些项的算法。数学意义上的枚举与可计算枚举是不同的概念。(builds.openlogicproject.org)

两种对角线技巧的用途不同。 沿着网格中一条接一条的有限对角线遍历，可以枚举自然数对，并帮助证明有理数集的可数性。相比之下，康托尔的反对角线构造通过改变各项的值，得到枚举之外的对象。(builds.openlogicproject.org)

不可数性并不能解决连续统假设。 对角线论证证明了实数比自然数更多，却不能判定两者的基数之间是否存在严格介于其间的基数。连续统假设断言不存在这样的中间基数；在通常的带选择公理的策梅洛—弗兰克尔公理体系一致的前提下，它独立于该公理体系。(plato.stanford.edu)

参考来源

Ueber eine elementare Frage der Mannigfaltigkeitslehre, the textonepagepapers.com
The Early Development of Set Theoryplato.stanford.edu
The Size of Setsbuilds.openlogicproject.org
Set Theory. An Open Introductionbuilds.openlogicproject.org
CS103 Course Textcs.stanford.edu
Revisions to enumerability and size of sets sectionsopenlogicproject.org
The Open Logic Textbuilds.openlogicproject.org
The Continuum Hypothesisplato.stanford.edu