Kurt Gödel · 1906–1978

哥德尔

他证明了：任何一套讲得清的规则，都留着自己说不出的真话

G \leftrightarrow \neg\mathrm{Prov}_T(\ulcorner G \urcorner)

不完备定理 · 一句说自己证不出来的话

库尔特·哥德尔生于奥匈帝国的布尔诺，一座纺织城，家里因为他没完没了的追问叫他「为什么先生」。他到维也纳大学本想读理论物理，被一门数论课改了方向。他常去维也纳学派的聚会，却从不认同那批人：他们认为数学不过是一套约定好的符号游戏，他相信数学对象像石头一样真实存在，人只是去发现它们。这个信念正是他能想到那个证明的原因——一个彻底的形式主义者不会去找「真却证不出来的话」，因为在他看来「真」就是「证得出来」。1929 年，二十三岁的哥德尔在博士论文里证明了一阶逻辑的完备性：凡是逻辑上真的，都能一步步推出来。两年后，他指出了这句话的边界。

1930 年 9 月 7 日，柯尼斯堡的一场圆桌讨论上，他平静地说出了不完备定理，会场没有反应；第二天，希尔伯特在同一座城市讲了「我们必须知道，我们必将知道」。1931 年论文发表，希尔伯特纲领就此关闭。1938 年他又把康托尔的连续统假设做掉一半——证明它驳不倒。1940 年他取道西伯利亚铁路与日本逃离欧洲，此后一直在普林斯顿高等研究院，每天与爱因斯坦一起走回家；爱因斯坦晚年说，自己去研究院「只是为了有幸能和哥德尔一起散步」。1949 年他送给爱因斯坦的生日礼物，是一个可以回到过去的宇宙解。晚年他确信有人要给他下毒，只肯吃妻子阿黛尔做的饭；1977 年她住院半年，1978 年 1 月他在普林斯顿医院去世，体重不到三十公斤，死亡证明上写的是「人格障碍导致的营养不良与饥饿衰竭」。

佚名摄，约1925 · 普林斯顿高等研究院档案馆藏，公有领域

生平

1906
生于布尔诺
奥匈帝国摩拉维亚的一座纺织城，今属捷克。追问太多，家里叫他「为什么先生」。
1929
完备性定理
博士论文：一阶逻辑里凡是真的都证得出来。他先证明的，是「够用」这一半。
1930
柯尼斯堡：一句没人接的话
9 月 7 日圆桌讨论上首次说出不完备定理，全场无人接话；次日希尔伯特在同城宣告「我们必将知道」。
1931
不完备定理发表
够强的系统里总有真而不可证的命题；而且它证不了自己不会出矛盾。
1938
可构造宇宙 L
证明选择公理与连续统假设与 ZF 相容——它们驳不倒。另一半要等科恩 1963 年补上。
1940
逃往美国
取道西伯利亚铁路、日本与旧金山，进普林斯顿高等研究院，此后没有再回欧洲。
1948
入籍听证会
他在美国宪法里找出一处逻辑漏洞，可以合法地变成独裁国。爱因斯坦与摩根斯坦一路把话岔开。
1949
哥德尔宇宙
给爱因斯坦七十岁生日的礼物：一个旋转的宇宙解，里面有路能走回自己的过去。
1978
卒于普林斯顿
妻子住院后他不再进食。死亡证明写：人格障碍导致的营养不良与饥饿衰竭。

展品厅

绝大多数展品都可以亲手把玩——这是本馆的立馆之本；少数以叙述为主的，做成故事展签。

镇馆之宝 · 亲手玩

这句话证不出来

他造了一句话，说的是「我在这套规则里证不出来」。

G \leftrightarrow \neg\mathrm{Prov}_T(\ulcorner G \urcorner)

希尔伯特要给全部数学配一套规则：不出矛盾、什么都证得出来、还能机械地判定。哥德尔 1931 年一举打掉了中间那条。办法是在系统内部造一句自指的话 G，它说的正是「G 在本系统里不可证」。两条路都走不通：若系统能证明 G，那它就证出了一句说自己不可证的话，自相矛盾；若能证明 G 的否定，那等于证出了「G 可证」，同样出事。所以只要系统不出矛盾，G 和它的否定都证不出来。而站在系统外面看，G 说的正是实情——它是真的。两年前他刚证明过一阶逻辑里「真」与「可证」是一回事；现在他指出，一旦系统强到能谈论算术，这两个词就分家了。

