哥德尔证明:智力的交响乐
本期混乱博物馆是对上一期节目“哥德尔、埃舍尔、巴赫”的具体延续——在5分钟之内演示哥德尔不完备定理的证明方法。这无论对我们还是对观众来说,都是一个巨大的挑战。
这个数学史上极其重要的定理,不可能在短短几分钟内详细阐述清楚,为此我们几乎省略了所有细节的推敲,也简化了大部分的函数,但保留了公式化的表达方法。高度抽象的形式化逻辑必然会让普通观众遇到思维方式上的重大障碍,难以同步理解我们的演示。
但不要紧,感兴趣的观众可以反复暂停观看本期内容,结合《哥德尔证明》这本小册子,你可以在大约一周的时间内弄懂这个最有哲学影响力的数学问题,随后感受到整个人的智力都上了一个台阶。
而对于那些不感兴趣的观众,本来也没什么好损失的。
以下为视频文字稿:
接下来,我们将在6分钟之内用最简略凝练的语言证明往期节目引出的“哥德尔不完备定理”。这是一个博大精深的定理,理解时有相当的难度,请读者们不要放弃,反复思考本期内容,我们也会在结尾推荐辅助读物。 哥德尔不完备定理讨论的是一个形式系统的一致性和完备性:所谓一致性,就是不会自相矛盾,一会儿肯定一个命题,一会儿又否定这个命题;所谓完备性,就是对任何符合语法的命题,都能证明它是真还是假。
我们在中学数学学过一套“如果、那么”、“非、且、或”的形式系统,叫做命题逻辑。
比如说,小明是男孩是真的,男孩不穿裙子也是真的,那么小明不穿裙子也是真的。令p表示“一个人是男孩”,q表示“一个人穿裙子”,则命题形式化为: p ∧ ( p → ¬q ) → ¬q 命题逻辑具有绝对的一致性,要证明它也非常简单,我们只需回想这个定理:假命题可以推出任何结论。
比如说,如果蝙蝠侠没杀过人,你就是我大爷。令p表示“蝙蝠侠杀过人”,q表示“你是我大爷”,则命题形式化为: p → ( ¬p → q ) 那么现在假设命题逻辑不一致,就必然有某个命题p和非p同时为真,那么对于上面的公式,我们将进一步得出q为真,也就是说,对于不一致的形式系统,可以推出任何命题为真。
那么倒过来,只要有一个命题必然是假命题,就证明了命题逻辑具有一致性。 而这个必定为假的命题就是“所有的命题都永远为真”,我们因此顺利证明了命题逻辑的一致性。 但命题逻辑是一个很弱小的演算系统,连加法都不能计算,为了让它足以支撑绝大多数的数学研究,我们给它加入两类符号,构成了关键的强化:一类是量化符号∀和∃,“∀”表示“对于所有的”,“∃”表示“存在这样的”;另一类是非逻辑符号,其实就是引入了函数和常数等概念。
比如“每个自然数都有后继”,就可以形式化为: ∀x ( x ∈ N → sx ∈ N ) 任取x,如果x是自然数,那么x的后继是自然数。 这正是算术公理的一部分——像这样强化过的命题逻辑,就是一阶谓词逻辑,也是数学上最重要最广泛采用的形式化逻辑系统,哥德尔不完备定理所要讨论的,就是这个逻辑系统的一致性和完备性——而哥德尔的结论非常令人失望,在一阶谓词逻辑系统中,这两个都不可证。
他在1931年的论文《关于数学原理和相关系统的不确定命题》中给出了相当精彩的证明,但这个证明也非常复杂,仅事先构造的定义和概念就多达46个,但我们的介绍规避了所有可能规避的难题。
这个证明的核心思路并不复杂: 首先,我们需要在一阶谓词逻辑系统中构造一个公式G,并找到他的否定非G。 同时,我们的构造还要费些心机,使得G一旦在系统内得到证明,非G也同时会被证明,反之亦然。
这样一来,我们就发现了一阶谓词逻辑的矛盾和不足,它的一致性和完备性土崩瓦解。 所以显然的,如何构造公式G就是哥德尔证明的精髓所在,他为此首先发明了一种编码方案,能给所有可能的语句赋予唯一的自然数编号,这个编号称为对应语句的“哥德尔数”。
这意味着所有对数学命题的讨论就转化成了对自然数的讨论,或者说,把元数学命题转化成了数学命题。这使我们需要的那种矛盾再也不是传统的罗素悖论了。 接下来,哥德尔构造了一个哥德尔数为g的公式G1: ~(∃x)Dem(x,g) 它的直接意思是: 不存在x,使得哥德尔数为x的证明过程能够证明哥德尔数为g的公式 更简练地说,就是: “具有哥德尔数g的公式不可证”,或者“公式G1不可证” 接着,为了求出“g”究竟是多少,他构造了一个关键的函数: Sub(y,17) 表示对于哥德尔数为y的公式,将其中所有的变量y,都用这个哥德尔数y赋值,再求取新公式的哥德尔数。
但我们先不关心这个自指函数的y究竟是什么,只需把它赋给公式G1中的变量g,得到一个新的公式G2: ~(∃x)Dem(x,Sub(y,17)) 最后一步构造,是继续求出公式G2的哥德尔数n,并将这个n赋给公式G2中的y——这也就是我们最终的公式G了: ~(∃x)Dem(x,Sub(n,17)) 这里的n代表一个巨大的整数,是个常数,而非变量, 换句话说,哥德尔成功构造出了公式G,公式G的意思“公式G不可证”——这就麻烦了。
如果公式G本身可证,我们就证明了“公式G不可证”,如果公式G的否定可证,我们就证明了公式G可证——无论如何,我们都会同时证明公式G和公式G的否定,这是自相矛盾。也就是说,我们找到了一阶谓词逻辑系统的破绽,希尔伯特的计划因此成了泡影。
更加意义重大的是,这个破绽是自然算术的必然结果,那么凡是蕴含自然数的一阶逻辑系统都将带有这个破绽——而半个世纪以来无比昌明的计算机科学正是这样一个系统,那么哥德尔不完备不但意味着现在的计算机不能解决所有数学问题,还意味着这样的计算机永远不能构造出真正的人工智能。
