您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
如何简单清晰地解释哥德尔不完备定理?
命题,定理,公理如何简单清晰地解释哥德尔不完备定理?
发布时间:2020-12-06加入收藏来源:互联网点击:
公理系统可能含有无穷条公理例如皮亚诺算术就是这样但要哥德尔定理生效必须存在检验证明是否正确的有效算法例如可以将关于自然数的所有在标准模型中为真的一阶语句组成一个集合这个公理系统是完备的哥德尔定理之所以无效是因为不存在决定任何一条语句是否公理的有效算法从另一方面说这个算法的不存在正是哥德尔定理的直接结果
另一个哥德尔定理不适用的特殊情况是将关于自然数的所有语句首先按长度然后按字典顺序排序并从皮亚诺公理集开始一个一个遍历列表如果发现一条语句既不能证明又不能否证就将它作为公理加入这样得到的系统是完备的兼容的并且是足够强大的但不是递归可枚举的
哥德尔本人只证明了以上定理的一个较弱版本以上定理的第一个证明是罗梭Rosser于1936年给出的
基本上第一定理的证明是通过在形式公理系统中构造如下命题
p = 此命题是不可证明的
来完成的这样它可以看成是说谎者悖论的一个现代变种
如果公理系统是相容的哥德尔证明了p及其否定不能在系统内证明因此p是真命题p声称它不可证明而它确实不能尽管其证明不能在系统内形式化请注意将p作为公理加入系统并不能解决问题扩大了的系统中会有另一个哥德尔语句出现
罗杰·彭罗斯声称可被机械地证明的和对人类来说看起来是真的的这一区别表明人类智能不同于自然的无意识过程这一观点未被普遍接受因为正如Marvin Minsky 所指出的人类智能有犯错误和理解不相容和谬误句子的能力但Marvin Minsky透露说库尔特·哥德尔私下告诉他他相信人类有一种到达真理的直觉方法但因为跟计算机式的方法不同人类可以知道为真的事情并不受他的定理限制
对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点也可以作如下评论我们其实不知道p是真是假因为我们并不也无法知道系统是否是相容的因此实际上我们并不知道系统之外的任何真理我们所确知的只有这样一个命题
要么p在系统内部无法证明要么该系统是不相容的
这样的命题之前已经在系统内部被证明实际上这样的证明已经给出
第一不完备定理的证明要点
要充实对证明要点的描述主要的问题在于为了构造相当于p是不可证明的这样的命题pp就必须包含有自身的引用而这很容易陷入无穷循环将要介绍的哥德尔巧妙的把戏后来被艾伦·图灵用于解决可判定性问题
开始的时候每个公式或者说可形式化的命题都被我们的系统赋予一个唯一的数称为哥德尔数这要通过一种可以方便地在哥德尔数和公式之间机械地来回转换的方式来完成因为系统足以表述数的概念因此也就足以表述公式的概念了
象F(x这样的公式含有一个自由变量x它们称为命题形式一旦x被一个特定的数代替它就马上变成一个真正的特定命题于是它要么是在系统中可证明的要么不命题形式自身并不是命题因此不能被证明也不能能被否证但每一个命题形式F(x都有一个哥德尔数可用G(F表示无论自由变量取什么值G(F的取值都不会改变
通过小心地分析系统的公理和推理规则可以写下一个命题形式P(x它表示x是系统中一个可以证明的命题的哥德尔数形式描述如下如果x是一个可证明命题对应的哥德尔数P(x就可被证明而其否定~P(x则不能尽管这对于一个证明要点来说已经足够但在数学上却不太严格请参见哥德尔和罗素的有关论文关键字是omega-consistency
哥德尔的把戏来了一个命题形式F(x称为不可自证的当且仅当把命题形式F的哥德尔数G(F代入F中所得的命题F(G(F是不可证明的这个定义可以形式化于是可以构造一个命题形式SU(z表示z是某个不可自证命题形式的哥德尔数SU(z的形式描述如下
对某个命题形式F(x有z = G(F而且设y是命题F(G(F的哥德尔数则有~P(y成立
我们所要的语句p就可以如下定义
p = SU(G(SU))
直观上当问到p是否为真的时候我们是在问不可自证这个特性本身是不可自证的吗这很容易让人联想到理发师悖论那个理发师只替那些不替自己理发的人理发他替自己理发吗
让我们假定公理系统是相容的
如果p可以证明于是SU(G(SU)为真根据SU的定义z = G(SU就是某个不可自证命题形式的哥德尔数于是SU就是不可自证的根据不可自证的定义SU(G(SU是不可证明的这一矛盾说明p是不可证明的
如果p = SU(G(SU的否定是可以证明的则根据SU的定义z = G(SU就不是不可自证命题形式的哥德尔数这意味着SU不是不可自证的根据不可自证的定义我们断定SU(G(SU是可以证明的同样得到矛盾这说明p的否定也是不可证明的
因此p既不可证明也不可否证
第二不完备定理的证明要点
令p是如上构造的不确定命题且假定系统的相容性可以在系统内部证明我们已经看到如果系统是相容的则p是不可自证的这个证明过程可以在系统内部形式化因此命题p是不可证明的或者~P(p可以在系统内证明
但是最后一个命题就等价于p自己而且这种等价性可以在系统内部证明从而p就可以在系统内证明这一矛盾说明系统是不相容的
-----------------------------
关于此词条原文中以下部分我发现存在较大矛盾和歧义
在原文中先称哥德尔数是针对命题形式的是不随命题形式中的变量x而改变的而下文中却又对特定的命题给出哥德尔数它表示x是系统中一个可以证明的命题的哥德尔数设y是命题F(G(F的哥德尔数
以上是难以理解的自相矛盾的
也有可能是原文除了对命题形式还隐含了对命题的哥德尔数运算法则没有写出来下文中会提到
在此之前由于对原文的进一步理解可能导致歧义为了避免歧义我先做如下语法规定
为了区别F是作为命题形式的一部分还是作为变量只是这里的变量F是命题形式我把所有命题形式中的变量用*代替以明确下文中引号内是引用原文故不一定遵守此语法规定而引号外遵守此语法规定
在这种语法规定下G(F和G(F(*)是不同的
G(F是个命题F是赋予变量的值命题形式是G(*)
G(F(*是命题形式*是变量赋值x后的命题是G(F(x))
于是又存在一个问题原文中的G(F)是G(F还是G(F(*))
假设原文隐含的运算法则是一个命题F(x)的哥德尔数G(F(x))=G(F(*)从而命题也有了哥德尔数则由此推出原文的表达有2种可能的歧义
-------------
⒈原文G(F意为G(F)
-------------
原文当且仅当把命题形式F的哥德尔数G(F代入F中所得的命题F(G(F是不可证明的
此句中把G(F代入意为代入G(F
故命题F(G(F即是命题F(G(FF是变量则其命题形式是*(G(*))
原文对某个命题形式F(x)有z=G(F而且设y是命题F(G(F的哥德尔数则有~P(y成立
根据上句此句中y=G(F(G(F)))=G(*(G(*)))显然y的值是定值与F变化无关
~P(y是否成立则与命题F(G(F是否不可证明有关即与F变化有关
-------------
⒉原文G(F意为G(F(*))
-------------
原文当且仅当把命题形式F的哥德尔数G(F)代入F中所得的命题F(G(F是不可证明的
此句中把G(F代入意为代入G(F(*
故命题F(G(F其实是命题F(G(F(x)))x是变量则其命题形式是F(G(F(*)))
原文对某个命题形式F(x有z = G(F而且设y是命题F(G(F的哥德尔数则有~P(y成立
上一篇:学逻辑学的真正用途是什么?
下一篇:返回列表
相关链接 |
||
网友回复(共有 0 条回复) |