对角线论证:改变数学与计算机的证明方法
<blockquote>RSS readers may not support rendering advanced formatting like math formulas.
Click to view the original page: <a href="https://dreams.plus/blog/2026/2026-07-31-the-diagonal-argument-en" target="_blank">https://dreams.plus/blog/2026/2026-07-31-the-diagonal-argument-en</a></blockquote><p>1891 年,德国数学家格奥尔格·康托尔发表了一篇仅几页的论文,证明了一个在当时看来有悖直觉的结论:存在不同「大小」的无穷。他所采用的证明技巧——对角线论证——不仅解决了手头的问题,更在此后一个多世纪里,成为数理逻辑、可计算性理论乃至哲学武器库中最强大的武器之一。<p>从「实数比自然数多」,到图灵证明「停机问题不可判定」,再到哥德尔证明「任何足够强的形式系统都包含不可判定命题」——这些看似主题各异的结论,本质上都是同一个想法的变体。本文将带领读者从集合论最基础的出发点开始,一步步推导对角线论证的完整过程,阐明它为何拥有如此强大的力量,并把抽象的证明转化为可以通过代码执行、观察的具体过程。<h2 id=等势>等势</h2><p>在讨论无穷集之前,必须先澄清一个预备问题:如何比较两个集合的大小?<p>对于有限集,答案很简单:数元素个数即可。但自然数集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=double-struck>N</mi><mo>=</mo><mo stretchy=false>{</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo separator=true>,</mo><mn>2</mn><mo separator=true>,</mo><mn>3</mn><mo separator=true>,</mo><mo>…</mo><mtext></mtext><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>\mathbb{N} = \{0, 1, 2, 3, \dots\}</annotation></semantics></math></span> 是无穷的,无法「数到底」;因此我们需要一种新的工具。<p>定义(双射)。给定两个集合 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 与 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>B</mi></mrow><annotation encoding=application/x-tex>B</annotation></semantics></math></span>,若存在函数 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi>A</mi><mo>→</mo><mi>B</mi></mrow><annotation encoding=application/x-tex>f: A \to B</annotation></semantics></math></span> 满足:<ul><li>单射:<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>a</mi><mn>1</mn></msub><mo mathvariant=normal>≠</mo><msub><mi>a</mi><mn>2</mn></msub><mo>⇒</mo><mi>f</mi><mo stretchy=false>(</mo><msub><mi>a</mi><mn>1</mn></msub><mo stretchy=false>)</mo><mo mathvariant=normal>≠</mo><mi>f</mi><mo stretchy=false>(</mo><msub><mi>a</mi><mn>2</mn></msub><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)</annotation></semantics></math></span>(不同的输入产生不同的输出)<li>满射:对每个 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>b</mi><mo>∈</mo><mi>B</mi></mrow><annotation encoding=application/x-tex>b \in B</annotation></semantics></math></span>,都存在 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>a</mi><mo>∈</mo><mi>A</mi></mrow><annotation encoding=application/x-tex>a \in A</annotation></semantics></math></span> 使得 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo stretchy=false>(</mo><mi>a</mi><mo stretchy=false>)</mo><mo>=</mo><mi>b</mi></mrow><annotation encoding=application/x-tex>f(a) = b</annotation></semantics></math></span>(每个输出都被覆盖)</ul><p>则称 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi></mrow><annotation encoding=application/x-tex>f</annotation></semantics></math></span> 为双射,并称 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 与 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>B</mi></mrow><annotation encoding=application/x-tex>B</annotation></semantics></math></span> 等势(记为 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=normal>∣</mi><mi>A</mi><mi mathvariant=normal>∣</mi><mo>=</mo><mi mathvariant=normal>∣</mi><mi>B</mi><mi mathvariant=normal>∣</mi></mrow><annotation encoding=application/x-tex>|A| = |B|</annotation></semantics></math></span>)——即两者「大小相等」。<p>定义(可数集)。若集合 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 能与自然数集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=double-struck>N</mi></mrow><annotation encoding=application/x-tex>\mathbb{N}</annotation></semantics></math></span> 建立双射(或 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 为有限集),则称 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 为可数集。<p>下面几个例子会揭示,「可数」这个概念远比直觉所认为的更加宽松:<ul><li>偶数集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>{</mo><mn>0</mn><mo separator=true>,</mo><mn>2</mn><mo separator=true>,</mo><mn>4</mn><mo separator=true>,</mo><mn>6</mn><mo separator=true>,</mo><mo>…</mo><mtext></mtext><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>\{0, 2, 4, 6, \dots\}</annotation></semantics></math></span> 可数:双射为 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo stretchy=false>(</mo><mi>n</mi><mo stretchy=false>)</mo><mo>=</mo><mn>2</mn><mi>n</mi></mrow><annotation encoding=application/x-tex>f(n) = 2n</annotation></semantics></math></span>。<li>整数集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=double-struck>Z</mi><mo>=</mo><mo stretchy=false>{</mo><mo>…</mo><mo separator=true>,</mo><mo>−</mo><mn>2</mn><mo separator=true>,</mo><mo>−</mo><mn>1</mn><mo separator=true>,</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo separator=true>,</mo><mn>2</mn><mo separator=true>,</mo><mo>…</mo><mtext></mtext><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}</annotation></semantics></math></span> 可数:可以用 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo stretchy=false>(</mo><mi>n</mi><mo stretchy=false>)</mo><mo>=</mo><mrow><mo fence=true>{</mo><mtable columnalign="left left" columnspacing=1em rowspacing=0.36em><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi>n</mi><mi mathvariant=normal>/</mi><mn>2</mn></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi>n</mi><mtext> 为偶数</mtext></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mo>−</mo><mo stretchy=false>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy=false>)</mo><mi mathvariant=normal>/</mi><mn>2</mn></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi>n</mi><mtext> 为奇数</mtext></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding=application/x-tex>f(n) = \begin{cases} n/2 & n \text{ 为偶数} \\ -(n+1)/2 & n \text{ 为奇数} \end{cases}</annotation></semantics></math></span> 把 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo separator=true>,</mo><mn>2</mn><mo separator=true>,</mo><mn>3</mn><mo separator=true>,</mo><mn>4</mn><mo separator=true>,</mo><mo>…</mo></mrow><annotation encoding=application/x-tex>0,1,2,3,4,\dots</annotation></semantics></math></span> 映射到 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mn>0</mn><mo separator=true>,</mo><mo>−</mo><mn>1</mn><mo separator=true>,</mo><mn>1</mn><mo separator=true>,</mo><mo>−</mo><mn>2</mn><mo separator=true>,</mo><mn>2</mn><mo separator=true>,</mo><mo>…</mo></mrow><annotation encoding=application/x-tex>0,-1,1,-2,2,\dots</annotation></semantics></math></span>。<li>有理数集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=double-struck>Q</mi></mrow><annotation encoding=application/x-tex>\mathbb{Q}</annotation></semantics></math></span> 同样可数(可以用「对角线枚举法」把所有分数 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>p</mi><mi mathvariant=normal>/</mi><mi>q</mi></mrow><annotation encoding=application/x-tex>p/q</annotation></semantics></math></span> 排成一个序列——这是康托尔的另一个经典成果,与本文讨论的论证共享「对角线」之名,但用法不同;请读者注意不要把两者混淆)。</ul><p>看上去,似乎所有无穷集都能被装进自然数的框架之内——直到我们遇到实数。<h2 id=实数的不可数>实数的不可数</h2><blockquote><p>定理(康托尔,1891)。区间 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>(0,1)</annotation></semantics></math></span> 中的实数是不可数的。</blockquote><p>这意味着:不存在任何方法能把 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>(0,1)</annotation></semantics></math></span> 中的实数与自然数一一对应。换言之,实数的无穷「大于」自然数的无穷。<p>我们采用反证法。<p>假设:<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>(0,1)</annotation></semantics></math></span> 中的实数可数。即存在双射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi mathvariant=double-struck>N</mi><mo>→</mo><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f: \mathbb{N} \to (0,1)</annotation></semantics></math></span>,使得我们可以把这些实数全部排成一个无穷列表:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mtable columnalign="right left" columnspacing=0em rowspacing=0.25em><mtr><mtd><mstyle displaystyle=true scriptlevel=0><msub><mi>x</mi><mn>1</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=true scriptlevel=0><mrow><mrow></mrow><mo>=</mo><mn>0.</mn><msub><mi>d</mi><mn>11</mn></msub><mtext></mtext><msub><mi>d</mi><mn>12</mn></msub><mtext></mtext><msub><mi>d</mi><mn>13</mn></msub><mtext></mtext><msub><mi>d</mi><mn>14</mn></msub><mo>…</mo></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=true scriptlevel=0><msub><mi>x</mi><mn>2</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=true scriptlevel=0><mrow><mrow></mrow><mo>=</mo><mn>0.</mn><msub><mi>d</mi><mn>21</mn></msub><mtext></mtext><msub><mi>d</mi><mn>22</mn></msub><mtext></mtext><msub><mi>d</mi><mn>23</mn></msub><mtext></mtext><msub><mi>d</mi><mn>24</mn></msub><mo>…</mo></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=true scriptlevel=0><msub><mi>x</mi><mn>3</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=true scriptlevel=0><mrow><mrow></mrow><mo>=</mo><mn>0.</mn><msub><mi>d</mi><mn>31</mn></msub><mtext></mtext><msub><mi>d</mi><mn>32</mn></msub><mtext></mtext><msub><mi>d</mi><mn>33</mn></msub><mtext></mtext><msub><mi>d</mi><mn>34</mn></msub><mo>…</mo></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=true scriptlevel=0><msub><mi>x</mi><mn>4</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=true scriptlevel=0><mrow><mrow></mrow><mo>=</mo><mn>0.</mn><msub><mi>d</mi><mn>41</mn></msub><mtext></mtext><msub><mi>d</mi><mn>42</mn></msub><mtext></mtext><msub><mi>d</mi><mn>43</mn></msub><mtext></mtext><msub><mi>d</mi><mn>44</mn></msub><mo>…</mo></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=true scriptlevel=0><mrow></mrow></mstyle></mtd><mtd><mstyle displaystyle=true scriptlevel=0><mrow><mrow></mrow><mtext></mtext><mrow><mi mathvariant=normal>⋮</mi><mpadded height=0em voffset=0em><mspace height=1.5em mathbackground=black width=0em></mspace></mpadded></mrow></mrow></mstyle></mtd></mtr></mtable><annotation encoding=application/x-tex>\begin{aligned} x_1 &= 0.d_{11}\, d_{12}\, d_{13}\, d_{14} \dots \\ x_2 &= 0.d_{21}\, d_{22}\, d_{23}\, d_{24} \dots \\ x_3 &= 0.d_{31}\, d_{32}\, d_{33}\, d_{34} \dots \\ x_4 &= 0.d_{41}\, d_{42}\, d_{43}\, d_{44} \dots \\ &\ \ \vdots \end{aligned}</annotation></semantics></math></span><p>其中 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>d</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow><annotation encoding=application/x-tex>d_{ij}</annotation></semantics></math></span> 表示第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>i</mi></mrow><annotation encoding=application/x-tex>i</annotation></semantics></math></span> 个数的第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>j</mi></mrow><annotation encoding=application/x-tex>j</annotation></semantics></math></span> 位小数(取值 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mn>0</mn></mrow><annotation encoding=application/x-tex>0</annotation></semantics></math></span> 到 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mn>9</mn></mrow><annotation encoding=application/x-tex>9</annotation></semantics></math></span>)。<p>构造对角数。现在我们沿着「对角线」走——即取出第 1 个数的第 1 位、第 2 个数的第 2 位、第 3 个数的第 3 位,依此类推——并根据以下规则,用这些数字构造一个新数 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi><mo>=</mo><mn>0.</mn><msub><mi>e</mi><mn>1</mn></msub><msub><mi>e</mi><mn>2</mn></msub><msub><mi>e</mi><mn>3</mn></msub><msub><mi>e</mi><mn>4</mn></msub><mo>…</mo></mrow><annotation encoding=application/x-tex>y = 0.e_1 e_2 e_3 e_4 \dots</annotation></semantics></math></span>:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>e</mi><mi>n</mi></msub><mo>=</mo><mrow><mo fence=true>{</mo><mtable columnalign="left left" columnspacing=1em rowspacing=0.36em><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mn>5</mn></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>若 </mtext><msub><mi>d</mi><mrow><mi>n</mi><mi>n</mi></mrow></msub><mo mathvariant=normal>≠</mo><mn>5</mn></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mn>6</mn></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>若 </mtext><msub><mi>d</mi><mrow><mi>n</mi><mi>n</mi></mrow></msub><mo>=</mo><mn>5</mn></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding=application/x-tex>e_n = \begin{cases} 5 & \text{若 } d_{nn} \neq 5 \\ 6 & \text{若 } d_{nn} = 5 \end{cases}</annotation></semantics></math></span><p>(这条规则的唯一目的是保证 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>e</mi><mi>n</mi></msub><mo mathvariant=normal>≠</mo><msub><mi>d</mi><mrow><mi>n</mi><mi>n</mi></mrow></msub></mrow><annotation encoding=application/x-tex>e_n \neq d_{nn}</annotation></semantics></math></span>;具体选哪两个数字无关紧要,只要每位数字刻意「避开」相应的对角线数字,同时避免出现全 0 或全 9 的小数表示——那会在十进制记法中引入歧义。)<p>现在关键问题出现了:<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 会出现在原来的列表里吗?<p>假设 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 出现在列表中,那么 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 必定等于被枚举的某个数,不妨设 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi><mo>=</mo><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>y = x_k</annotation></semantics></math></span>(对某个确定的指标 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>k</mi></mrow><annotation encoding=application/x-tex>k</annotation></semantics></math></span>)。<p>但根据我们的构造规则,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 的第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>k</mi></mrow><annotation encoding=application/x-tex>k</annotation></semantics></math></span> 位小数是 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>e</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>e_k</annotation></semantics></math></span>,而 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>e</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>e_k</annotation></semantics></math></span> 被刻意构造得与 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>d</mi><mrow><mi>k</mi><mi>k</mi></mrow></msub></mrow><annotation encoding=application/x-tex>d_{kk}</annotation></semantics></math></span>(即 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>x_k</annotation></semantics></math></span> 的第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>k</mi></mrow><annotation encoding=application/x-tex>k</annotation></semantics></math></span> 位小数)不同:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>e</mi><mi>k</mi></msub><mo mathvariant=normal>≠</mo><msub><mi>d</mi><mrow><mi>k</mi><mi>k</mi></mrow></msub><mtext></mtext><mo>⟹</mo><mtext></mtext><mi>y</mi><mo mathvariant=normal>≠</mo><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>e_k \neq d_{kk} \implies y \neq x_k</annotation></semantics></math></span><p>这与 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi><mo>=</mo><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>y = x_k</annotation></semantics></math></span> 的假设矛盾!<p>而且,这一矛盾对每一个 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>k</mi></mrow><annotation encoding=application/x-tex>k</annotation></semantics></math></span> 都成立——<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 在第 1 位与第 1 个数不同,在第 2 位与第 2 个数不同,在第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 位与第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 个数不同……因此 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 与列表中的每一个数都不同。<p>然而 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 无疑是 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>(0,1)</annotation></semantics></math></span> 中的实数(它的每一位都是合法的十进制数字)。<p>结论:无论你如何构造这份「实数大全列表」,总能构造出一个逃脱列表的实数 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span>。这就说明最初的假设——存在双射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi mathvariant=double-struck>N</mi><mo>→</mo><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f: \mathbb{N} \to (0,1)</annotation></semantics></math></span>——是假的。<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>(0,1)</annotation></semantics></math></span> 中的实数不可数。<p>为什么叫「对角线」?这个名称源于证明中选取数字 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>d</mi><mn>11</mn></msub><mo separator=true>,</mo><msub><mi>d</mi><mn>22</mn></msub><mo separator=true>,</mo><msub><mi>d</mi><mn>33</mn></msub><mo separator=true>,</mo><mo>…</mo></mrow><annotation encoding=application/x-tex>d_{11}, d_{22}, d_{33}, \dots</annotation></semantics></math></span> 的方式——若把所有 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>x</mi><mi>i</mi></msub></mrow><annotation encoding=application/x-tex>x_i</annotation></semantics></math></span> 纵向排成无穷矩阵,这些位置恰好构成矩阵的主对角线:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo fence=true>(</mo><mtable columnalign="center center center center" columnspacing=1em rowspacing=0.16em><mtr><mtd><mstyle displaystyle=false scriptlevel=0><menclose notation=box><mstyle displaystyle=false scriptlevel=0><mstyle displaystyle=false scriptlevel=0><mstyle displaystyle=true scriptlevel=0><msub><mi>d</mi><mn>11</mn></msub></mstyle></mstyle></mstyle></menclose></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><msub><mi>d</mi><mn>12</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><msub><mi>d</mi><mn>13</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋯</mo></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><msub><mi>d</mi><mn>21</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><menclose notation=box><mstyle displaystyle=false scriptlevel=0><mstyle displaystyle=false scriptlevel=0><mstyle displaystyle=true scriptlevel=0><msub><mi>d</mi><mn>22</mn></msub></mstyle></mstyle></mstyle></menclose></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><msub><mi>d</mi><mn>23</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋯</mo></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><msub><mi>d</mi><mn>31</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><msub><mi>d</mi><mn>32</mn></msub></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><menclose notation=box><mstyle displaystyle=false scriptlevel=0><mstyle displaystyle=false scriptlevel=0><mstyle displaystyle=true scriptlevel=0><msub><mi>d</mi><mn>33</mn></msub></mstyle></mstyle></mstyle></menclose></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋯</mo></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi mathvariant=normal>⋮</mi><mpadded height=0em voffset=0em><mspace height=1.5em mathbackground=black width=0em></mspace></mpadded></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi mathvariant=normal>⋮</mi><mpadded height=0em voffset=0em><mspace height=1.5em mathbackground=black width=0em></mspace></mpadded></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi mathvariant=normal>⋮</mi><mpadded height=0em voffset=0em><mspace height=1.5em mathbackground=black width=0em></mspace></mpadded></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋱</mo></mstyle></mtd></mtr></mtable><mo fence=true>)</mo></mrow><annotation encoding=application/x-tex>\begin{pmatrix} \boxed{d_{11}} & d_{12} & d_{13} & \cdots \\ d_{21} & \boxed{d_{22}} & d_{23} & \cdots \\ d_{31} & d_{32} & \boxed{d_{33}} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}</annotation></semantics></math></span><p>我们「翻转」对角线上的每一位数字,构造出一个必然逃脱整个列表的新元素。<h2 id=构造逃逸者>构造逃逸者</h2><p>仅凭公式可能仍有几分抽象;让我们通过代码把这一过程具体化。下面的程序取十个「实数」作为示例列表,真正执行一次对角线构造,让读者清楚地看到新数如何「避开」原来的每一个数。<pre><code class="hljs language-python"><span class=hljs-keyword>def</span><span class="hljs-title function_">diagonal_construct</span>(<span class=hljs-params>number_list, digits=<span class=hljs-number>10</span></span>):
<span class=hljs-string>"""
number_list:字符串列表,每个形如 "0.d1d2d3..."
返回:通过对角线方法构造出的新数字字符串
"""</span>
new_digits = []
<span class=hljs-keyword>for</span> i, num_str <span class=hljs-keyword>in</span><span class=hljs-built_in>enumerate</span>(number_list):
decimal_part = num_str.split(<span class=hljs-string>'.'</span>)[<span class=hljs-number>1</span>].ljust(digits, <span class=hljs-string>'0'</span>)
d = <span class=hljs-built_in>int</span>(decimal_part[i]) <span class=hljs-comment># 第 i 个数的第 i 位(对角线数字)</span>
new_d = (d + <span class=hljs-number>5</span>) % <span class=hljs-number>10</span><span class=hljs-comment># 规则:使新数字与原数字不同</span>
new_digits.append(<span class=hljs-built_in>str</span>(new_d))
<span class=hljs-keyword>return</span><span class=hljs-string>"0."</span> + <span class=hljs-string>""</span>.join(new_digits)
sample_list = [
<span class=hljs-string>"0.1234567890"</span>, <span class=hljs-string>"0.9876543210"</span>, <span class=hljs-string>"0.5555555555"</span>, <span class=hljs-string>"0.1111111111"</span>,
<span class=hljs-string>"0.3141592653"</span>, <span class=hljs-string>"0.2718281828"</span>, <span class=hljs-string>"0.0000000001"</span>, <span class=hljs-string>"0.9999999998"</span>,
<span class=hljs-string>"0.4242424242"</span>, <span class=hljs-string>"0.6180339887"</span>,
]
new_number = diagonal_construct(sample_list)
<span class=hljs-built_in>print</span>(<span class=hljs-string>"对角线构造出的新数:"</span>, new_number)
</code></pre><p>输出:<pre><code class="hljs language-graphql">原始列表:
第 <span class=hljs-number>1</span> 个:<span class=hljs-number>0.1234567890</span> (第 <span class=hljs-number>1</span> 位对角线数字:<span class=hljs-number>1</span>)
第 <span class=hljs-number>2</span> 个:<span class=hljs-number>0.9876543210</span> (第 <span class=hljs-number>2</span> 位对角线数字:<span class=hljs-number>8</span>)
第 <span class=hljs-number>3</span> 个:<span class=hljs-number>0.5555555555</span> (第 <span class=hljs-number>3</span> 位对角线数字:<span class=hljs-number>5</span>)
第 <span class=hljs-number>4</span> 个:<span class=hljs-number>0.1111111111</span> (第 <span class=hljs-number>4</span> 位对角线数字:<span class=hljs-number>1</span>)
第 <span class=hljs-number>5</span> 个:<span class=hljs-number>0.3141592653</span> (第 <span class=hljs-number>5</span> 位对角线数字:<span class=hljs-number>5</span>)
第 <span class=hljs-number>6</span> 个:<span class=hljs-number>0.2718281828</span> (第 <span class=hljs-number>6</span> 位对角线数字:<span class=hljs-number>8</span>)
第 <span class=hljs-number>7</span> 个:<span class=hljs-number>0.0000000001</span> (第 <span class=hljs-number>7</span> 位对角线数字:<span class=hljs-number>0</span>)
第 <span class=hljs-number>8</span> 个:<span class=hljs-number>0.9999999998</span> (第 <span class=hljs-number>8</span> 位对角线数字:<span class=hljs-number>9</span>)
第 <span class=hljs-number>9</span> 个:<span class=hljs-number>0.4242424242</span> (第 <span class=hljs-number>9</span> 位对角线数字:<span class=hljs-number>4</span>)
第 <span class=hljs-number>10</span> 个:<span class=hljs-number>0.6180339887</span> (第 <span class=hljs-number>10</span> 位对角线数字:<span class=hljs-number>7</span>)
对角线构造出的新数:<span class=hljs-number>0.6306035492</span>
验证新数与列表中每个数都不同:
与第 <span class=hljs-number>1</span> 个在第 <span class=hljs-number>1</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>1</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>6</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>2</span> 个在第 <span class=hljs-number>2</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>8</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>3</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>3</span> 个在第 <span class=hljs-number>3</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>5</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>0</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>4</span> 个在第 <span class=hljs-number>4</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>1</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>6</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>5</span> 个在第 <span class=hljs-number>5</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>5</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>0</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>6</span> 个在第 <span class=hljs-number>6</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>8</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>3</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>7</span> 个在第 <span class=hljs-number>7</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>0</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>5</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>8</span> 个在第 <span class=hljs-number>8</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>9</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>4</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>9</span> 个在第 <span class=hljs-number>9</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>4</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>9</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span>
与第 <span class=hljs-number>10</span> 个在第 <span class=hljs-number>10</span> 位不同:原数<span class=hljs-punctuation>=</span><span class=hljs-number>7</span>,新数<span class=hljs-punctuation>=</span><span class=hljs-number>2</span>,不同<span class=hljs-punctuation>=</span><span class=hljs-literal>True</span></code></pre><p>可以清楚地看到,新构造的数 <code>0.6306035492</code> 恰好在相应的位置上与列表中的每一个数都不同。当然,这里演示的只是十个数的有限情形(真正的无穷列表毕竟无法存入计算机),但这恰恰是证明核心逻辑步骤——对任意 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>k</mi></mrow><annotation encoding=application/x-tex>k</annotation></semantics></math></span>,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi><mo mathvariant=normal>≠</mo><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding=application/x-tex>y \neq x_k</annotation></semantics></math></span>——的直观实例化。无论列表多长,这条构造规则都能保证新数逃脱每一个条目。<h2 id=康托尔定理>康托尔定理</h2><p>对角线论证不仅能证明实数不可数;它还有一个更一般、更强大的表述:康托尔定理。<blockquote><p>康托尔定理。对任意集合 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span>,其幂集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\mathcal{P}(A)</annotation></semantics></math></span>(即 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 的所有子集构成的集合)的势严格大于 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 本身,即 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=normal>∣</mi><mi>A</mi><mi mathvariant=normal>∣</mi><mo><</mo><mi mathvariant=normal>∣</mi><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo><mi mathvariant=normal>∣</mi></mrow><annotation encoding=application/x-tex>|A| < |\mathcal{P}(A)|</annotation></semantics></math></span>。</blockquote><p>需要指出,该定理对有限集和无穷集都成立,而对无穷集尤其揭示出一个惊人的事实:不存在「最大的无穷」。无论 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 多大,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\mathcal{P}(A)</annotation></semantics></math></span> 总更大;你可以无限地迭代幂集运算,得到一级级不断攀升的无穷层级。<h3 id=证明>证明</h3><p>假设存在一个满射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi>A</mi><mo>→</mo><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f: A \to \mathcal{P}(A)</annotation></semantics></math></span>(我们将证明这样的满射不存在,由此得到 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=normal>∣</mi><mi>A</mi><mi mathvariant=normal>∣</mi><mo><</mo><mi mathvariant=normal>∣</mi><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo><mi mathvariant=normal>∣</mi></mrow><annotation encoding=application/x-tex>|A| < |\mathcal{P}(A)|</annotation></semantics></math></span>)。<p>对每个元素 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>a</mi><mo>∈</mo><mi>A</mi></mrow><annotation encoding=application/x-tex>a \in A</annotation></semantics></math></span>,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo stretchy=false>(</mo><mi>a</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f(a)</annotation></semantics></math></span> 都是 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 的一个子集。现在构造一个特殊的子集:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo>=</mo><mo stretchy=false>{</mo><mtext></mtext><mi>a</mi><mo>∈</mo><mi>A</mi><mo>:</mo><mi>a</mi><mo mathvariant=normal>∉</mo><mi>f</mi><mo stretchy=false>(</mo><mi>a</mi><mo stretchy=false>)</mo><mtext></mtext><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>D = \{\, a \in A : a \notin f(a) \,\}</annotation></semantics></math></span><p>这就是「对角集」——它收集所有「不属于自己被映射到的那个子集」的元素。<p>由于 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi></mrow><annotation encoding=application/x-tex>f</annotation></semantics></math></span> 是满射,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span>(作为 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi></mrow><annotation encoding=application/x-tex>A</annotation></semantics></math></span> 的子集,因而是 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\mathcal{P}(A)</annotation></semantics></math></span> 的元素)必有原像;即存在某个 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>A</mi></mrow><annotation encoding=application/x-tex>d \in A</annotation></semantics></math></span> 使得 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo stretchy=false>(</mo><mi>d</mi><mo stretchy=false>)</mo><mo>=</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>f(d) = D</annotation></semantics></math></span>。<p>现在问:<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>d \in D</annotation></semantics></math></span> 吗?<ul><li>若 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>d \in D</annotation></semantics></math></span>:根据 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span> 的定义,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>D</mi><mtext></mtext><mo>⟺</mo><mtext></mtext><mi>d</mi><mo mathvariant=normal>∉</mo><mi>f</mi><mo stretchy=false>(</mo><mi>d</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>d \in D \iff d \notin f(d)</annotation></semantics></math></span>。由于 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo stretchy=false>(</mo><mi>d</mi><mo stretchy=false>)</mo><mo>=</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>f(d) = D</annotation></semantics></math></span>,就有 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>D</mi><mtext></mtext><mo>⟺</mo><mtext></mtext><mi>d</mi><mo mathvariant=normal>∉</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>d \in D \iff d \notin D</annotation></semantics></math></span>。矛盾!<li>若 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo mathvariant=normal>∉</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>d \notin D</annotation></semantics></math></span>:同理,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo mathvariant=normal>∉</mo><mi>D</mi><mtext></mtext><mo>⟺</mo><mtext></mtext><mi mathvariant=normal>¬</mi><mo stretchy=false>(</mo><mi>d</mi><mo mathvariant=normal>∉</mo><mi>f</mi><mo stretchy=false>(</mo><mi>d</mi><mo stretchy=false>)</mo><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>d \notin D \iff \neg(d \notin f(d))</annotation></semantics></math></span>,即 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>f</mi><mo stretchy=false>(</mo><mi>d</mi><mo stretchy=false>)</mo><mo>=</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>d \in f(d) = D</annotation></semantics></math></span>,从而 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>d</mi><mo>∈</mo><mi>D</mi></mrow><annotation encoding=application/x-tex>d \in D</annotation></semantics></math></span>。矛盾!</ul><p>两种情况都导致自相矛盾,说明「存在满射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi>A</mi><mo>→</mo><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f: A \to \mathcal{P}(A)</annotation></semantics></math></span>」这一假设站不住脚。因此 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=normal>∣</mi><mi>A</mi><mi mathvariant=normal>∣</mi><mo><</mo><mi mathvariant=normal>∣</mi><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo><mi mathvariant=normal>∣</mi></mrow><annotation encoding=application/x-tex>|A| < |\mathcal{P}(A)|</annotation></semantics></math></span>。<p>细心的读者可能已经发现,这个证明的结构与上面的不可数证明完全相同:<table><thead><tr><th>实数的不可数性<th>康托尔定理<tbody><tr><td>假设双射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi mathvariant=double-struck>N</mi><mo>→</mo><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f: \mathbb{N} \to (0,1)</annotation></semantics></math></span><td>假设满射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi><mo>:</mo><mi>A</mi><mo>→</mo><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi>A</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>f: A \to \mathcal{P}(A)</annotation></semantics></math></span><tr><td>构造对角数 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span>,每一位都与 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>x</mi><mi>n</mi></msub></mrow><annotation encoding=application/x-tex>x_n</annotation></semantics></math></span> 的第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 位不同<td>构造对角集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo>=</mo><mo stretchy=false>{</mo><mi>a</mi><mo>:</mo><mi>a</mi><mo mathvariant=normal>∉</mo><mi>f</mi><mo stretchy=false>(</mo><mi>a</mi><mo stretchy=false>)</mo><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>D = \{a : a \notin f(a)\}</annotation></semantics></math></span><tr><td>对所有 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 有 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi><mo mathvariant=normal>≠</mo><msub><mi>x</mi><mi>n</mi></msub></mrow><annotation encoding=application/x-tex>y \neq x_n</annotation></semantics></math></span><td>对所有 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>a</mi></mrow><annotation encoding=application/x-tex>a</annotation></semantics></math></span> 有 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo mathvariant=normal>≠</mo><mi>f</mi><mo stretchy=false>(</mo><mi>a</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>D \neq f(a)</annotation></semantics></math></span><tr><td><span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span> 无法被列表覆盖;矛盾<td><span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span> 无法被映射覆盖;矛盾</table><p>事实上,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>(</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>(0,1)</annotation></semantics></math></span> 中的实数可以与 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>{</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><msup><mo stretchy=false>}</mo><mi mathvariant=double-struck>N</mi></msup></mrow><annotation encoding=application/x-tex>\{0,1\}^{\mathbb{N}}</annotation></semantics></math></span>(由 0 和 1 组成的无穷二进制序列集)近似对应,而 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo stretchy=false>{</mo><mn>0</mn><mo separator=true>,</mo><mn>1</mn><msup><mo stretchy=false>}</mo><mi mathvariant=double-struck>N</mi></msup></mrow><annotation encoding=application/x-tex>\{0,1\}^{\mathbb{N}}</annotation></semantics></math></span> 本质上就是 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=script>P</mi><mo stretchy=false>(</mo><mi mathvariant=double-struck>N</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\mathcal{P}(\mathbb{N})</annotation></semantics></math></span>(每个子集对应一个 0/1 序列,标明某个位置是否属于该子集)。因此,「实数不可数」实际上是康托尔定理在 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>A</mi><mo>=</mo><mi mathvariant=double-struck>N</mi></mrow><annotation encoding=application/x-tex>A = \mathbb{N}</annotation></semantics></math></span> 这一特例下的具体体现。<p>虽然我们无法在计算机中表示无穷集,但可以用有限集验证证明的逻辑骨架:<pre><code class="hljs language-python"><span class=hljs-keyword>def</span><span class="hljs-title function_">cantor_diagonal_demo</span>(<span class=hljs-params>A</span>):
<span class=hljs-comment># 构造一个「任意」的映射 f: A -> P(A) 用于演示</span>
f = {}
<span class=hljs-keyword>for</span> i <span class=hljs-keyword>in</span> A:
f[i] = <span class=hljs-built_in>frozenset</span>(j <span class=hljs-keyword>for</span> j <span class=hljs-keyword>in</span> A <span class=hljs-keyword>if</span> (i + j) % <span class=hljs-number>2</span> == <span class=hljs-number>0</span>)
<span class=hljs-built_in>print</span>(<span class=hljs-string>"集合 A ="</span>, <span class=hljs-built_in>set</span>(A))
<span class=hljs-keyword>for</span> i <span class=hljs-keyword>in</span> A:
<span class=hljs-built_in>print</span>(<span class=hljs-string>f" f(<span class=hljs-subst>{i}</span>) = <span class=hljs-subst>{<span class=hljs-built_in>set</span>(f[i])}</span>"</span>)
<span class=hljs-comment># 对角线构造:D = { i in A : i not in f(i) }</span>
D = <span class=hljs-built_in>frozenset</span>(i <span class=hljs-keyword>for</span> i <span class=hljs-keyword>in</span> A <span class=hljs-keyword>if</span> i <span class=hljs-keyword>not</span><span class=hljs-keyword>in</span> f[i])
<span class=hljs-built_in>print</span>(<span class=hljs-string>f"对角线构造出的集合 D = <span class=hljs-subst>{<span class=hljs-built_in>set</span>(D)}</span>"</span>)
matches = [i <span class=hljs-keyword>for</span> i <span class=hljs-keyword>in</span> A <span class=hljs-keyword>if</span> f[i] == D]
<span class=hljs-built_in>print</span>(<span class=hljs-string>f"是否存在 i 使得 f(i) = D? -> <span class=hljs-subst>{matches <span class=hljs-keyword>if</span> matches <span class=hljs-keyword>else</span><span class=hljs-string>'不存在(矛盾已建立)'</span>}</span>"</span>)
cantor_diagonal_demo([<span class=hljs-number>0</span>, <span class=hljs-number>1</span>, <span class=hljs-number>2</span>, <span class=hljs-number>3</span>])
</code></pre><p>输出:<pre><code class="hljs language-scss">集合 <span class=hljs-selector-tag>A</span> = {<span class=hljs-number>0</span>, <span class=hljs-number>1</span>, <span class=hljs-number>2</span>, <span class=hljs-number>3</span>}
假定的映射 f: A -> <span class=hljs-built_in>P</span>(A):
<span class=hljs-built_in>f</span>(<span class=hljs-number>0</span>) = {<span class=hljs-number>0</span>, <span class=hljs-number>2</span>}
<span class=hljs-built_in>f</span>(<span class=hljs-number>1</span>) = {<span class=hljs-number>1</span>, <span class=hljs-number>3</span>}
<span class=hljs-built_in>f</span>(<span class=hljs-number>2</span>) = {<span class=hljs-number>0</span>, <span class=hljs-number>2</span>}
<span class=hljs-built_in>f</span>(<span class=hljs-number>3</span>) = {<span class=hljs-number>1</span>, <span class=hljs-number>3</span>}
对角线构造出的集合 D = { <span class=hljs-selector-tag>i</span> : i ∉ <span class=hljs-built_in>f</span>(i) } = <span class=hljs-built_in>set</span>()
是否存在 <span class=hljs-selector-tag>i</span> 使得 <span class=hljs-built_in>f</span>(i) = D? -> 不存在(矛盾已建立)
逐一验证 <span class=hljs-built_in>f</span>(i) ≠ D:
<span class=hljs-selector-tag>i</span>=<span class=hljs-number>0</span>:<span class=hljs-selector-tag>i</span>∉D 但 <span class=hljs-selector-tag>i</span>∈<span class=hljs-built_in>f</span>(<span class=hljs-number>0</span>),故 D ≠ <span class=hljs-built_in>f</span>(<span class=hljs-number>0</span>)
<span class=hljs-selector-tag>i</span>=<span class=hljs-number>1</span>:<span class=hljs-selector-tag>i</span>∉D 但 <span class=hljs-selector-tag>i</span>∈<span class=hljs-built_in>f</span>(<span class=hljs-number>1</span>),故 D ≠ <span class=hljs-built_in>f</span>(<span class=hljs-number>1</span>)
<span class=hljs-selector-tag>i</span>=<span class=hljs-number>2</span>:<span class=hljs-selector-tag>i</span>∉D 但 <span class=hljs-selector-tag>i</span>∈<span class=hljs-built_in>f</span>(<span class=hljs-number>2</span>),故 D ≠ <span class=hljs-built_in>f</span>(<span class=hljs-number>2</span>)
<span class=hljs-selector-tag>i</span>=<span class=hljs-number>3</span>:<span class=hljs-selector-tag>i</span>∉D 但 <span class=hljs-selector-tag>i</span>∈<span class=hljs-built_in>f</span>(<span class=hljs-number>3</span>),故 D ≠ <span class=hljs-built_in>f</span>(<span class=hljs-number>3</span>)
</code></pre><p>这里构造出的 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span> 恰好是空集,而这个特定的映射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi></mrow><annotation encoding=application/x-tex>f</annotation></semantics></math></span> 恰好没有把任何元素映射到空集——这是对角线论证「刻意构造逃逸者」这一核心思想的直接体现。当然,这只是一个具体的映射示例;真正的证明是对每一种可能的映射 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>f</mi></mrow><annotation encoding=application/x-tex>f</annotation></semantics></math></span> 都成立的普适论证。<h2 id=停机问题>停机问题</h2><p>对角线论证最令人惊叹的应用之一,出现在阿兰·图灵 1936 年对停机问题不可判定性的证明中。这一结果直接奠定了整个可计算性理论领域的基础。<p>停机问题。给定一个程序 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>P</mi></mrow><annotation encoding=application/x-tex>P</annotation></semantics></math></span> 和一个输入 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>x</mi></mrow><annotation encoding=application/x-tex>x</annotation></semantics></math></span>,是否存在一个通用算法,能够判断 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>P</mi></mrow><annotation encoding=application/x-tex>P</annotation></semantics></math></span> 在输入 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>x</mi></mrow><annotation encoding=application/x-tex>x</annotation></semantics></math></span> 上运行时,究竟会停机(并返回结果)还是永不停机(陷入死循环)?<p>图灵证明:这样的通用算法不存在(这是对角线论证的一个变体)。<p>假设存在这样一个「通用停机判定器」,我们把它形式化为一个函数:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><mi>P</mi><mo separator=true>,</mo><mi>x</mi><mo stretchy=false>)</mo><mo>=</mo><mrow><mo fence=true>{</mo><mtable columnalign="left left" columnspacing=1em rowspacing=0.36em><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mtext>真</mtext></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>若 </mtext><mi>P</mi><mo stretchy=false>(</mo><mi>x</mi><mo stretchy=false>)</mo><mtext> 停机</mtext></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mtext>假</mtext></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>若 </mtext><mi>P</mi><mo stretchy=false>(</mo><mi>x</mi><mo stretchy=false>)</mo><mtext> 不停机</mtext></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding=application/x-tex>\text{halts}(P, x) = \begin{cases} \text{真} & \text{若 } P(x) \text{ 停机} \\ \text{假} & \text{若 } P(x) \text{ 不停机} \end{cases}</annotation></semantics></math></span><p>这个函数本身必须在有限时间内总是给出正确回答(这就是「通用」的含义)。<p>构造一个对角线程序 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span>,其行为定义如下:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo stretchy=false>(</mo><mi>P</mi><mo stretchy=false>)</mo><mo>=</mo><mrow><mo fence=true>{</mo><mtable columnalign="left left" columnspacing=1em rowspacing=0.36em><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mtext>死循环</mtext></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>若 halts</mtext><mo stretchy=false>(</mo><mi>P</mi><mo separator=true>,</mo><mi>P</mi><mo stretchy=false>)</mo><mo>=</mo><mtext>真</mtext></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mtext>立即停机</mtext></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>若 halts</mtext><mo stretchy=false>(</mo><mi>P</mi><mo separator=true>,</mo><mi>P</mi><mo stretchy=false>)</mo><mo>=</mo><mtext>假</mtext></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding=application/x-tex>D(P) = \begin{cases} \text{死循环} & \text{若 } \text{halts}(P, P) = \text{真} \\ \text{立即停机} & \text{若 } \text{halts}(P, P) = \text{假} \end{cases}</annotation></semantics></math></span><p>请注意这里的要害操作:把程序本身作为自己的输入喂给自己(<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><mi>P</mi><mo separator=true>,</mo><mi>P</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\text{halts}(P, P)</annotation></semantics></math></span>)。这正是对角线论证中「取第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 个数的第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 位」的直接类比——让一个程序「审视」自身的自指动作。<p>导出矛盾。现在考察具体的执行 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo stretchy=false>(</mo><mi>D</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>D(D)</annotation></semantics></math></span>。<ul><li>若 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><mi>D</mi><mo separator=true>,</mo><mi>D</mi><mo stretchy=false>)</mo><mo>=</mo><mtext>真</mtext></mrow><annotation encoding=application/x-tex>\text{halts}(D, D) = \text{真}</annotation></semantics></math></span>(即判定「<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo stretchy=false>(</mo><mi>D</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>D(D)</annotation></semantics></math></span> 停机」),那么根据 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span> 的定义,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo stretchy=false>(</mo><mi>D</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>D(D)</annotation></semantics></math></span> 应该死循环。这与「它停机」矛盾。<li>若 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><mi>D</mi><mo separator=true>,</mo><mi>D</mi><mo stretchy=false>)</mo><mo>=</mo><mtext>假</mtext></mrow><annotation encoding=application/x-tex>\text{halts}(D, D) = \text{假}</annotation></semantics></math></span>(即判定「<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo stretchy=false>(</mo><mi>D</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>D(D)</annotation></semantics></math></span> 不停机」),那么根据 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span> 的定义,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo stretchy=false>(</mo><mi>D</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>D(D)</annotation></semantics></math></span> 应该立即停机。这与「它不停机」矛盾。</ul><p>两种情况都导致自相矛盾。因此,「存在通用停机判定器 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mtext>halts</mtext></mrow><annotation encoding=application/x-tex>\text{halts}</annotation></semantics></math></span>」的假设是假的。停机问题不可判定。<p>若按某种规则把所有程序枚举出来(<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><msub><mi>P</mi><mn>1</mn></msub><mo separator=true>,</mo><msub><mi>P</mi><mn>2</mn></msub><mo separator=true>,</mo><msub><mi>P</mi><mn>3</mn></msub><mo separator=true>,</mo><mo>…</mo></mrow><annotation encoding=application/x-tex>P_1, P_2, P_3, \dots</annotation></semantics></math></span>——这是可行的,因为程序本质上就是有限长的字符串),并想象一张无穷表格:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo fence=true>(</mo><mtable columnalign="center center center" columnspacing=1em rowspacing=0.16em><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><msub><mi>P</mi><mn>1</mn></msub><mo separator=true>,</mo><msub><mi>P</mi><mn>1</mn></msub><mo stretchy=false>)</mo></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><msub><mi>P</mi><mn>1</mn></msub><mo separator=true>,</mo><msub><mi>P</mi><mn>2</mn></msub><mo stretchy=false>)</mo></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋯</mo></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><msub><mi>P</mi><mn>2</mn></msub><mo separator=true>,</mo><msub><mi>P</mi><mn>1</mn></msub><mo stretchy=false>)</mo></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><msub><mi>P</mi><mn>2</mn></msub><mo separator=true>,</mo><msub><mi>P</mi><mn>2</mn></msub><mo stretchy=false>)</mo></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋯</mo></mstyle></mtd></mtr><mtr><mtd><mstyle displaystyle=false scriptlevel=0><mrow><mi mathvariant=normal>⋮</mi><mpadded height=0em voffset=0em><mspace height=1.5em mathbackground=black width=0em></mspace></mpadded></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mrow></mrow></mstyle></mtd><mtd><mstyle displaystyle=false scriptlevel=0><mo lspace=0em rspace=0em>⋱</mo></mstyle></mtd></mtr></mtable><mo fence=true>)</mo></mrow><annotation encoding=application/x-tex>\begin{pmatrix} \text{halts}(P_1, P_1) & \text{halts}(P_1, P_2) & \cdots \\ \text{halts}(P_2, P_1) & \text{halts}(P_2, P_2) & \cdots \\ \vdots & & \ddots \end{pmatrix}</annotation></semantics></math></span><p>对角线程序 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span> 的行为恰恰取决于这张表格的主对角线 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mtext>halts</mtext><mo stretchy=false>(</mo><msub><mi>P</mi><mi>i</mi></msub><mo separator=true>,</mo><msub><mi>P</mi><mi>i</mi></msub><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\text{halts}(P_i, P_i)</annotation></semantics></math></span>,并且刻意表现得相反。这与康托尔构造「每一位都与相应对角线数字不同的实数」在结构上完全一致。<p>我们无法真正实现一个通用停机判定器(因为它根本不存在!),但可以通过代码演示这种逻辑矛盾是如何具体产生的:<pre><code class="hljs language-python"><span class=hljs-keyword>import</span> sys
sys.setrecursionlimit(<span class=hljs-number>50</span>)
<span class=hljs-keyword>def</span><span class="hljs-title function_">hypothetical_halts</span>(<span class=hljs-params>f, x, fuel=<span class=hljs-number>10</span></span>):
<span class=hljs-string>"""假想的停机判定器(仅用于悖论演示;并非真正可行的实现)"""</span><span class=hljs-keyword>try</span>:
result = f(x, fuel)
<span class=hljs-keyword>return</span> result <span class=hljs-keyword>is</span><span class=hljs-keyword>not</span><span class=hljs-literal>None</span><span class=hljs-keyword>except</span> RecursionError:
<span class=hljs-keyword>return</span><span class=hljs-literal>False</span><span class=hljs-keyword>def</span><span class="hljs-title function_">D</span>(<span class=hljs-params>x, fuel=<span class=hljs-number>10</span></span>):
<span class=hljs-keyword>if</span> fuel <= <span class=hljs-number>0</span>:
<span class=hljs-keyword>raise</span> RecursionError(<span class=hljs-string>"燃料耗尽,模拟死循环"</span>)
will_halt = hypothetical_halts(x, x, fuel - <span class=hljs-number>1</span>)
<span class=hljs-keyword>if</span> will_halt:
<span class=hljs-keyword>raise</span> RecursionError(<span class=hljs-string>"模拟死循环:halts 判定其停机,故 D 刻意不停机"</span>)
<span class=hljs-keyword>else</span>:
<span class=hljs-keyword>return</span><span class=hljs-string>"D 停机"</span>
outcome = D(D, fuel=<span class=hljs-number>8</span>)
<span class=hljs-built_in>print</span>(<span class=hljs-string>"D(D) 的执行结果:"</span>, outcome)
</code></pre><p>输出:<pre><code class="hljs language-scss">=== 对角线悖论推导 ===
假设 <span class=hljs-built_in>halts</span>(f, x) 是一个完美的停机判定器(能正确判断任意程序)
构造 <span class=hljs-built_in>D</span>(x):若 <span class=hljs-built_in>halts</span>(x,x)==停机 则 D 死循环;若 <span class=hljs-built_in>halts</span>(x,x)==不停机 则 D 立即停机
情形 <span class=hljs-selector-tag>A</span>:若 <span class=hljs-built_in>halts</span>(D,D) 判定为「停机」 -> 根据 D 的定义,D 应死循环 -> 矛盾
情形 <span class=hljs-selector-tag>B</span>:若 <span class=hljs-built_in>halts</span>(D,D) 判定为「不停机」 -> 根据 D 的定义,D 应立即停机 -> 矛盾
=> 无论哪种判定都会自相矛盾,证明通用 halts 函数不可能存在。
=== 代码实例化(低燃料以便快速演示) ===
触发递归异常,模拟自相矛盾的执行状态:模拟死循环:halts 判定其停机,故 D 刻意不停机
</code></pre><p>这段代码里的 <code>hypothetical_halts</code> 显然不是一个真正的「通用」判定器——它只能在一个有限的 <code>fuel</code>(步数预算)内运行,这正是我们能在一台真实计算机上执行它的唯一原因。而这恰恰佐证了图灵的结论:一个总能给出正确答案的真正通用的停机判定器不可能存在。我们所能写的任何「模拟版本」都必然带有这样或那样的局限(比如这里采用的步数上限)。<h2 id=哥德尔不完备定理>哥德尔不完备定理</h2><p>1931 年,库尔特·哥德尔运用对角线论证的一个更加精巧的变体,证明了数理逻辑史上最深刻的成果之一:<blockquote><p>哥德尔第一不完备定理。任何包含初等算术的相容(不自相矛盾)形式系统,都存在一个在该系统内既不能被证明也不能被否证的命题。</blockquote><p>哥德尔的证明大体分为三步:<ol><li><p>哥德尔编号。把形式系统中的每个公式和每个证明都编码成一个自然数(这种编码技巧本身就是天才之举,如今被称为「哥德尔数」)。这样一来,「某个证明是否证明了某个公式」就变成了自然数上的一个算术关系,可以在系统内部表达出来。</p><li><p>构造自指命题。利用编码技巧,构造一个命题 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span>,其核心内容是:</p><span class=katex><math display=block xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi><mo>:</mo><mo>=</mo><mtext>「命题 </mtext><mi>G</mi><mtext> 本身在该系统内不可证明」</mtext></mrow><annotation encoding=application/x-tex>G := \text{「命题 } G \text{ 本身在该系统内不可证明」}</annotation></semantics></math></span><p>这是一个高度自指的构造,其数学基础被称为对角线引理(又称不动点引理):对任意只含一个自由变量的公式 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>ϕ</mi><mo stretchy=false>(</mo><mi>x</mi><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\phi(x)</annotation></semantics></math></span>,都能构造一个句子 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>ψ</mi></mrow><annotation encoding=application/x-tex>\psi</annotation></semantics></math></span>,使系统证明 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>ψ</mi><mo>↔</mo><mi>ϕ</mi><mo stretchy=false>(</mo><mo><mi mathvariant=normal>⌜</mi></mo><mi>ψ</mi><mo><mi mathvariant=normal>⌝</mi></mo><mo stretchy=false>)</mo></mrow><annotation encoding=application/x-tex>\psi \leftrightarrow \phi(\ulcorner \psi \urcorner)</annotation></semantics></math></span>(其中 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mo><mi mathvariant=normal>⌜</mi></mo><mi>ψ</mi><mo><mi mathvariant=normal>⌝</mi></mo></mrow><annotation encoding=application/x-tex>\ulcorner \psi \urcorner</annotation></semantics></math></span> 表示 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>ψ</mi></mrow><annotation encoding=application/x-tex>\psi</annotation></semantics></math></span> 的哥德尔数)。这个引理正是「对角线」思想在逻辑中的抽象:它让一个命题能够「谈论」关于其自身代码的某种性质。</p><li><p>导出矛盾的两难。</p><ul><li>若系统能证明 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span>,那么根据 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span> 的含义(「<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span> 不可证明」),系统就同时证明了一个假命题——与系统的相容性矛盾。<li>若系统能否证 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span>(即证明 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi mathvariant=normal>¬</mi><mi>G</mi></mrow><annotation encoding=application/x-tex>\neg G</annotation></semantics></math></span>,相当于证明「<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span> 可证明」),那么在合理的补充条件下,这同样会导致矛盾。<li>因此 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span> 既不能被证明也不能被否证——它是系统内的一个「不可判定命题」。</ul></ol><p>与前面两个证明的共通之处:<table><thead><tr><th><th>对角数 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span><th>对角集 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span><th>对角程序 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span><th>哥德尔句 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>G</mi></mrow><annotation encoding=application/x-tex>G</annotation></semantics></math></span><tbody><tr><td>自指的对象<td>每一位「避开」自身<td>收集「不属于自己」的元素<td>用自己的行为否定对自身的判定<td>断言「我不可证明」<tr><td>依赖的机制<td>十进制展开的对角线<td>集合属于关系的自指<td>程序以自身为输入<td>通过哥德尔编号实现的自指<tr><td>矛盾的来源<td>假定的双射无法覆盖 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>y</mi></mrow><annotation encoding=application/x-tex>y</annotation></semantics></math></span><td>假定的满射无法覆盖 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi></mrow><annotation encoding=application/x-tex>D</annotation></semantics></math></span><td>假定的判定器导致悖论<td>假定的可证明性导致悖论</table><p>这四个证明,本质上都在做同一件事:利用「自指」构造出一个必然与假定的「完备覆盖」相矛盾的对象。正是这一点,使对角线论证——横跨集合论、可计算性理论与数理逻辑三大领域——成为二十世纪最具穿透力的证明思想之一。<h2 id=延伸>延伸</h2><p>除了上面讨论的三个经典应用,对角线论证及其背后的思想还渗透进计算机科学与数学的许多角落:<ul><li><p>柯尔莫哥洛夫复杂度。对角线论证可用于证明「不可压缩」字符串的存在——即无法由任何比字符串本身更短的程序生成的字符串——而且这样的字符串构成绝对多数。</p><li><p>复杂度理论中的时间与空间谱系定理。对角线论证被用来证明,赋予图灵机更多的时间或空间预算,确实能让它解决严格更多的问题(这是 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>P</mi><mo>⊊</mo><mtext>EXP</mtext></mrow><annotation encoding=application/x-tex>P \subsetneq \text{EXP}</annotation></semantics></math></span> 等谱系关系的基础)。</p><li><p>塔斯基不可定义定理。该结果证明,在足够强的形式系统内,「真」这个概念无法被完整定义;其证明结构与哥德尔定理非常相似。</p><li><p>罗素悖论。虽然从历史上看它早于对角线论证在现代形式下的普遍认知,但「所有不包含自身的集合构成的集合」这个悖论,<span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>R</mi><mo>=</mo><mo stretchy=false>{</mo><mi>x</mi><mo>:</mo><mi>x</mi><mo mathvariant=normal>∉</mo><mi>x</mi><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>R = \{x : x \notin x\}</annotation></semantics></math></span>,与康托尔定理证明中的集合 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>D</mi><mo>=</mo><mo stretchy=false>{</mo><mi>a</mi><mo>:</mo><mi>a</mi><mo mathvariant=normal>∉</mo><mi>f</mi><mo stretchy=false>(</mo><mi>a</mi><mo stretchy=false>)</mo><mo stretchy=false>}</mo></mrow><annotation encoding=application/x-tex>D = \{a : a \notin f(a)\}</annotation></semantics></math></span> 具有完全相同的结构——两者都是「自指 + 自我排除」的产物。</p></ul><p>若把对角线论证提炼成一个可复用的「思维模板」,其轮廓大致如下:<ol><li>出发点(反证)。假设存在一种「完美覆盖」或「普适判定」——一个双射、一个满射、一个判定器、一个证明系统。<li>构造自指的对象。利用假设本身所提供的「编号」或「映射」能力,构造一个新对象,它刻意与假定的覆盖中的每一个条目「作对」(对角数、对角集、对角程序、自指命题)。<li>验证其逃逸性。证明这个新对象与假定覆盖范围内的每一个条目都系统性地不同(通常通过「第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 个条目在第 <span class=katex><math xmlns=http://www.w3.org/1998/Math/MathML><semantics><mrow><mi>n</mi></mrow><annotation encoding=application/x-tex>n</annotation></semantics></math></span> 个位置不同」这一模式)。<li>导出矛盾。按假设,这个新对象应当被覆盖——但构造过程保证了它必然逃脱覆盖。矛盾产生;原假设被推翻。</ol>