如何简单清晰地解释哥德尔不完备定理？库尔特 。哥德尔于1931年发表了一篇重要的论文:《论数学原理和有关系统I的形式不可判定命题》 。文章证明了一条后来以他的名字命名的不完全性定理(这里的完全性指的是完备性) 。定理说:在任何含初等数论的相容(这里的相容通俗的讲就是不产生矛盾)的形式系统(形式系统可以简单的理解为由一些公理组成的)中，存在着不可判定命题(这句话可以简单的理解为，你即不能证明这个命题是正确的，也不能证明这个命题是错误的 。)，即命题本身和它的否定在该系统中都不可证 。考虑到二值逻辑(所为二值逻辑指逻辑值要么为"真“要么为"伪"两种情况必取一)中，命题和它的否定必有一真，不可判定命题是真的，为此不完全性定理实际上断言了，上述系统中存在着“真"的不可证命题 。这种表述通常称之为哥德尔第一定理 。该定理还有一个推论:一个包含初等数论的形式糸统的相容性，在该系统内是不可证明的 。这个表述通常称为哥德尔第二定理 。哥德尔的定理用通俗的话说:就是在现有的公理和定理的条件下，存在着一些命题 。它们即不能证明是正确的，也不能证明它是错误的 。那么在数学中有这样的命题吗？ 。在数学中还真有这样的命题，那就是"连续通假设" 。其实，现在人们把它当成一个公理 。连续通假设通俗的讲就是，直线上的点与实数的个数一样多即点数与个数相等 。哥德尔定理是现代逻辑发展史上的一座丰碑，一个转折点，它开创了现代逻辑发展的新时期 。哥德尔的不完全性定理和塔斯基的形式语言的真理论及图灵机和判定问题的理论，已被国际逻辑界赞誉为现代逻辑的三大成果 。亚里士多德是古希腊最伟大的思想家 。他创建了古典的形式逻辑，被西方人称之为"逻辑之父" 。有人为认，现代能与亚里土多德相比的逻辑学家，只有哥德尔 。他的不完全性定理 。是二十世纪数学，逻辑学领域中最卓越的成果 。rr什么是不完全性 。大多数人的理解就是“存在不可证的真命题’，但其实不完全性是一个十分专业的逻辑学概念，不是简单几个字就能说清的 。首先还是要说一些背景性的东西 。数学工作是靠数学证明来完成的，每个证明总得有个出发点，不然证明就无法开始 。因此，整个数学必然要有一些不证自明的出发点，由它们出发来构建整个数学大厦 。这些出发点就是数学公理 。但公理为什么是正确的呢？这时似乎就只能求助于我们的直观 。那些直观上非常简单，甚至根本无法想象它不对的那些数学命题就能够作为公理，比如欧式几何的五条公理：任意两点能连成一条直线、所有直角都相等...等等 。这些都是看起来很trivial甚至不值一提的命题，但正是因为这样，它们才足够作为公理——因为它们看起来不可能错 。但人们逐渐发现，靠直观的公理还是有可能会错 。比如集合论的公理（见 LLLBK：据说罗素悖论有解，如何解？）会导致矛盾，欧式几何的第五公理虽然说不上错但完全可以被修改为非欧几何 。直觉总是有可能不靠谱的，因此有些形式主义的数学家（如希尔伯特）希望把直觉完全排除出数学 。这时，谁来保证公理为真？形式主义者会说，公理没有什么真假可言，也没有什么意义，它们仅仅是人为约定的符号组成的符号串而已，数学家所做的工作无非就是按照既定的推理规则从一个符号串推出另一个符号串 。这就像下象棋一样，每个棋子有自己的移动规则，车走直线，马会被拐马脚，炮需要支炮架才能攻击，这样的理解有助于我们记住每个棋子的移动规则 。但即使不这样理解，也不影响一个人会下象棋 。他不必把棋子“车”理解为战车，“马”理解为马，“炮”理解为炮，“帅”理解为军队的大帅，他也可以学会下象棋并且下的不错 。数学家不必理解那些数学符号的“意义”，只需要知道该如何按照既定的推导规则推理下去就行了 。这样一来，数学公理系统就变为了纯形式的符号系统 。形式系统简单来说，有三部分：符号、公理、推导规则 。公理是由符合组成的公式，形式系统做的事就是从公理出发，根据推理规则，机械地推导一个又一个的公式 。我举一个例子（GEB中的例子），以下这个系统叫ep系统：符号：-, e, p公理：x-exp-，其中x代表任意一串“-” 。（如 ---e--p-, -----e----p-都是公理，注意x不是系统内的符号，只是我们为了简写这一公理模式而将-的串简写为x）推导规则：从xeypz可以推出x-eypz-，其中xyz都代表任意一串“-” 。（如，可从 --e-p-推出---e-p--）简单地说，这个系统中的合法字符串都长这样...e...p... 字符e和p将“-”的串分成了三段，这一推导规则意为，如果一个字符串被推导出来了，那么可在这个字符串的第一段“-”串和第三段“-”串后各添加一个“-” 。这个形式系统可以从公理出发，根据推导规则推导出类似-----e--p---的字符串，推导如下：公理：---e--p-推出：----e--p--推出：-----e--p---事实上，一个形式系统就是一个字符串操作机器，它有一些公理和推导规则，然后就能哗啦啦地得到许许多多的字符串（或者叫公式） 。当然，形式主义者需要先证明，自己的形式系统能够推导出所有数学中的真命题，这样才能用形式系统真正取代传统的数学研究 。一旦证明了这一点，就可以不再管什么是“真”命题，而只进行纯形式的推导就够了 。也就是说，虽然本质上形式系统是没有意义的，但人们希望自己的形式系统能够“表达”一些东西 。在数学中，形式主义数学家希望形式系统能“表达”所有的数学真理 。这个“表达”是很神秘的概念，以上面的ep系统为例，它表达了什么？如果你进行了十几个系统内的推导，你会发现导出的公式都是类似这样的：---e-p--, -----e----p-, ----e-p---... 第一段“-”的数量等于第二段和第三段“-”的数量之和 。反过来，类似 ----e-p-, -----e---p---这样不满足第一段“-”的数量等于第二段和第三段“-”的数量之和的公式是推不出来的 。因此这个ep系统似乎“表达”了加法 。需要注意的是，这种“表达”关系并不是唯一的，而是我们希望它能表达什么，系统本身并没有一个固定的表达 。ep系统可以表达加法——只要把e理解为equal，p理解为plus就行了 。但它也同样可表达减法，只要把e理解为减法，而p理解为=就行了 。那么，是不是说有了ep系统之后，加减法就不再是必要的了，我们可以像形式主义者所说的那样，不用再管加减法的意义，彻底抛弃传统的加减法，只需要按照ep系统去操作就可以取代传统的加减法呢？现在还是不够的 。要想证明ep系统确实有取代加法算术的能力，我们需要证明两点：ep系统的完全性：所有正确的加法算式（如2+3=5, 5+7=12等）都能在ep系统中推出 。ep系统的可靠性：所有ep系统能推出的公式，都表达的是正确的而不是错误的加法算式 。（如ep系统不能推出4=1+2）简单地说就是，可靠性保证了ep系统能推的都是正确的算式，完全性保证了正确的算式ep系统都能推出 。这两条合起来保证了ep系统能完成所有的加法运算 。其中，可靠性是很好证明的，只需证明ep系统的公理都是正确的，并且ep系统的推导规则是保真的（如果推导规则的前提是正确的，那么结论也是正确的） 。这样由于系统内所有公式都由公理出发经过推理规则得到，而公理是对的，推理规则保证了不可能从对的推出错的，那么系统内所有公式就都是对的了 。但完全性是很难证明的，事实上完全性证明是逻辑学的中心问题之一 。（我暂时也不知道怎么证明ep系统的完全性...）以上是用ep系统举例，说明了什么是可靠性和完全性 。相对的，不完全性自然就是说，人们希望一个形式系统能表达某领域内所有的真命题，但这个系统做不到，即，有一些真命题是该形式系统推不出的 。哥德尔不完全性定理说的就是这个 。哥德尔证明了，能够表达初等数论（算术）的形式系统，总存在一些真的算术命题是它无法推出的 。（这里有错，根据评论里 指出，哥德尔证明的不是这个，而是“存在一个公式，形式系统既不能推出它，也不能推出它的否定，即形式系统无法判定它” 。）当然，这种形式系统比上面的ep系统复杂得多，但基本的原理就是这样 。形式主义数学家希望他们的形式系统足够刻画整个数论，即能推出所有的算术真命题，但年轻的哥德尔粉碎了他们的梦想 。简单来说，这种表达算术的形式系统包含一些类似 的符号——都是我们现在经常在数学中见到的 。这种包含量词 和变元 和性质 的逻辑叫做一阶逻辑 。这个名称要来源于罗素的《数学原理》 。在罗素悖论之后，数学家们对数学的基础展开了新的探索，罗素自己当然也不例外 。他拯救罗素悖论的方式是“类型论”（见 LLLBK：据说罗素悖论有解，如何解？），将语言进行分层，最底层的就是一阶的 。数学家们按照类型论纲领发展数理逻辑，自然是先从最简单的第一阶开始研究，这些研究现在被归入了一阶逻辑这个领域中 。事实上，哥德尔的论文题目就是《〈数学原理〉及有关系统中的形式不可判定命题》，也就是《论罗素那本书里的系统以及相关的一系列系统中有什么推不出的命题》 。3. 定理的证明虽然这篇论文本身艰深难懂，但思路倒是非常简明 。把哥德尔证明的那个不完全的形式系统叫做PM.首先要区分两个层次的定理：系统内定理和元定理 。系统内定理就是PM能推出的公式，如 就是PM的内定理 。而元定理是关于PM系统本身的定理 。如“ 的首个字符是 ”就是一个元定理，“ 在系统内可推导（简称“可证”）”也是一个元定理 。显然，内定理和元定理是两个不同层次的东西 。元定理陈述了一些关于内定理的事情，但内定理无法陈述关于元定理的事 。但如果内定理也能陈述关于元定理的事呢，情况会怎么样？那我们就可以在系统内部用字符串表达“xxx公式不可证”，“xxx公式的首字符是 ”这种元定理 。我们甚至有可能写出一个公式，它表达了“本公式不可证” 。为表达对哥德尔的敬意，把表达了“本公式不可证”的系统内公式记作G 。显然，G为真当且仅当G不可证，G为假当且仅当G可证 。PM系统的可靠性是毋庸置疑的——没有数学家会使用不可靠的系统 。因此G是绝对不能为假的，因为这意味着G可证，即PM系统推出了假命题，这违反了可靠性 。因此，G为真，但这恰好说明G不可证，这也就是说存在不可证的真公式，因此PM系统是不完全的 。因此哥德尔定理证明的关键就在于如何构造这个G 。更本质地说，如何发现PM系统能表达关于它自身的元定理 。我们已经知道的是，PM系统能够表达算术命题，比如1=1这种 。那如果算术能够表达PM的元定理，不就说明了PM能表达PM的元定理？简单的表示就是：PM—（表达）—算术—（表达）—PM的元层面—（表达）—PM因此，问题的关键就落在了，如何建立算术和PM系统的元层面之间的关系 。举例来说，类似 “ 的首字符是 ”这样的元定理，是否能找到一个类似 这样的正确算式来刻画？哥德尔通过哥德尔编码的方式来完成这个任务，哥德尔编码给每个基本符号如 等等指派一个数字，如以上三个符号可分别指派1，2，3 。从此出发，可以用建立数字和符号串之间的对应 。用一个例子来说明：看一个最简单的公式，假如给定的编码是，这个公式的六个字符分别对应数字1 2 3 4 3 5，则整个公式对应的哥德尔数为，将这个数记为n 。即，将素数从小到大排好，在它们上面按顺序写出符号对应的哥德尔数 。类似地，也是一个哥德尔数，它对应的字符串是，当然，这并不是一个合法的公式，仅仅是随意排列的字符串而已 。根据算数基本定理，一个合数可唯一的分解为这种素数^指数的乘积，这保证了不同的公式对应了不同的哥德尔数 。而元定理“ 的首字符为 ”就能通过它的哥德尔数n的某些算术性质来表示 。显然，如果能说明n的哥德尔数可被分解为 这种因式，就能说明 的首字符为 了 。即，要说明n能被2^1整除，但不能被2^2整除 。即，要说明：存在一个数a，使得2a=n；但不存在一个数b，使得4b=n 。而这就是一个纯粹的算术命题了 。这是一个直观的例子，展示了如何建立算术和PM系统的元层面之间的关系 。一个推导就是公式组成的序列，它也可以被一个哥德尔数表示，表示的方法是：如果这一推导中的公式对应的哥德尔数分别为a,b,c... 那这个推导本身就对应着哥德尔数，这个很大很大的数记为x 。这个推导有个最终的结论公式，假设这个结论的哥德尔数是z，那么显然，x和z之间会存在一些算术上的关系（如x^2+4=z，当然要比这种复杂得多）这个关系我们记为prove(x, z)（意为x对应的序列证明了z对应的公式） 。prove(x, z)表示x是z的证明，因此，“存在x，prove(x, z)” 就表示“数z对应的那个命题（在PM系统内）可证” 。这样，我们就把“可证性”这个元层面的性质也用算术表达出来了 。当然，可证性对应的算术性质是非常非常复杂的，但理解起来并不难 。同样的，不可证性就也表示出来了——“不存在x，prove(x, z)” 。简便起见，把z的可证性表示为“provable(z)”，z的不可证性为unprovable(z) 。z取不同的数，对应着不同的真假 。如对于上述 的哥德尔数n，provable(n)就是假的，因为系统推不出n对应的这一公式 。由于provable是一个算术性质，因此可以被PM系统所表达 。（被PM系统所表达，意为存在一个公式对应着这个性质，这不意味着PM能推出这个公式 。）这个表达可能很复杂，但我们并不需要考虑这个表达的内部结构，只要抽象地表示为PROVABLE就行了 。即，provable(z)这个算术层面的性质，可以找到一个系统中的很复杂的公式相对应，这个公式简记为PROVABLE(Z) 。对应地，unprovable(z)对应的系统内公式记为UNPROVABLE(Z) 。但是，注意到z是一个哥德尔数，它对应着一个公式 。