您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
如何简单清晰地解释哥德尔不完备定理？
命题,定理,公理如何简单清晰地解释哥德尔不完备定理？
发布时间：2020-12-06加入收藏来源：互联网点击：
但是，注意到z是一个哥德尔数，它对应着一个公式。根据不动点定理（不知道也没关系，想知道的同学参考https://www.zhihu.com/question/66094972/answer/238396535），存在一个数a，使得UNPROVABLE(A)的哥德尔数恰好是a自身。事实上，这个UNPROVABLE(A)就是我们最开始要构造的那个G了。因为UNPROVABLE(A)为真，当且仅当unprovable(a)，即a具有算术性质unprovable，这等价于a（通过哥德尔编码）所对应的PM系统内公式不可证，即UNPROVABLE(A)不可证。也就是说，我们成功地构造出了一个公式，它“说它自己不可证”。这个公式为真，但不可证。这就证完了整个定理。
这篇文章在百度上大量存在，他完美的解释了哥德尔定理，但是哥德尔定理还有第二个定理，第二，完全性定理，有兴趣的同学，请搜索一下百度。
回答于 2019-09-11 08:43:50
在数理逻辑中哥德尔不完备定理是库尔特·哥德尔于1930年证明并发表的两条定理哥德尔定理是一阶逻辑的定理故最终只能在这个框架内理解
简单地说第一条定理指出
任何一个相容的数学形式化理论中只要它强到足以蕴涵皮亚诺算术公理就可以在其中构造在体系中既不能证明也不能否证的命题
这条定理是在数学界以外最著名的定理之一也是误解最多的定理之一形式逻辑中有一条定理也同样容易被错误表述有许多命题听起来很像是哥德尔不完备定理但事实上是错误的稍后我们可以看到一些对哥德尔定理的误解
把第一条定理的证明过程在体系内部形式化后哥德尔证明了他的第二条定理该定理指出
任何相容的形式体系不能用于证明它本身的相容性
这个结果破坏了数学中一个称为希尔伯特计划的哲学企图大卫·希尔伯特David Hilbert提出象实分析那样较为复杂的体系的相容性可以用较为简单的体系中的手段来证明最终全部数学的相容性可以归结为基本算术的相容性但哥德尔的第二条定理证明了基本算术的相容性不能在自身内部证明因此当然就不能用来证明比它更强的系统的相容性了
哥德尔不完备定理的意义
在形式逻辑中数学命题及其证明都是用一种符号语言描述的在这里我们可以机械地检查每个证明的合法性于是便可以从一组公理开始无可辩驳地证明一条定理理论上这样的证明可以在电脑上检查事实上这样的合法性检查程序也已经有了
为了这个过程得以进行我们需要知道手头有什么样的公理我们可以从一组有限的公理集开始例如欧几里德几何或者更一般地我们可以允许无穷的公理列表只要能机械地判断给定的命题是否一条公理就行在计算机科学里面这被称为公理的递归集尽管无穷的公理列表听起来有些奇怪实际上自然数的的通常理论中称为皮亚诺公理的就是这么一样东西
哥德尔的第一条不完备定理表明任何一个允许定义自然数的体系必定是不完全的它包含了既不能证明为真也不能证明为假的命题
存在不完备的体系这一事实本身并不使人感到特别惊讶例如在欧几里德几何中如果把平行公设去掉就得到一个不完备的体系不完备的体系可能只意味着尚未找出所有必须的公理而已
但哥德尔揭示的是在多数情况下例如在数论或者实分析中你永远不能找出公理的完整集合每一次你将一个命题作为公理加入将总有另一个命题出现在你的研究范围之外
你可以加入无穷条公理例如所有真命题到公理列表中但你得到的公理列表将不再是递归集给出任意一条命题将没有机械的方法判定它是否是系统的一条公理如果给出一个证明一般来说也无法检查它是否正确
在计算机科学的语言中哥德尔定理有另一种表述方式在一阶逻辑中定理是递归可枚举的你可以编写一个可以枚举出其所有合法证明的程序你可以问是否可以将结论加强为递归的你可以编写一个在有限时间内判定命题真假的程序吗根据哥德尔定理答案是一般来说不能
不确定命题的例子
哥德尔和保尔·科恩得出的一些结果结合起来给出了不确定命题既不能证明也不能否证的命题的一个实际例子选择公理和连续统假设都是集合论的标准公理系统内的不确定命题
在1973年同调代数中的怀特海问题被证明是集合论中的不确定命题
1977年Paris和Harrington证明了组合论中的一个命题拉姆赛理论的某个版本在皮阿诺公理给出的算术公理系统中是不确定的但可以在集合论的一个更大体系中证明为真
在计算机科学中用到的Kruskal的树问题也是在皮亚诺公理中不确定而在集合论中可证明的
Goodstein定理是一个关于自然数的相对简单的命题它在皮亚诺算术中是不确定的
Gregory Chaitin在算法信息论中构造了一个不确定命题即``Chaitin 随机数Ω的第n个字节是否为0"这样的命题在ZFC内是不可判定的.
对哥德尔定理的一些进一步解释
由于哥德尔的第一条定理有不少误解我们举出一些例子
该定理并不意味着任何有趣的公理系统都是不完备的例如欧几里德几何可以被公理化为一个完备的系统事实上欧几里德的原创公理集已经非常接近于完备的系统所缺少的公理是非常直观的以至于直到出现了形式化证明之后才注意到需要它们
该定理需假设公理系统可以定义自然数但是并非所有系统都能定义自然数例如塔斯基Tarski证明了实数和复数理论都是完备的公理化系统
这理论用在人工智慧上则指出有些道理可能是我们能够判别但机器单纯用一阶逻辑断却无法得知的道理不过机器可以用非一阶逻辑的逻辑系统
讨论和推论
不完备性的结论影响了数学哲学以及形式化主义使用形式符号描述原理中的一些观点我们可以将第一定理解释为我们永远不能发现一个万能的公理系统能够证明一切数学真理而不能证明任何谬误
以下对第二定理的另一种说法甚至更令人不安
如果一个公理系统可以用来证明它自身的相容性那么它是不相容的
于是为了确立系统 S 的相容性就要构建另一个系统 T 但是 T 中的证明并不是完全可信的除非不使用 S 就能确立 T 的相容性举个例子自然数上的皮亚诺公理的相容性可以在集合论中证明但不能单独在自然数理论范围内证明这对大卫·希尔伯特的著名的未解决的23个数学问题中的第二个给出了一个否定回答
理论上哥德尔理论仍留下了一线希望也许可以给出一个算法判定一个给定的命题是否是不确定的让数学家可以忽略掉这些不确定的命题然而对可判定性问题的否定回答表明不存在这样的算法
要注意哥德尔理论只适用于较强的公理系统较强意味着该理论包含了足够的算术以便承载对第一不完备定理证明过程的编码基本上这就要求系统能将一些基本操作例如加法和乘法形式化例如在鲁宾逊算术Q中那样有一些更弱的公理系统是相容而且完备的例如Presburger算术它包括所有的一阶逻辑的真命题和关于加法的真命题
上一篇：学逻辑学的真正用途是什么？
下一篇：返回列表
相关链接 |
||
| 网友回复（共有 0 条回复） |