分头假设「G 可证」与「G 的否定可证」，一步步推到矛盾

G ⟷ ¬Prov(⌜G⌝)

读作：「这句话在 T 里证不出来。」⌜G⌝ 是 G 自己的编号，Prov(n) 是「编号为 n 的那句话有证明」。把编号这件事办成，靠的是隔壁那件展品。

这里的 T 可以是任何一套「不出矛盾、公理列得出来、且强到能谈算术」的系统。换一套更强的规则不管用：新系统有新的 G。这不是某一套公理没搭好，是形式系统本身的价格。

给每一句话编一个号

把符号串变成数，数学就能开口谈论自己了。

\ulcorner s_1 s_2 \cdots s_k \urcorner = 2^{s_1} \cdot 3^{s_2} \cdots p_k^{s_k}

一句公式是一串符号，一个证明是一串公式——这些都是语法层面的东西，本来与「数」无关。哥德尔给每个符号配一个数，再把这串数放到接连的素数的指数上乘起来。由算术基本定理，这个乘积只能这样拆回去，于是每一句话、每一个证明都拿到了自己独一份的号码。这一步是整台机器的枢纽：它把「第 m 号证明恰好是第 n 号命题的证明」这种关于符号的说法，翻译成了一句纯粹关于自然数的算术命题。数学从此能在自己内部谈论自己，那句自指的话才造得出来。今天编译器把源代码读成语法树、再把语法树读成数据，做的是同一件事。

零不是一——皮亚诺公理之一

符号	¬	(	0	=	S	0	)
编号	7	13	1	5	3	1	15
位置素数	2	3	5	7	11	13	17

2⁷ · 3¹³ · 5¹ · 7⁵ · 11³ · 13¹ · 17¹⁵

= 849379380498660411659278081730828160（36 位数）

「一个证明」也是一串符号，照样有编号。于是「第 m 号证明恰好证明了第 n 号命题」这句关于符号的话，变成了一句关于两个自然数的算术命题——算术从此能谈论算术自己。那句「这句话证不出来」正是这样造出来的。

系统证不了自己没毛病

一套规则若真的不出矛盾，它就恰恰说不出这一点。

T \nvdash \mathrm{Con}(T)

第二不完备定理是第一条的推论，也是那一击真正落下的地方。把第一条定理的整个论证在系统内部原样走一遍，得到的是一句系统自己也认的话：「本系统若不出矛盾，则 G 不可证」。可 G 说的就是「G 不可证」，于是系统证明了「本系统不出矛盾」蕴涵 G。既然 G 证不出来，「本系统不出矛盾」也就证不出来。希尔伯特纲领要的正是用最保险的有限手段证明全部数学不会出矛盾，这句话把它关死了：想证明一套规则可靠，只能站到它外面去，而外面那套又要谁来担保？根茨 1936 年确实证出了算术的相容性，代价是用上一直走到 ε₀ 的超限归纳——那已经不是算术拿得出的东西。

T₀ = PA（皮亚诺算术）
证得出加、乘与归纳法。初等数论几乎全在里面——素数无穷多也证得出来。
证不出Con(T₀)：「T₀ 永远推不出矛盾」

希尔伯特纲领要的是：用最保险、最有限的手段，一劳永逸地证明全部数学不会出矛盾。第二不完备定理说的正是这件事办不到——不是还没办成，是原理上办不成。

可构造宇宙 L

他造了一个瘦到极致的集合宇宙，在那里连续统假设是对的。

L = \bigcup_{\alpha \in \mathrm{Ord}} L_\alpha

康托尔问：ℵ₀ 与实数之间还有没有别的无穷？他一生没能回答，希尔伯特把这一问排在二十三题的第一位。哥德尔 1938 年从另一头下手——不去证明它对，而去证明它驳不倒。办法是把集合的宇宙削瘦：一层层往上造，每层只收下能由已有各层明确定义出来的集合，别的一概不要。这样得到的 L 仍然满足 ZF 的全部公理，而在 L 里，选择公理与连续统假设都成立。既然存在这样一个模型，ZF 就推不出它们的否定。二十五年后科恩补上另一半：用力迫法往模型里塞进足够多的新实数，造出一个连续统假设不成立的宇宙。合起来，希尔伯特第一题有了答案，而答案是——这个问题在现有的公理里没有答案。

