哥德尔不完备定理----一切都是非真即假的吗_千峰翠色的博客-程序员秘密

如果有一个人说：“我在说谎”

那么，他说的话是谎言吗？

如果是假的，那么他说的反而是真的，如果是真的，那么他说的反而是假的了。

如果这话是匹诺曹说的，恐怕他的鼻子就得变成永动机了。

匹诺曹：“怪我咯？”

很多人都听说过这个悖论，它叫说谎者悖论，据说是世界上最早的悖论，产生于数千年前。

虽然与悖论打了几千年交道，可数学家们不觉得它们可怕，因为它们与数学无关。数学怎么可能会有这么无厘头的东西？他们还要“统一数学”呢。

笛卡儿、莱布尼茨等都想创造一个“万物理论”。莱布尼茨甚至设想把逻辑学用数学符号表示，以后每逢争论，拿支笔一算就见分晓了。可惜莱布尼茨太超前了，没能完成他的夙愿。

19世纪末，康托尔提出集合论，为统一数学提供了一线希望。可就在数学家踌躇满志的时候，悖论这个幽灵却悄无声息地将临在数学家们面前。

“包含一切集合的集合是否存在？”如果存在，那么它自己为什么不在其中。这个问题困扰着康托尔本人。

更为严重的是罗素悖论

设集合S是由一切不属于自身的集合所组成，即“S={x|x ∉ x}”。

那么问题是：S包含于S是否成立？首先，若S包含于S，则不符合x∉S，则S不包含于S；其次，若S不包含于S，则符合x∉S，S包含于S

我们也可以通俗地描述如下：

在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。

这给“统一数学”的希望蒙上了一层阴霾，在无理数的发现，无穷小量的矛盾之后被称为“第三次数学危机”。

为了处理这次危机，数学家们给出了公理来排除这种定义。然而“悖论”依然阴魂不散。

20世纪20年代，大数学家希尔伯特向全世界的数学家抛出了个宏伟计划，其大意是建立一组公理体系，使一切数学命题原则上都可由此经有限步推定真伪，这叫做公理体系的“完备性”；希尔伯特还要求公理体系保持“独立性”（即所有公理都是互相独立的，使公理系统尽可能的简洁）和“无矛盾性”（即相容性，不能从公理系统导出矛盾）。

然而，哥德尔的证明无情的击碎了这一企图。他证明出了这样两个定理。

第一不完备性定理
任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。
第二不完备性定理
如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。

哥德尔的证明揭示出，任何足够强到蕴含了皮亚诺算术系统（PA）的一致（即无矛盾）的系统都是不完备的。

要证明哥德尔的不完备性定理，只需在假定的形式系统T内表达出一个为真但无法在T内推导出（证明）的命题。

他构造了这样一个命题，用自然语言表达就是：命题P说的是“P不可在系统T内证明”（这里的系统T当然就是我们的命题P所处的形式系统了），也就是说“我不可以被证明”。

这跟文章开头提到的说谎者悖论非常相似，只是把“说谎”改成了“不可以被证明”。

我们注意到，一旦这个命题能够在T内表达出来，我们就可以得出“P为真但无法在T内推导出来”的结论，从而证明T的不完备性。

为什么呢？我们假设T可以证明出P，而因为P说的就是P不可在系统T内证明，于是我们又得到T无法证明出P，矛盾产生，说明我们的假设“T可以证明P”是错误的，根据排中律，我们得到T不可以证明P，而由于P说的正是“T不可证明P”，所以P就成了一个正确的命题，同时无法由T内证明！

哥德尔定理的证明不仅具有数学意义，而且蕴含了深刻的哲学意义。著名数学家外尔曾发出这样的感叹：“上帝是存在的，因为数学无疑是相容的；魔鬼也是存在的，因为我们不能证明这种相容性。

此文略作简介和分享，博主仍在学习中，可能有些不足，还望指正。

更多关于哥德尔不完备定理德资料见：

康托尔、哥德尔、图灵——永恒的金色对角线 By刘未鹏

Gödel's incompleteness theorems Wikipedia

They Said "A smooth sea never made a skillful mariner."

原文地址：http://ozem.pw/archives/871

本文链接：https://blog.csdn.net/qq_36403266/article/details/54782277

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Linux中Shell脚本--awk的用法_awk写入文件_Archie_java的博客-程序员秘密

语法格式：awk [选项] ‘指令’ 操作文件常用选项：-F 指定分隔符，分隔符用""引起来-v：var=value在awk程序开始之前指定一个值valu给变量var，这些变量值用于awk程序的BEGIN快-f：后面跟一个保存了awk程序的文件，代替在命令行指定awk程序实例1：在命令行直接输入awk指令awk '{print}' 1.txt #逐行读取文件1.txt内容并打印awk '{print $0}' 1.txt #逐行读取文件内容，并打印该行，$0保存的是当前行的内容awk

共享打印机提示服务器没有运行,winXP共享打印机提示“工作站服务没有启动”|没有启动服务器Workstation服务..._Yang Yanzhe的博客-程序员秘密

winXP共享打印机提示“工作站服务没有启动”|没有启动服务器Workstation服务在行业办公的地方还有相当一部份使用的电脑系统中都是winXP系统，winXP系统也已经有很多年头了，使用方面的操作大家已经再熟悉不过，使用共享打印机的操作技巧大家也已经掌握，利用好共享打印机可以提升工作效率，但是在使用共享打印机时可能会遇到系统提示“工作站服务没有启动” 没有启动服务器服务窗口的问题，那如果在使...

Ubuntu16.04 —— 系统安装 :: 工控机安装ubuntu16.04_Comma_dev的博客-程序员秘密

1. 按F12进入boot manager界面选择从USB启动盘启动。然后选择：选择要安装的系统系统开始启动：启动完成，双击安装程序2. 开始安装选择语言选择要安装的方式设置用户名密码开始安装，安装成功后重启。3. 安装完成机器现在可以正常启动了。启动时，让选择F2/F12可以不选择，等待一会儿即可正常启动。拨出系统安装盘即可。...

python清除输出_使用Python 3删除一些输出内容_嘉兴水果代采代发的博客-程序员秘密

Review:Thishotel has been here awhile.However,they’ve kept it up nicely.Thestaffisvery professionalandfriendly.Therooms have everything you need.Onlycon,the ice machines are on the2ndand8thfloors only...

【layui数据表格】多选批量删除增删改查_layui数据表格多选_Khun_HWJ的博客-程序员秘密

数据表格的增删改查第一步：创建表格，id定位到表格名，data获取Ajax数据内容，field定位到ajax数据相对应的名字，toolbar定位到script的barDemo，通过lay-event="edit"来控制点击<table class="layui-hide" id="list" lay-filter="list" lay-data="{id:'list'}">&lt...

goim中的 bilibili/discovery (eureka)基本概念及应用_weixin_34293059的博客-程序员秘密

goim 文章系列(共5篇):goim 架构与定制从goim定制, 浅谈 golang 的 interface 解耦合与gRPCgoim中的 bilibili/discovery (eureka)基本概念及应用goim 的 data flow 数据流goim的业务集成(分享会小结与QA)有个 slack 频道, 不少朋友在交流 goim , 欢迎加入slack #goim0....