在数理逻辑中，哥德尔不完备定理是库尔特·哥德尔于1930年证明并发表的两条定理。简单地说，第一条定理指出：任何一个相容的数学形式化理论中，只要它强到足以蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题。这条定理是在数学界以外最著名的定理之一，也是误解最多的定理之一。形式逻辑中有一条定理也同样容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上是错误的。稍后我们可以看到一些对哥德尔定理的误解。把第一条定理的证明过程在体系内部形式化后，哥德尔证明了他的第二条定理。该定理指出：任何相容的形式体系不能用于证明它本身的相容性。这个结果破坏了数学中一个称为希尔伯特计划的哲学企图。大卫·希尔伯特(David Hilbert)提出，像实分析那样较为复杂的体系的相容性，可以用较为简单的体系中的手段来证明。最终，全部数学的相容性可以归结为基本算术的相容性。但哥德尔的第二条定理证明了基本算术的相容性不能在自身内部证明，因此当然就不能用来证明比它更强的系统的相容性了。

哥德尔不完备定理的意义哥德尔定理是一阶逻辑的定理，故最终只能在这个框架内理解。在形式逻辑中，数学命题及其证明都是用一种符号语言描述的，在这里我们可以机械地检查每个证明的合法性，于是便可以从一组公理开始无可辩驳地证明一条定理。理论上，这样的证明可以在电脑上检查，事实上这样的合法性检查程序也已经有了。为了这个过程得以进行，我们需要知道手头有什么样的公理。我们可以从一组有限的公理集开始，例如欧几里德几何。或者更一般地，我们可以允许无穷的公理列表，只要能机械地判断给定的命题是否一条公理就行。在计算机科学里面，这被称为公理的递归集。尽管无穷的公理列表听起来有些奇怪，实际上自然数的的通常理论中，称为皮亚诺公理的就是这么一样东西。哥德尔的第一条不完备定理表明任何一个允许定义自然数的体系必定是不完全的：它包含了既不能证明为真也不能证明为假的命题。存在不完备的体系这一事实本身并不使人感到特别惊讶。例如，在欧几里德几何中，如果把平行公设去掉，就得到一个不完备的体系。不完备的体系可能只意味着尚未找出所有必须的公理而已。但哥德尔揭示的是在多数情况下，例如在数论或者实分析中，你永远不能找出公理的完整集合。每一次你将一个命题作为公理加入，将总有另一个命题出现在你的研究范围之外。你可以加入无穷条公理（例如，所有真命题）到公理列表中，但你得到的公理列表将不再是递归集。给出任意一条命题，将没有机械的方法判定它是否是系统的一条公理。如果给出一个证明，一般来说也无法检查它是否正确。在计算机科学的语言中，哥德尔定理有另一种表述方式。在一阶逻辑中，定理是递归可枚举的：你可以编写一个可以枚举出其所有合法证明的程序。你可以问是否可以将结论加强为递归的：你可以编写一个在有限时间内判定命题真假的程序吗？根据哥德尔定理，答案是一般来说不能。

不确定命题的例子哥德尔和保尔·科恩得出的一些结果结合起来给出了不确定命题（既不能证明也不能否证的命题）的一个实际例子：选择公理和连续统假设都是集合论的标准公理系统内的不确定命题。在1973年，同调代数中的怀特海问题被证明是集合论中的不确定命题。1977年，Paris和Harrington证明了组合论中的一个命题，拉姆赛理论的某个版本，在皮阿诺公理给出的算术公理系统中是不确定的，但可以在集合论的一个更大体系中证明为真。在计算机科学中用到的Kruskal的树问题，也是在皮亚诺公理中不确定而在集合论中可证明的。Goodstein定理是一个关于自然数的相对简单的命题，它在皮亚诺算术中是不确定的。Gregory Chaitin在算法信息论中构造了一个不确定命题, 即``Chaitin 随机数Ω的第n个字节是否为0"这样的命题在ZFC内是不可判定的.

对哥德尔定理的一些进一步解释由于哥德尔的第一条定理有不少误解。我们举出一些例子：该定理并不意味着任何有趣的公理系统都是不完备的。例如，欧几里德几何可以被公理化为一个完备的系统。（事实上，欧几里德的原创公理集已经非常接近于完备的系统。所缺少的公理是非常直观的，以至于直到出现了形式化证明之后才注意到需要它们） 该定理需假设公理系统可以定义自然数。但是并非所有系统都能定义自然数。例如，塔斯基(Tarski)证明了实数和复数理论都是完备的公理化系统。 这理论用在人工智慧上，则指出有些道理可能是我们能够判别，但机器单纯用一阶逻辑断却无法得知的道理。不过机器可以用非一阶逻辑的逻辑系统。

第一不完备定理的证明要点要充实对证明要点的描述，主要的问题在于：为了构造相当于“p是不可证明的”这样的命题p，p就必须包含有自身的引用，而这很容易陷入无穷循环。将要介绍的哥德尔巧妙的把戏，后来被艾伦·图灵用于解决可判定性问题。开始的时候，每个公式或者说可形式化的命题都被我们的系统赋予一个唯一的数，称为哥德尔数。这要通过一种可以方便地在哥德尔数和公式之间（机械地）来回转换的方式来完成。因为系统足以表述“数”的概念，因此也就足以表述公式的概念了。象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就可以在系统内证明。这一矛盾说明系统是不相容的。

我发现今天吧里好几篇抽象理论研究的文章...晕了

汗……我要发克莱因瓶讲四维空间……

晕了晕了...看了一半实在看不懂了......卖火枪的，我想看看你咋讲思维口牙~~