【数理逻辑】Incompleteness Theorem

2018-11-10

字数统计: 1.9k字 | 阅读时长≈ 6分

在学数理逻辑的时候，有一个问题一直想不通：P->Q，为什么在P为假时，无论Q为真还是假，整个命题都为真。在当时，我想到了两个解释：

命题实际上包含的是一个世界观，P->Q是世界观P到Q的自然推导或者说是一种类似因果关系的宇宙定律，当作为前提的世界观都是错误的，那么这个世界就必然是混沌的，在混沌的宇宙中，没有你我之分，所有的事件都搅拌在一起，无论Q是什么，都是同一个结果：真。
数理逻辑需要明确的定义，既然当前件P是假的，那么P->Q的结果真假，是和P与Q具体是什么东西有关的。而数理逻辑是为了构建一个抽象的世界观，所以为了便于形式化的推导，数学家便将这种情况永久地定义为“真”。

可是，今天无意间看了一系列哥德尔不完备定理的文章，内心激动无比。

本文索引自哲学涉猎系列。

哲学涉猎系列，记录了我纯粹满足好奇心的不成熟的学习和摘录，主要涉及哲学各个学派、命题的学习、理解。包含的内容不多，但会龟速保持更新。

什么是哥德尔不完备定理

在哥德尔的论文中，我们一般所说的“哥德尔不完备定理”（有时候也被叫做“哥德尔第一不完备定理”）是指论文中的定理VI，原文如下：

TheoremVI: For every ω-consistent primitive recursive class κ of formulae, there is aprimitive recursive class-sign r , such that neither forall(v,r) nornot(forall(v,r)) belongs to Conseq(κ) (where v is the free variable of r).

尽量原汁原味的翻译如下：

定理VI：对于任意一个ω一致（第四重）的原始递归公理集合κ，一定存在一个原始递归（第三重、第四重）的表达式r，使得无论是“r总成立”这个命题，还是“r不总成立”这个命题，都不属于通过κ可推导出来的定理的集合（原文中的Conseq(κ)）。

我们简要理解“哥德尔不完备定理”说的是：一个足够复杂的公理体系（至少蕴含了皮亚诺算术公理），如果它是一致的（相容的，无矛盾的），那么它就是不完备的。这里的完备，指的是“对于任何可在这个公理体系内描述的命题，都可以在这个公理体系内得到判定，要么是正确的，要么是错误的”。

再用大白话解释一下，就是说，一个没有矛盾的公理体系内，总有一些命题是说不清楚对还是错的（务必注意，这是指在这个体系内说不清楚，不是说永远都说不清楚了）。也许有人说了，既然没矛盾的公理体系有问题，那就搞个有矛盾的公理体系呗。如果设想一个公理体系，一会儿告诉我们“1+1=2”，一会儿又告诉我们“1+1!=2”，相信不会再有人把这个公理体系当回事。有矛盾的公理体系会导致彻底的无意义和虚无

为什么哥德尔不完备定理成立

构造一个不一致（不相容、存在矛盾）的公理体系是无意义的。从直觉出发，我们都清楚，存在矛盾的体系当然有问题了。这里，我们给出逻辑上的说明（或者说证明）。

做这件事之前，让我们先来感谢罗素和怀特海，是他们的艰苦工作成果《数学原理》给出了数学形式化的基础。我们正是以此为基础，来说明一致性的重要意义。另外，了解《数学原理》中给出的数学形式化的基本表示，也是继续修炼第三重、第四重神功的基础，因为哥德尔就是基于《数学原理》中数学形式化的表达来证明“哥德尔不完备定理”的。

由于形式化表达的符号存在不同的样式，为避免歧义，本文中数学形式化的表达与哥德尔论文中的样子保持一致。以下是数学形式化的基本原则：

使用字母（一般使用p、q、r等）表示命题变量，即一个字母表示一个命题；使用如下符号表示特定逻辑（注意，形式化之后的表达式是无含义的，因此这些符号仅表示某种逻辑关系）：

～逻辑“非”；

∨ 逻辑“或”；

⇒ 逻辑“推出”，意思是“如果……那么……”；

∧ 逻辑“与”；

∀x∙p 对于任意x，p都成立；

∃x∙p 存在x使p成立；

组成合理的命题表达式。譬如，“p∨q”就是一个合理的命题表达式，而“p∨”就是一个错误的表达式。
两条变换规则：一是代入规则，可以使用其它的命题表达式对某个命题表达式中的某个命题变量进行全部统一替换；二是分离规则，其实就是我们常说的逻辑三段论，已知p和p⇒q成立，则q成立。
《数学原理》提出的四条基本逻辑推演公理：

(p∨p)⇒p

p⇒(p∨q)

(p∨q)⇒(q∨p)

(p⇒q)⇒((r∨p)⇒(r∨q))

大家可能觉得这四条基本逻辑推演公理看起来像是废话，由此可知《数学原理》这本巨著是从多么基础的逻辑出发的。不要小看这四条基本推演公理，它们可以推导出难以想象的复杂的结论。

好，以上四条数学形式化的基本原则叙述完毕，下面开始推出一个逻辑定理：p⇒(~p⇒q)。推演过程如下：

根据第二条推演公理，得到p⇒(p∨q)；

根据变换规则二，设p成立，则得到如下结论，

p∨q成立；

在p成立的前提下，设～p成立（即p不成立），则由∨逻辑的基本含义得到q成立（意思就是，“p或q”成立，且p不成立，那么必然q要成立）；

根据上述结果，在p成立的条件下，如果～p也成立，那么q成立。

于是得到上面的逻辑定理p⇒(~p⇒q)。注意，这里面q是一个自由的命题变量，根据基本变换规则一，可以把任何命题代入q。因此，我们得到了一个重要结论，如果有一个命题“p”和它的逻辑非“～p”都成立，那么任意命题q都成立。也就是说，有矛盾的公理体系可以推导出任意命题都成立。这就是为什么公理体系必须一致，不一致的公理体系为什么无意义的原因了。

“在非真实的前提下运用逻辑可以得出任何结果”。这句话时是有其逻辑基础的，”有矛盾的公理体系可以推导出任意命题都成立“。

这也是为什么，p->q，当p为假时，整个命题永远都是真的。

豁然开朗。