精华区文章阅读

发信人: ssos (存在与虚无·戒酒戒网), 信区: Math
标  题: 歌德尔定理(转载)
发信站: 哈工大紫丁香 (2001年11月25日08:58:49 星期天), 转信

【以下文字转载自 Computer 讨论区】
【原文由 ssos 所发表】
你好象对哥德尔定理的理解不太清楚，下面我分几个部分来说明一下，
首先申明一点的是，下面谈到的形式系统，人脑，或广义的系统等都
先假定它们自身是相容的，否则就没什么好说的了，讨论一个矛盾的
系统大概没有什么意义吧。
　
一、哥德尔定理大意
　
1. 哥德尔定理:  任何包含算术系统的(相容的)形式系统都是不完备的
　
2. 证明过程概述：
　
   设A是一个包含算术系统的形式系统, 记它所能表出的命题集合为 B
A 完备的意思是说: 对 B 中任何一个命题C, C或~C中要恰有一个能在
A 中被证出(注意是恰有一个，而不能是两个，否则 A 就不相容了)
　
   哥德尔采用了一种编号的办法可对B中所有的命题编上一个唯一的号
　
   接下去，哥德尔证明了命题: " B 中的k号命题不能在 A 中证出 "
是可以被 A 形式化的，即它属于B，记其编号为 p(k)
　
   一般情况下 p(k) ≠ k, 因此 k 号命题可以是假的，而p(k)号�
　
   但偏偏哥德尔找到了一个数g使 p(g)=g，于是B中就有这样一对命题
   g 号命题:          " B 中的g号命题不能在 A 中证出 "
   g 号命题的反命题:  " B 中的g号命题  能在 A 中证出 "

   若g 号命题能在 A 中证出，则与 g 命题自身叙述矛盾，所以 g 号
命题不能在 A 证出。若 g 号命题的反命题能在 A 中证出，则 g 号命
题能在 A 中证出，这也与 g 命题自身叙述矛盾，所以 g 号命题的反命
题也不能在 A 证出。

   就是说这一正一反两个命题都不可能在 A 中证出，于是就证明了 A
的不完备性。
　
二、几点说明
　
1. 人脑超越形式系统
　
    前面已说了，g 号命题不能在 A 中证出，也就是说 g 号命题是真的，
人脑能认识到这点，但形式系统 A 却证不出。从这个意义上讲，人脑是
超越形式系统 A 的。注意到 A 的任意性，就可以说人脑是超越任何形式
系统的。
　
2. 徒劳的补救方式
　
   当然，在以上步骤之后，你或许想可以将 g 号命题作为公理加进形式系统
A 中形成一个新形式系统 A'。在A'中就可以证出 g 号命题，这样的 A' 或许
就完备了。但不幸得很，A' 仍不会完备。因为我们可在 A' 中用完全相同的
办法再构造出一个新命题 g'，使 g' 与 ~g'在 A' 中都证不出。
　
三、几个可能的错误
　
1. 用"本命题不能在形式系统 A 中得到证明"来说明 A的不完备性
　
   请注意 A 的完备性并不是说对于所有的命题C,  C 或 ~C 中要恰有一个
能在 A 中被证出，这里的 C 必须要属于A所能表出的命题集合 B，否则就无从
证起了。一个不能在 A 中被形式化的命题自然谈不上能不能在 A 中被证出，
因此拿这样的命题来讨论 A 是否完备是没有意义的。
　
   例如我们讨论平面欧氏几何系统的完备性时，不能说该系统中不能证出概率
论中的某个定理就说平面欧氏几何系统不完备。
　
   因此若想用"本命题不能在形式系统 A 中得到证明"来说明 A 的不完备性，
必须证明 "本命题不能在形式系统 A 中得到证明" 这个命题是能在 A 中被
形式化的，哥德尔定理的证明实际上就是在 A 中千辛万苦地构造出这一个命题，
上面证明中的 g 号命题即是。
　
2. 对人脑超越形式系统的误解
　
   人脑超越形式系统的意思如前所述，是指对任何一个形式系统 A, 都存在
A 中的一个命题 g, g 在 A 中不能被证出，但人脑能认识到 g 是真的。当然
可能会存在另一个形式系统 A'，g 可在 A' 中被证出，但 A' 中也必然存在
一个命题 g', g' 不能在 A' 中证出，但人脑能认识到 g' 是真的。
　
   你在文中所说的 "形式系统不能证明那个命题，是因为形式系统的完备性。
如果不认为它完备，就可以证明这个命题了。"我没有看懂，哥德尔定理已经说
了形式系统都是不完备的，那你的"因为形式系统的完备性"是什么意思？另外
我提醒一句，形式系统不是只有一个，而是有各种各样的，请在考虑问题时不要
将不同的形式系统混淆起来。

3. 你的另一段话
　
   "当认为形式系统完备时，我们可以证明形式系统不能证明的命题，但可以按
照该命题的思路构造另一个命题，如果认为人脑完备，则人脑不能证明这个命题
，而形式系统能。"
　
   你的这段话我完全没有看懂，你的意思好象是说一个系统(包括形式系统和人
脑，姑且认为人脑是一个系统吧)，既可以是完备的，又会存在系统中不能证明
的真命题。但这句话明明是相互矛盾的啊。
　
四、关于人脑是否完备(个人观点)
　
1. 人脑是否完备
　
   我想首先应该对这个问题下一个定义。
　
   对一个系统，系统完备的意思应是说: 对系统能描述的任何一个命题C, C或
~C中要恰有一个能在系统中被证出(注意是恰有一个，而不能是两个，否则系统就
不相容了)
　
   如果将人脑视为一个系统，那么该系统所能描述的命题应该是全部可能的命题，
而人脑完备的意思就成了: 对任何一个命题C, C或~C中要恰有一个能被人脑证出。
也就是说对任何真命题都能被人脑证出。
　
   即人脑完备 <==> 任何真命题都能被人脑证出。
　
   这样一看人脑完备与否倒象一个信仰问题，我个人认为这是真的，即认为
人脑是完备的。
　
2. 对"人脑找不到本命题的证明"的分析
　
   看这样一个命题x: 人脑找不到本命题x的证明
　
   这个命题最有可能说明人脑不完备，即若 x 为假，那么人脑可找到 x 的证明
，这是矛盾的，所以 x 为真，即人脑找不到 x 的证明，于是人脑不完备。
　
   但是，再仔细想一想就会发现 x 实际上根本就不是一个命题!!!
　
   我们先来看一下著名的说谎者悖论 y: 这句话是假的。我想大家都知道 y 不
是一个命题吧。因为若 y 为真，则 y 为假; 而若 y 为假，则 y 为真; 总有矛盾
于是 y 不是一个命题。
　
　 x 的情况与此类似。假设 x 是个命题，若 x 为假，那么人脑可找到 x 的证明
这当然是矛盾的，所以 x 不是假的，而 x 是个命题，那么 x 就只能是真的，也就
是说我证明了 x，于是人脑找到了 x 的证明，但这与 x 本身的叙述矛盾，于是 x
也不能是真的。总有矛盾，故 x 不是命题
--


<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 天外飞仙]

Math 版 (精华区)