|||
哥德尔第二不完全定理
如果一个数学系统是协调的,那么它的协调性在那个系统里不可证。(协调就是无法推出矛盾的意思。)
换句话说:
如果它的协调性是可证的,那么将出现矛盾。
下面这个推理题和哥德尔定理的证明有些类似。
推理题
逻辑之岛上有两种人:好人和坏人。好人只说真话,坏人只说假话。
一天,一个游客来到逻辑之岛。岛上的某居民对他说:你永远不会相信我是好人。
假设这个游客具有内省能力。什么样的内省能力?如果相信p,则相信自己相信p。举个例子。他相信地球是圆的,那他会相信自己相信地球是圆的。此外还具有完美的逻辑推理能力。
游客会推出什么?
下面我们来证明,假设游客相信自己不会相信矛盾,则他会相信矛盾。
游客推理:
如果我相信他是好人。那么我相信他说的是真话,那么我相信,我永远都不相信他是好人。
而我相信他是好人,则我会相信我相信他是好人。
所以如果假设我相信他是好人,将得到我相信,我相信他是好人和我不相信他是好人。这样我的信念就矛盾了。
而我是不会相信矛盾的,所以假设错误,所以我不相信这居民是好人。
游客接着推理:
我不相信他是好人,而他也说我不相信他是好人,这说明他说的是真话,所以他是好人。
推理到这里,由于游客具有反省能力,所以游客相信自己相信他是好人。
游客继续推理:
我相信他是好人,而他又说我永远不会相信他是好人,他的话是假话,所以他是坏人。
这时,游客既相信他是好人,又相信他是坏人。信念矛盾了。
所以,如果游客相信自己不会相信矛盾,那么他将相信矛盾。
认知逻辑
上面实际上证明了:
B﹁B⊥∧B(p↔﹁Bp) ⇒ B⊥
它和下式等价:
﹁B⊥∧B(p↔﹁Bp) ⇒ ﹁B﹁B⊥
上面的式子里B表示相信,p表示那居民是好人,⊥表示矛盾。p↔﹁Bp表示:他是好人,当且仅当,游客不相信他是好人。
推理时,除了经典命题逻辑的规则外,还加了3条规则:
(1) 如果A是逻辑定理,那么BA
(2) 如果B(p→q) ∧Bp,那么Bq
(3) 如果Bp,则BBp
其中(1)和(2)表达的是完美的推理能力,(3)是自省能力。
上面的推理可以用符号严格地重写一遍。
和哥德尔定理的联系
将上面的B理解为“证明”。﹁B⊥∧B(p↔﹁Bp) ⇒ ﹁B﹁B⊥表示的就是哥德尔第二不完全定理。
在认知逻辑中直接引入B这个算子,但在哥德尔证明所用的数学系统中并没有这样的算子。他利用高超的技巧构造了“证明”这个谓词,同时证明了存在一个命题p,使得p↔﹁Bp是系统中的定理。他构造的命题p意思是这样的:本语句在本系统中无法证明。
在做完这些构造性的工作后,后面的证明就简单了,其过程和上面的证明一样。
参考资料:
Raymond Smullyan,Forever Undecided:A puzzle guide to godel,1987
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-23 21:32
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社