[控场AI]
· 7 分钟阅读· 3,910 字

哥德尔第二不完备定理:理论为何无法自证一致

哥德尔第二不完备定理:理论为何无法自证一致

哥德尔第二不完备定理表明,一致且包含算术的理论无法证明自身一致性,其证明依赖可证性条件形式化第一定理;勒布定理则揭示了T只为已证句子担保。

文章从“0=1恐慌”切入,解释哥德尔第二不完备定理:一致的、包含皮亚诺算术的理论无法在自身内部证明自己的一致性。证明的关键是将第一定理形式化进理论内部,依赖三条可证性条件D1、D2、D3,其中D3是核心黑箱。文章还介绍了勒布定理——T只为已证明的句子担保,并回答了亨金问题。通过构造理论T' = T + “T不一致”,说明一致不等于可靠,一致的理论也可能证明假话。最后澄清了定理的适用条件、强度要求及常见误解,并指出第二定理不阻止ZFC等更强系统证明PA的一致性。

从“0=1”恐慌说起

假如有人从皮亚诺算术的公理出发,一步步推出了0等于1,整座算术大厦就会坍塌——因为从矛盾出发,任何命题都能被推导出来。希尔伯特当然不认为这种事会发生,但他想要一个证明:用最朴素、最没有争议的方法,证明算术永远不会推出矛盾。

问题来了:皮亚诺算术(PA)能不能自己证明自己推不出0=1?这一集的答案是不能。而这个“不能”,几乎是上一集哥德尔句的直接推论。

一致性:一个“永不停机”的句子

把理论T的一致性写成算术句子,就是“T中不存在推出矛盾的证明的编码”,记作Con(T)。你可以把它想象成一台机器:不断检查自然数,看它是不是矛盾的证明编码。Con(T)说的就是——这台机器永远不停。

停机有有限的证据,不停机却没有。每一个具体的数都能核对,难的是“所有的数”。如果T真的一致,Con(T)就是一个真句子。因为“矛盾可证”为真当且仅当T真的证明了矛盾,而T一致时后者为假。

第三条,第三。

哥德尔编码是理解Con(T)的关键技术。它把形式系统T中的符号、公式和证明序列,都映射为自然数。具体而言,每个符号对应一个数字,公式对应数字序列,而证明序列(公式序列)则通过质数分解等技巧编码为单个自然数。这样,“T中存在矛盾证明”就变成了一个关于自然数的Σ₁命题:“存在自然数x,x编码了一个从T的公理出发、以矛盾结尾的证明序列”。由于证明的正确性可以在有穷步内机械检验,这个命题是可在PA中形式化表达的。Con(T)即该命题的否定,是一个Π₁命题。

可证性条件:让T照镜子

要把第一定理的证明搬进T内部,需要T对自己的可证性知道得足够多,即三条可证性条件(D1、D2、D3):

  • D1:如果T证明了φ,那么T也证明“φ可证”。镜子外的每个定理,镜子里都看得到。
  • D2:T能证明“如果φ可证蕴含ψ可证,并且φ可证,那么ψ可证”。镜子里的推理也遵守分离规则。
  • D3:如果φ可证,那么“φ可证”可证。镜子里还有镜子。

D3不是对任意句子都成立。拿哥德尔句G来试:如果T证明“G蕴含G可证”,再加上G蕴含G不可证,T就证明了G不成立——而一致的T不会证明G不成立。D3之所以成立,靠的是“φ可证”这个句子的特定形状:它说的是“存在一个证明”,存在的东西只要找出来,就能一步步核对。

现在,假如T还能证明我一致,T就能证明G。

把第一定理搬进T

回忆第一定理的论证:如果T证明了G,由D1,T也证明“G可证”;可G说的恰恰是“G不可证”,两者一起,T就矛盾了。浓缩成一句话:如果T证明G,那么T证明矛盾。

现在把这句话里的“证明”全部换成形式化的可证性谓词Prov_T,就得到T内部的一个句子:“如果G可证,那么矛盾可证”。T自己就能证明这个句子,步骤是:

  1. 由G的取法,T证明“G蕴含非P”(P即“G可证”)。注意非P就是P蕴含矛盾的缩写。
  2. 对第一行用D1,再用D2,得到“P蕴含(P蕴含矛盾)可证”。
  3. 再用一次D2,得到“如果(P蕴含矛盾)可证且P可证,那么矛盾可证”。
  4. 对G用D3,得到“P蕴含P可证”。
  5. 在T里假设P,串起第二、四、三步,最终得到“矛盾可证”。

最后取逆否:如果矛盾不可证,那么G不可证,按G的取法即G成立。T能证明“如果我一致,那么G”。假如T还能证明自己一致,T就能证明G——可第一定理说一致的T证明不了G,矛盾。这就是哥德尔第二不完备定理:一致的、包含皮亚诺算术的理论,证明不了自己一致。反过来读更醒目:能证明自己一致的,恰恰是不一致的理论。

勒布定理:T只为已证明的句子担保

1952年,亨金问了一个反过来的问题:用对角线引理造一个句子H,它说“我可证”,H到底可不可证?两种答案似乎都不矛盾。1955年,勒布给出了答案:H可证。他证明的是一个更一般的定理:如果T能证明“只要φ可证,φ就成立”,那么T其实已经能证明φ了。注意,这里没有假设T一致。

