闲话 九个不可能性定理
只要乐于钻研，精于实践，我们立刻就能克服困难，只要再多一点时间，就能超越认知。
——美国阿灵顿国家公墓外海蜂（美国海军工兵营）纪念碑碑文
数学中一些最伟大的定理就是关于不可能性的定理。这里我们将介绍其中最著名的九个定理。
（1）
是无理数。传说，梅塔庞托的希伯斯（活跃于公元前 5 世纪）是毕达哥拉斯（约公元前 570—约公元前 495）的一个追随者。他因为证明正方形的边和对角线不可公度 6 而让他的同僚震怒。用今天的术语来说就是，他证明了 
是无理数。也就是说，我们无法找到整数 
和 
，使得 
。我们会在第 4章深入讨论这一发现。
6设有两条线段 
和 
，如果存在整数 和 ，使得 
，则我们称 和 可公度。——译者注
（2）费马大定理。1637 年，皮埃尔·德·费马（1601 或 1607[1]— 1665）在他的一本书的空白处写下了这句著名的话：“不可能把一个立方数分为两个立方数，或是把一个四次幂分为两个四次幂。更一般地，不可能把一个高于二次的幂分为两个同次幂。关于此，我发现了一种美妙证法，但这里空白太小，没法写下。”换句话说，如果 
是一个整数，那么 
没有正整数解。这个结论被称为费马大定理。超过三个半世纪以来，人们都无法证明它。直到 1994 年，秘密研究了 7 年的安德鲁·怀尔斯才终于证明了费马大定理。
（3）哥尼斯堡七桥问题。18 世纪中叶，普鲁士城市哥尼斯堡有七座跨越普列戈利亚河的桥（图 T.3）。当地居民在闲暇时，就会寻找一条走过每座桥刚好一次，并最终回到起点的散步路线。这一游戏被莱昂哈德·欧拉（1707—1783）得知，他在 1735 年证明了不存在这样一条路线。欧拉的方法如今被认为是图论领域的开端。
图 T.3 不能同时经过哥尼斯堡的七座桥的路线
（4）五次方程无根式解。二次方程的求根公式算得上是高中代数课内容的巅峰了。它为求方程 
的两个根提供了一种简单的计算方法。公式如下：
尽管复杂得多，三次方程和四次方程的根也有类似的表达方式。但是，五次或更高次方程的根无法用这样的公式来计算。特别是，多项式 
有一个实数根，大约是 - 1.673 04，但我们无法用整数、四则运算以及开方来表达这个数。尼尔斯·阿贝尔（1802—1829）在 1824 年给出了这个不可能性定理的第一个完整证明。
（5）连续统 7 不可数。我们有十根手指。我们知道这一点，因为手指和集合 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 中的元素可以一一对应起来。小孩子就是这样数手指的。格奥尔格·康托尔（1845—1918）推广了这一概念——用来数无穷集。如果一个集合能和正整数集 {1, 2, 3,…} 一一对应，那么我们称该集合可数无穷。整数、偶数、质数都是可数无穷集。最令人惊讶的是，有理数也是可数无穷的。但是康托尔证明了不是所有无穷集都是可数的，更大的、不可数的无穷是存在的。他证明了正整数和实数之间不存在一一对应的关系。这一发现震惊了数学界。如今它被认为是数学史上最重要的成果之一。它也是下面第 6 和第 9 个定理的核心所在。
7连续统是一个数学概念。当人们笼统地说“在实数集里实数可以连续变动”，也就可以说实数集是个连续统；更严格的描述需要使用序理论、拓扑学等数学工具。——译者注
（6）停机问题。任何写过简单计算机程序的人都知道，存在无限循环无法停止的程序。它可能只是个重复打印简单文字（“Hello world! Hello world! Hello world!...”）的程序，也可能是程序中的一个难以察觉的漏洞。当用户输入预想之外的内容时，这个漏洞就会导致程序进入无限循环。要是有个计算机程序能判断另一个计算机程序对于特定输入会不会无限循环不是挺好的吗？不幸的是，这样的程序并不存在。1936 年，艾伦·图灵（1912—1954）证明了这个不可能性定理。该问题现在被称作停机问题。[2]
（7）阿罗不可能性定理。有很多著名的选举被“第三方搅局者”影响。假设候选人 
和 
一对一角逐的话， 会获胜，甚至可能大胜。但如果与 有着类似政见的候选人 
参加选举，某些本来会投 的人就会投 ，那么这反而会让 赢得选举。所以 不是因为更受欢迎而胜选，而是因为多数投票没办法很好地适用于有三名候选人的情况。我们也有其他的投票机制，比如同意投票 8 或者排序复选制 9 等。每种投票机制都有其利弊。没有一种投票机制是完美的。1950 年，经济学家肯尼斯·阿罗（1921—2017）研究了排序投票制。在排序投票中，每位投票人对于候选人都有一个喜好排序。系统最后会得出一个总的候选人排名。阿罗给出了几个公平的投票机制应该具有的常识性的标准。他随后证明了不存在满足所有标准的完美投票机制。
8又称为“认可投票”或“赞成投票”，是一种在选举中可以多选的投票制度。——译者注
9在候选人超过两名的情况下，选民在选票上按喜好排列其支持的候选者。——译者注
（8）平行公设。欧几里得用一些定义、五条公理 10 和五条公设证明了《几何原本》中的全部定理。第五公设现在被称作平行公设，它听上去有些拗口，有些难以理解。约翰·普莱费尔（1748—1819）给出了下面这个更直观的等价版本：
10这里的公理原文为“common notion”，公设原文为“postulate”。在《几何原本》中，公设是几何特有的，而公理则是更一般的、常识性的原则。在现代数学中，不区分公设和公理。——译者注
“经过直线外一点有且仅有一条直线平行于已知直线。”
数百年间，数学家们曾认为平行公设是多余的，并且可以用其他四条公设推导出来。我们现在知道这是不可能的。在 19 世纪，数学家们发现了满足前四条公设，却不满足第五公设的非欧几何。在非欧几何中，普莱费尔公理并不成立。同理，第五公设也不成立。在马鞍形上，给定直线和直线外一点，有无数条经过这点的直线与已知直线不相交。在球面上，所有的线（大圆）都相交，所以经过一点不存在任何与已知直线毫无交点的直线。因为非欧几何的存在，我们知道了不可能用前四条公设推导第五公设。
（9）哥德尔不完备定理。最后一个不可能性定理精巧、深刻，又震撼人心：无法证明的定理是存在的，即便它们是真正的数学表述。数学家们很熟悉那些看上去无法证明的猜想，例如孪生素数猜想、哥德巴赫猜想和黎曼猜想。乐观的数学家们认为它们最终都会得证。但即便它们永远不会得证，那就意味着我们不可能证明它们吗？或许吧。有可能它们可以被证明，只是数学家们还不够有创新性，没能发现证明。但它们也有可能是正确的，并且是无法证明的。在 19 世纪和 20 世纪之交，数学家们致力于为数学构建一个坚实基础——一组能推导出所有数学的定义和公理。这梦想是如此宏大，最终却又化作泡影。1931 年，库尔特·哥德尔（1906—1978）证明了不完备定理。第一不完备定理指出，在任何足够复杂的公理体系中，都存在不能被证明的真命题。在某种意义上，这是最极致的不可能性的证明！
[1] 很多年来，我们都相信费马生于 1601 年，但最新证据表明，他可能生于 1607 年。参见巴尔纳（2001）。
[2] 这段讨论是停机问题的现代描述。图灵的描述稍有不同。他当时是在研究图灵机（这是我们今天的叫法），而他想要图灵机持续工作下去——停机是不好的。