康托尔问：ℵ₀ 与 |ℝ| 之间还有没有别的无穷？希尔伯特把它排在二十三题的第一位。答案是这个问题在 ZFC 里没有答案——哥德尔证明了驳不倒，科恩证明了证不出。

一个能回到昨天的宇宙

1949 年，他送给爱因斯坦一个解——在那里，你能沿一条路走回自己的过去。

\mathrm{d}s^2 = a^2\left[-(\mathrm{d}t + e^{x}\mathrm{d}z)^2 + \mathrm{d}x^2 + \mathrm{d}y^2 + \tfrac{1}{2}e^{2x}\mathrm{d}z^2\right]

到普林斯顿之后他改行了一阵，去解爱因斯坦的场方程。他找的是一个整体在旋转的宇宙：物质处处旋转，会把各处的光锥一起带着倾倒。离转轴越远，锥倒得越狠；过了某个半径，锥已经倒到可以让一条封闭的曲线全程留在锥内——那是一条闭合类时曲线，沿着它一路向前走，每一步都朝着自己的未来，最后却回到了出发的那个事件。他要说的不是时间机器可行：他连这趟旅行要多少燃料都算了，多得不切实际。他要说的是，广义相对论并不禁止这件事，所以「时间在流逝」不可能是从物理定律里推出来的。手法还是他一贯的那一套——不争论，造一个模型，让对方的立场自己说不出话。

半径 r / r_c = 1.32

锥已经倒过了头：绕轴一圈的那条路，整条都落在光锥之内。沿它走，每一步都朝着自己的未来，走满一圈却回到了出发的那个事件——这就是闭合类时曲线。哥德尔连这趟旅行要多少燃料都算了，多得不切实际；他要说的从来不是时间机器可行，而是广义相对论不禁止这件事。

1930 年 9 月 7 日，没有人听见

他在圆桌讨论上说了一段话，全场毫无反应；只有一个人追了出来。

那年秋天柯尼斯堡开了一场关于精确科学认识论的会议。9 月 7 日的圆桌讨论记录里，二十四岁的哥德尔说了一段话，大意是：即便一套形式系统里推出来的全是真命题，也仍然可能有真命题在其中证不出来。会议记录显示，讨论随后照旧进行，无人接话。散会后冯·诺依曼追上去细问；几周后他写信告诉哥德尔，自己顺着这条路独立推出了第二定理——哥德尔回信说，那已在他即将发表的手稿里。就在第二天，同一座城市，希尔伯特讲完了他一生最著名的那段话：「我们必须知道，我们必将知道。」两人此后似乎从未就此交谈。这不是一场辩论的胜负，而是一件更安静的事：一个纲领在它被喊得最响的那一天，已经倒了。

故事展签故事展签：一句话在会议记录里静静躺着，八十多年后仍在被引用。

传承

他的工作没有留在十八世纪——每条链的终点，都是你今天正在使用的东西。

不完备定理⟶图灵机与停机问题⟶可计算性理论与今天的计算机科学

哥德尔编码：把语法变成算术⟶系统能在内部描述自己⟶编译器、形式验证与自动定理证明

可构造宇宙 L⟶科恩的力迫法⟶独立性从一桩意外变成一门技术

哥德尔宇宙解⟶闭合类时曲线⟶广义相对论中的因果结构研究

语录

「要么人的心智无限地超过任何有限的机器，要么存在绝对无解的丢番图问题。」
—— 1951 年吉布斯讲演《数学基础及其哲学含义》，收于《哥德尔文集》第三卷，1995

「类与概念也可以设想成实在的对象……假定这样的对象存在，与假定物理对象存在一样合理。」
—— 《罗素的数理逻辑》，1944

「世界的意义，在于愿望与事实的分离。」
—— 写在私人笔记本里，年份不详；见王浩《逻辑之旅：从哥德尔到哲学》1996