勒布定理还有一个耐人寻味的读法:“若φ可证,则φ成立”是T在为φ做担保。定理说,T只敢为它已经证明了的句子担保。所以T证明不了的真句子,远不止G一个。

亨金问题中的句子H是通过对角线引理构造的:存在一个句子H,使得T可证明H ↔ Prov_T(⌜H⌝)。直观上,H声称“我是可证的”。这一构造与哥德尔句G(声称“我不可证”)形成对照。勒布定理表明H实际上可证,其证明可通过在T中形式化“如果H可证则H”这一条件,并利用H的构造直接得到H。这解决了亨金问题:两种看似可能的答案中,只有“H可证”成立,而且这并不与第二定理冲突,因为H本身没有声称T一致。

一致不等于可靠:一个“坚信自己不一致”的理论

第二定理有一个看起来很荒唐的推论:既然T证明不了Con(T),那把它的否定“T不一致”加进去当公理,会不会矛盾?不会。如果加进去就矛盾,T用反证法就能证明Con(T),而这不可能。于是我们得到一个一致的理论T',它却坚信自己的基础T不一致——它证明“存在一个T中推出矛盾的证明”,可这句话是假的。

因为在标准自然数里,矛盾可证这句话是假的。

T'的模型不可能是标准自然数。在标准自然数里,“矛盾可证”是假的;而在T'的模型里,确实有一个非标准数b,模型认为它编码了一个推出矛盾的证明。但从模型外面看,这个“证明”的长度不是有限的,根本不是一个真正的证明。T'的信念是错的,可它自己永远驳不倒这个信念。这个例子清晰地划出了“一致”与“可靠”之间的距离。

非标准模型是解释T'行为的关键。一阶算术的理论可以有不与标准自然数同构的模型,称为非标准模型。这些模型包含所有标准自然数0,1,2,...,但还包含“非标准整数”,它们比任何标准自然数都大。在T' = T + ¬Con(T)的模型中,虽然从外部看T是一致的,但模型内部存在一个非标准数b,模型认为b编码了T中推出矛盾的证明。由于b是非标准的,其“长度”不是有限的,因此实际上不是一个真正的证明。然而,T'的内部视角无法区分标准与非标准数,因而坚信“T不一致”为真。这揭示了一阶逻辑的局限性:一致的理论可以拥有非标准模型,在其中为假句子被“证明”。

三个必须说清楚的细节

写法:Con(T)依赖于Prov_T的具体写法。第二定理针对的是“标准写法”,即满足D1到D3的写法。换一种不自然的写法,PA甚至能证明相应的一致性——所以定理的表述必须精确。

强度:要求T包含PA而不只是罗宾逊算术Q,因为D2、D3的证明需要在T里做归纳。

适用范围:它不只适用于算术。集合论ZFC能在内部定义自然数,所以只要ZFC一致,ZFC也证明不了自己一致。

这对希尔伯特计划意味着什么?通常认为有穷方法都能在PA里形式化,那么第二定理就说明PA的一致性没有有穷的证明。但这不是说PA的一致性无法证明——ZFC就能证明它,根岑也给出过用到超穷归纳的证明。这些证明没有凭空变出信心,只是把信任从PA转移到了别处;它们真正的价值,是精确量出了证明PA一致到底需要多强的手段。

就变成一套小小的摩太轮。

把“可证”写成方框算子,D1到D3加上勒布定理就构成一套小小的模态逻辑,即GL。1976年,索洛维证明:PA关于自身可证性的所有命题逻辑规律,恰好就是GL的定理。

根岑的证明是第二定理的一个重要补充。根岑在1936年给出了PA一致性的证明,但使用了超穷归纳(直至ε₀序数)这一方法,它不能在PA内部形式化。这恰好印证了第二定理:任何足以证明PA一致性的方法,都必须超出PA的表达能力。另一方面,ZFC可以证明PA的一致性,因为ZFC的强度远高于PA。但这些证明并非“凭空产生信心”,而是将信任从PA转移到了更强的系统。第二定理的真正意义在于精确刻画了证明PA一致性所需的最小强度,从而划定了有穷主义方法的界限,而非否定一致性证明的可能性。

四个常见误解

  1. “第二定理说明我们永远无法知道数学是否一致”——不对。定理只说T不能在自己内部证明自己一致,PA的一致性可以在ZFC里证明。
  2. “系统能证明自己一致,它就一定一致”——恰恰相反,对满足条件的T,能证明自己一致等价于它不一致。
  3. “一致的理论说的都是真话”——不对。T加“T不一致”就是一致却证明假话的理论。一致只排除自相矛盾,不排除说错话。
  4. “第二定理适用于任何形式系统”——也不对。它要求公理能被机器列出、包含足够算术、且一致性用自然的方式写出。

打开最后一个黑箱

今天做的事,本质是让T照镜子:可证性条件D1、D2、D3让T能在内部谈论自己的可证性;把第一定理的证明搬进T,T就证明了“如果我一致,那么G”;于是,一致的T证明不了自己一致。勒布定理是这一图景的一般化,第二定理是它的特例。而“T加上我不一致”仍然一致,提醒我们:一致不等于说真话。

第一集欠下的六个黑箱至此全部还清,第三个可证性条件是新揭开的。下一集将检查定理的每个条件,看看拿掉哪个条件会发生什么。

#哥德尔第二不完备定理#可证性条件#勒布定理#皮亚诺算术#一致性证明#数理逻辑#希尔伯特计划#哥德尔句
分享:

相关推荐