哥德尔的不完备定理-杂记
在数理逻辑中，哥德尔不完备定理是库尔特·哥德尔于1931年证明并发表的两条定理。第一条定理指出：
任何自洽的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的真命题，因此通过推理演绎不能得到所有真命题（即体系是不完备的）。
这是形式逻辑中的定理，容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上并不是。具体实例见对哥德尔定理的误解。
把第一条定理的证明过程在体系内部形式化后，哥德尔证明了第二条定理。该定理指出：
任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性。
哥德尔不完备定理破坏了希尔伯特计划的哲学企图。大卫·希尔伯特提出，像实分析那样较为复杂的体系的兼容性，可以用较为简单的体系中的手段来证明。最终，全部数学的兼容性都可以归结为基本算术的兼容性。但哥德尔的第二条定理证明了基本算术的兼容性不能在自身内部证明，因此当然就不能用来证明比它更强的系统的兼容性了。
通俗来讲，哥德尔不完备定理表明每个数学系统都存在一些语句永远无法被证明。
一般数学上的形式系统都有三种特性
- 完备性
- 一致性
- 有效公理化
不完备性的结论影响了数学哲学以及形式化主义（使用形式符号描述原理）中的一些观点。第一定理可以被解释为：“不存在一个万能的公理系统，使得其既能够证明一切数学真理，又能证伪任何谬误。” 以下对第二定理的另一种说法甚至更令人不安：
如果一个（强度足以证明基本算术公理的）公理系统可以用来证明它自身的兼容性，那么它是不兼容的。
于是，为了确立系统S的兼容性，就要构建另一个系统T，但是T中的证明并不是完全可信的，除非不使用S就能确立T的兼容性。举个例子，自然数上的皮亚诺公理的兼容性可以在集合论中证明，但不能单独在自然数理论范围内证明。这对大卫·希尔伯特的著名的未解决的23个数学问题中的第二个给出了一个否定回答。
理论上，哥德尔理论仍留下了一线希望：也许可以给出一个算法判定一个给定的命题是否是不确定的，让数学家可以忽略掉这些不确定的命题。然而，对可判定性问题的否定回答表明不存在这样的算法。
值得注意的是，符合哥德尔不完备定理的系统，必须要蕴涵皮亚诺算术公理以承载对第一不完备定理证明过程的编码。基本上，这就要求系统能将一些基本操作例如加法和乘法形式化，例如在鲁宾逊算术Q中那样。有一些更弱的公理系统是兼容而且完备的，例如Presburger算术，它包括所有的一阶逻辑的真命题和关于加法的真命题。
公理系统可能含有无穷条公理（例如皮亚诺算术就是这样），但要哥德尔定理生效，必须存在检验证明是否正确的有效算法。例如，可以将关于自然数的所有在标准模型中为真的一阶语句组成一个集合。这个公理系统是完备的；哥德尔定理之所以无效，是因为不存在决定任何一条语句是否正确的有效算法。从另一方面说，这个算法的不存在正是哥德尔定理的直接结果。
另一个哥德尔定理不适用的特殊情况是：将关于自然数的所有语句首先按长度然后按字典顺序排序，并从皮亚诺公理集开始，一个一个遍历列表，如果发现一条语句既不能证明又不能否证，就将它作为公理加入。这样得到的系统是完备的，兼容的，并且是足够强大的，但不是递归可枚举的。
哥德尔本人只证明了以上定理的一个较弱版本；以上定理的第一个证明是罗素（Russel）于1936年给出的。
基本上，第一定理的证明是通过在形式公理系统中构造如下命题
𝑝 = “此命题是不可证明的”
来完成的。这样，它可以看成是说谎者悖论的一个现代变种。
如果公理系统是兼容的，哥德尔证明了𝑝（及其否定）不能在系统内证明。因此p是真命题（p声称它不可证明，而它确实不能），尽管其证明不能在系统内形式化。请注意将𝑝作为公理加入系统并不能解决问题：扩大了的系统中会有另一个哥德尔语句出现。
罗杰·彭罗斯声称“可被机械地证明的”和“对人类来说看起来是真的”的这一区别，表明了人类智能在本质上不同于机械过程。这一观点未被普遍接受，因为正如马文·闵斯基所指出的，人类智能有犯错误和理解不兼容和谬误句子的能力。但马文·闵斯基透露说库尔特·哥德尔私下告诉他，他相信人类有一种到达真理的直觉方法，但因为跟计算机式的方法不同，人类可以知道为真的事情并不受他的定理限制。[2]
对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点，也可以作如下评论：p无法被证明，也无法被证伪，因为无法知道系统是否是兼容的。因此实际上我们并不知道系统之外的任何真理。我们所确知的只有这样一个命题：
要么𝑝在系统内部无法证明，要么该系统是不兼容的。
