章节出错了,点此刷新,刷新后小编会在两分钟内校正章节内容,请稍后再试。
哥德尔不完备定理
哥德尔的不完备性定理是数理逻辑的两个定理，它们与形式公理化理论中可证明性的限制有关。这些结果由KurtGödel于1931年发表，在数理逻辑和数学哲学中都很重要。这些定理被广泛但不普遍地解释为表明希尔伯特的程序为所有数学找到一套完整且一致的公理是不可能的。
第一个不完备性定理指出，没有任何一致的公理系统能够通过有效的程序（即算法）列出其定理，从而能够证明有关自然数算术的所有真理。对于任何这种一致的形式系统，总会有关于自然数的陈述是真实的，但在系统内是无法证明的。第二个不完备性定理是第一个定理的扩展，表明系统不能证明其自身的一致性。
使用对角线论证，哥德尔的不完备性定理是关于形式系统局限性的几个密切相关的定理中的第一个。紧随其后的是Tarski关于真理的形式不可定义性的不可定义性定理，Church证明希尔伯特的Entscheidungsproblem是不可解决的，以及图灵的关于没有算法可以解决停机问题的定理。
形式系统：完整性、一致性和有效公理化
不完备性定理适用于具有足够複杂性来表达自然数的基本算术并且是一致且有效公理化的形式系统。特别是在一阶逻辑的上下文中，形式系统也被称为形式理论。一般而言，形式系统是一种演绎装置，由一组特定的公理以及允许从公理推导新定理的符号操作规则（或推理规则）组成。这种系统的一个例子是一阶皮亚诺算术，这是一个所有变量都旨在表示自然数的系统。在其他系统中，例如集合论，只有形式系统的一些句子表达了关于自然数的陈述。不完备性定理是关于这些系统内的形式可证明性，而不是关于非正式意义上的“可证明性”。
形式系统可能具有几个属性，包括完整性、一致性和有效公理化的存在。不完备性定理表明，包含足够数量的算术的系统不能拥有所有这三个属性。
有效公理化
如果正式系统的定理集是递归可枚举集，则称其为有效公理化（也称为有效生成）（Franzén2005,p.112）.
这意味着有一个计算机程序原则上可以枚举系统的所有定理，而不列出任何不是定理的陈述。有效生成的理论示例包括Peano算术和Zermelo-Fraenkel集合论(ZFC)。
被称为真算术的理论由皮亚诺算术语言中关于标准整数的所有真实陈述组成。这个理论是一致的和完整的，并且包含了足够数量的算术。然而，它没有一组可递归枚举的公理，因此不满足不完备性定理的假设。
完整性
如果对于公理语言中的任何陈述，该陈述或其否定可以从公理中证明，则一组公理是（句法上或否定-）完整的（Smith2007,p.24）.这是与哥德尔第一个不完备定理相关的概念。不要与语义完整性混淆，这意味着公理集证明了给定语言的所有语义重言式。在他的完备性定理中（不要与这裡描述的不完备性定理混淆），哥德尔证明一阶逻辑在语义上是完备的。但它在句法上并不完整，因为有些句子可以用一阶逻辑的语言表达，而单靠逻辑公理既不能证明也不能证伪。
在数学系统中，像希尔伯特这样的思想家认为，找到这样一种公理化方法只是时间问题，它允许人们证明或反驳（通过证明其否定性）每一个数学公式。
一个正式的系统在设计上可能在句法上是不完整的，就像逻辑一般。或者它可能是不完整的，因为没有发现或包含所有必要的公理。例如，没有平行公设的欧几里得几何是不完整的，因为语言中的某些陈述（例如平行公设本身）无法从剩馀的公理中证明。类似地，稠密线性阶的理论并不完整，而是通过一个额外的公理说明阶中没有端点而变得完整。连续统假设是ZFC语言中的一个陈述这在ZFC中无法证明，因此ZFC不完整。在这种情况下，没有明显的候选新公理可以解决问题。
一阶皮亚诺算术理论似乎是一致的。假设情况确实如此，请注意它具有无限但可递归枚举的公理集，并且可以为不完备定理的假设编码足够的算术。因此，根据第一不完备定理，皮亚诺算术是不完备的。该定理给出了一个算术陈述的明确示例，该陈述在皮亚诺的算术中既不可证明也不可证伪。而且，这种说法在通常的模型中是正确的。此外，Peano算术的有效公理化、一致扩展是不完整的。
一致性
如果没有陈述使得陈述及其否定都可以从公理证明，则一组公理（简单地）是一致的，否则不一致。也就是说，一个一致的公理系统是一个没有矛盾的系统。
Peano算术在ZFC中可证明是一致的，但不是在其内部。类似地，ZFC本身不能证明是一致的，但是ZFC+“存在一个不可访问的基数”证明了ZFC是一致的，因为如果κ是最小的这样的基数，那麽位于冯诺依曼宇宙中的Vκ是ZFC的模型，并且一个理论是一致的当且仅当它有一个模型。
如果将皮亚诺算术语言中的所有语句都视为公理，那麽这个理论是完整的，具有一组可递归枚举的公理，并且可以描述加法和乘法。但是，它并不一致。
不一致理论的其他例子来自于在集合论中假设无限制理解的公理模式时产生的悖论。
包含算术的系统
不完备性定理仅适用于能够证明关于自然数的足够事实集合的形式系统。一个足够的集合是罗宾逊算术Q的一组定理。一些系统，例如皮亚诺算术，可以直接表达关于自然数的陈述。其他的，例如ZFC集合论，能够将关于自然数的陈述解释成他们的语言。这些选项中的任何一个都适用于不完备性定理。
给定特徵的代数闭域理论是完整的、一致的，并且具有无限但可递归枚举的公理集。然而，不可能将整数编码到这个理论中，并且该理论不能描述整数的算术。一个类似的例子是实封闭场理论，它本质上等同于欧几里得几何的塔斯基公理。所以欧几里得几何本身（在塔斯基的公式中）是一个完整的、一致的、有效的公理化理论的例子。
Presburger算术系统由一组自然数的公理组成，只有加法运算（省略了乘法运算）。Presburger算术是完整的、一致的和递归可枚举的，并且可以编码自然数的加法但不能编码乘法，这表明对于哥德尔定理，需要该理论不仅可以编码加法，还可以编码乘法。
DanWillard(2001)研究了一些算术系统的弱族，这些系统允许足够的算术作为关係来形式化哥德尔编号，但不足以将乘法作为函数，因此无法证明第二不完备性定理；也就是说，这些系统是一致的，并且能够证明自己的一致性（参见自我验证理论）。
相互冲突的目标
在选择一组公理时，一个目标是能够证明尽可能多的正确结果，而不会证明任何不正确的结果。例如，我们可以想像一组真实的公理，它们允许我们证明关于自然数的每一个真实的算术声明（Smith2007，p.2）.在标准的一阶逻辑系统中，一组不一致的公理将证明其语言中的每一个陈述（这有时被称为爆炸原理），因此是自动完成的。然而，一组既完整又一致的公理证明了一组最大的非矛盾定理（Hinman2005,p.143）.
前面几节用Peano算术、ZFC和ZFC+“存在不可访问的基数”说明的模式通常不能被打破。这裡ZFC+“存在一个不可访问的基数”不能从自身证明是一致的。它也不完整，正如ZFC+“存在一个不可接近的基数”理论中未解决的连续统假设所示。
第一个不完备性定理表明，在可以表达基本算术的形式系统中，永远不可能创建一个完整且一致的有限公理列表：每次添加一个额外的、一致的陈述作为一个公理，还有其他真实陈述仍然不能被证明，即使使用新公理。如果添加了使系统完整的公理，那麽这样做的代价是使系统不一致。无限的公理列表甚至不可能是完整的、一致的和有效的公理化。
第一不完备定理
哥德尔的第一个不完备性定理首先作为“定理VI”出现在哥德尔1931年的论文“OnFormallyUndecidablePropositionsofPrincipiaMathematicaandRelatedSystemsI”中。此后不久，J.BarkleyRosser(1936)使用Rosser的技巧改进了该定理的假设。由此产生的定理（结合罗瑟的改进）可以用英语解释如下，其中“形式系统”包括系统有效生成的假设。
第一个不完备性定理：“任何可以在其中进行一定数量的基本算术的一致的形式系统F都是不完备的；即，存在F语言的陈述，在F中既不能证明也不能证伪。”（拉蒂凯宁2015）
该定理所指的不可证明的陈述GF通常被称为系统F的“哥德尔句子”。该证明为系统F构造了一个特定的Gödel句子，但係统语言中有无限多的陈述具有相同的属性，例如Gödel句子和任何逻辑有效句子的合取。
每个有效生成的系统都有自己的哥德尔语句。可以定义一个更大的系统F'，它包含整个F加上GF作为附加公理。这不会导致一个完整的系统，因为哥德尔定理也适用于F'，因此F'也不能是完整的。在这种情况下，GF确实是F'中的一个定理，因为它是一个公理。因为GF只声明它在F中不可证明，所以它在F'中的可证明性并不存在矛盾。然而，因为不完备性定理适用于F'，对于F'会有一个新的哥德尔陈述GF'，表明F'也是不完全的。GF'与GF的不同之处在于GF'指的是F'，而不是F。
哥德尔句的句法形式
哥德尔句子旨在间接地指代它自己。该句子指出，当使用特定的步骤序列来构造另一个句子时，该构造的句子将无法在F中证明。然而，步骤的顺序使得构造的句子原来是GF本身。这样，哥德尔句子GF间接地说明了它在F内的不可证明性(Smith2007,p.135).
为了证明第一个不完备性定理，哥德尔证明了系统内可证明性的概念可以纯粹用对系统的哥德尔句子数进行运算的算术函数来表达。因此，可以证明有关数字的某些事实的系统也可以间接证明有关其自身陈述的事实，前提是它是有效生成的。关于系统内陈述的可证明性的问题被表示为关于数字本身的算术性质的问题，如果它是完整的，它将由系统决定。
因此，虽然哥德尔句子间接地指代系统F的句子，但当作为算术语句阅读时，哥德尔句子直接指代自然数。它断言没有自然数具有特定属性，该属性由原始递归关係给出（Smith2007,p.141）.因此，哥德尔句子可以用算术语言以简单的句法形式编写。特别是，它可以表示为算术语言中的一个公式，该公式由许多领先的全称量词后跟一个无量词体组成（这些公式在水平Π10算术层次结构）。通过MRDP定理，哥德尔语句可以重写为一个声明，即当用整数代替其变量时，许多具有整数係数的变量中的特定多项式永远不会取零值(Franzén2005,p.71).
哥德尔句子的真相
第一个不完备性定理表明，适当形式理论F的哥德尔句子GF在F中是不可证明的。因为，当解释为关于算术的陈述时，这种不可证明性正是该句子（间接）断言的内容，所以哥德尔句子实际上是正确的（Smoryński1977,p.825;另见Franzén2005，第28-33页）。出于这个原因，句子GF通常被称为“真实但不可证明”。（拉蒂凯宁2015年）.然而，由于哥德尔语句本身不能正式指定其预期的解释，因此GF语句的真实性只能通过系统外部的元分析得出。一般来说，这种元分析可以在称为原始递归算术的弱形式系统中进行，这证明了蕴涵Con(F)→GF，其中Con(F)是断言F一致性的规范句子(Smoryński1977年，第840页,菊池&田中1994年,p.403）。
儘管一致理论的哥德尔语句作为关于算术的预期解释的陈述是正确的，但由于哥德尔的完备性定理，哥德尔语句在一些非标准算术模型中将是错误的(Franzén2005,p.135).该定理表明，当一个句子独立于一个理论时，该理论将具有句子为真的模型和句子为假的模型。如前所述，系统F的哥德尔语句是一个算术语句，它声称不存在具有特定属性的数。不完备性定理表明，这一主张将独立于系统F，并且哥德尔句子的真实性源于没有标准自然数具有所讨论的性质这一事实。任何哥德尔语句为假的模型都必须包含一些满足该模型内属性的元素。这样的模型必须是“非标准的”——它必须包含不符合任何标准自然数的元素（Raatikainen2015,弗兰岑2005年，第。135）。
与说谎者悖论的关係
哥德尔在“论数学原理和相关係统中的形式上不可判定的命题I”的介绍部分特别引用了理查德的悖论和说谎者悖论作为他的句法不完整结果的语义类似物。骗子悖论是“这句话是假的”这句话。对撒谎者句子的分析表明，它不可能是真的（因为它断言，它是假的），也不能是假的（因为它是真的）。系统F的哥德尔句子G与说谎者句子类似，但用可证明性代替了真值：G说“G在系统F中是不可证明的.”G的真值和可证明性分析是对说谎者句子真值分析的形式化版本。
在哥德尔句子中不能用“假”代替“不可证明”，因为谓词“Q是假公式的哥德尔数”不能表示为算术公式。这一结果被称为塔斯基不可定义定理，由哥德尔在证明不完备性定理时和该定理的同名阿尔弗雷德·塔斯基独立发现。
哥德尔原始结果的扩展
与哥德尔1931年论文中陈述的定理相比，许多当代关于不完备性定理的陈述在两个方面更为普遍。这些概括的陈述被表述为适用于更广泛的系统类别，并且它们被表述为包含较弱的一致性假设。
哥德尔证明了数学原理系统的不完备性，这是一个特殊的算术系统，但是对于任何具有某种表达能力的有效系统，都可以给出平行的证明。哥德尔在他论文的引言中评论了这一事实，但为了具体性，将证明限制在一个系统上。在该定理的现代陈述中，通常将有效性和表达性条件陈述为不完备性定理的假设，因此它不限于任何特定的形式系统。1931年哥德尔发表他的研究结果时，用于说明这些条件的术语尚未开发。
哥德尔不完备定理的原始陈述和证明需要假设系统不仅是一致的，而且是ω-一致的。一个系统是ω-一致的，如果它不是ω-不一致的，并且是ω-不一致的，如果有一个谓词P使得对于每个特定的自然数m系统证明~P(m)，但係统也证明有存在一个自然数n使得P(n)。也就是说，系统说具有属性P的数存在，同时否认它有任何特定的价值。一个系统的ω-一致性意味着它的一致性，但一致性并不意味着ω-一致性。J.BarkleyRosser(1936)通过找到证明的变体(Rosser'strick)只要求系统是一致的，而不是ω-一致的。这主要是出于技术上的兴趣，因为所有真正的算术形式理论（其公理都是关于自然数的真实陈述的理论）都是ω一致的，因此最初陈述的哥德尔定理适用于它们。仅假设一致性而不是ω-一致性的不完全性定理的更强版本现在通常称为哥德尔不完全性定理和Gödel-Rosser定理。
第二不完备定理
对于每个包含基本算术的形式系统F，可以规范地定义一个公式Cons(F)来表示F的一致性。这个公式表达了“在系统F中不存在一个自然数编码其结论是句法矛盾的形式推导”的性质。句法矛盾通常被认为是“0=1”，在这种情况下，Cons(F)声明“没有自然数编码从F的公理推导'0=1'”。
哥德尔的第二个不完备定理表明，在一般假设下，这个规范一致性陈述Cons(F)在F中是不可证明的。该定理首先作为“定理XI”出现在哥德尔1931年的论文“OnFormallyUndecidablePropositionsinPrincipiaMathematicaandRelatedSystemsI”中。在以下陈述中，术语“形式化系统”还包括F被有效公理化的假设。
第二个不完备性定理：“假设F是一个包含初等算术的一致形式化系统。那麽F⊬Cons(F).”（拉蒂凯宁2015年）
该定理比不完备性第一定理强，因为第一不完备性定理构造的陈述不直接表达系统的一致性。第二不完备定理的证明是通过在系统F本身内形式化第一不完备定理的证明来获得的。
表达一致性
关于将F的一致性表示为F语言中的公式的方法，第二不完备性定理有一个技术上的微妙之处。表示系统一致性的方法有很多种，但并非所有方法都导致相同的结果。第二个不完备定理的公式Cons(F)是一致性的特殊表达。
F是一致的主张的其他形式化可能在F中是不等价的，有些甚至可能是可证明的。例如，一阶Peano算术（PA）可以证明“PA的最大一致子集”是一致的。但是，因为PA是一致的，所以PA的最大一致子集只是PA，所以从这个意义上说，PA“证明了它是一致的”。PA没有证明的是，PA的最大一致子集实际上是整个PA。（术语“PA的最大一致子集”在这裡是指在某些特定有效枚举下PA公理的最大一致初始部分。）
希尔伯特-伯奈斯条件
第二个不完备定理的标准证明假定可证明谓词ProvA(P)满足Hilbert-Bernays可证明条件。让#(P)表示公式P的哥德尔数，可证明性条件说：
如果F证明P，则F证明ProvA(#(P))。
F证明1。也就是说，F证明ProvA(#(P))→ProvA(#(ProvA(#(P))))。
F证明ProvA(#(P→Q))∧ProvA(#(P))→ProvA(#(Q))
有些系统，例如Robinson算术，足以满足第一不完备性定理的假设，但不能证明Hilbert-Bernays条件。然而，皮亚诺算术足以验证这些条件，所有理论都比皮亚诺算术更强大。
一致性证明的含义
哥德尔的第二不完备性定理还暗示满足上述技术条件的系统F1不能证明任何证明F1一致性的系统F2的一致性。这是因为这样的系统F1可以证明，如果F2证明了F1的一致性，那麽F1实际上是一致的。对于F1是一致的主张具有形式“对于所有数字n，n具有不是F中矛盾证明的代码的可判定属性1”。如果F1实际上是不一致的，那麽F2将证明一些n是F1中矛盾的代码。但是如果F2也证明了F1是一致的（即，不存在这样的n)，那麽它本身就是不一致的。这个推理可以在F1中形式化，以表明如果F2是一致的，那麽F1是一致的。因为，根据第二不完备性定理，F1不能证明它的一致性，也不能证明F2的一致性。
第二个不完备定理的这个推论表明，例如，没有希望证明Peano算术的一致性，例如，使用可以在一个系统中形式化的任何有限方法来证明Peano算术的一致性，该系统的一致性可以在Peano算术(PA)中证明。例如，被广泛接受为有限数学的精确形式化的原始递归算术系统（PRA）在PA中可证明是一致的。因此PRA不能证明PA的一致性。这一事实通常被认为暗示了希尔伯特的计划，其目的是通过给出理想原则一致的有限证明来证明在“真实”（有限）数学陈述的证明中使用“理想”（无限）数学原理是合理的，弗兰岑2005年，第106).
推论还表明了第二个不完备性定理的认识论相关性。如果系统F证明了它的一致性，它实际上不会提供任何有趣的信息。这是因为不一致的理论证明了一切，包括它们的一致性。因此，F在F中的一致性证明不会给我们关于F是否真的是一致的任何线索；毫无疑问，关于F的一致性的任何疑问都可以通过这样的一致性证明来解决。一致性证明的兴趣在于证明系统F在某个系统F'中的一致性的可能性，该系统在某种意义上比F更容易怀疑本身，例如弱于F。对于许多自然发生的理论F和F'，例如F=Zermelo-Fraenkel集合论和F'=原始递归算术，F'的一致性在F中是可证明的，因此F'不能通过上述证明F的一致性第二不完备性定理的推论。
第二个不完备性定理并没有完全排除证明某个理论T的一致性的可能性，只是在T本身可以证明是一致的理论中这样做。例如，GerhardGentzen在不同的系统中证明了Peano算术的一致性，该系统包括一个公理断言称为ε0的序数是有根据的；参见Gentzen的一致性证明。Gentzen定理促进了证明论中序数分析的发展。
不可判定陈述的例子
在数学和计算机科学中，“不可判定”这个词有两种不同的含义。其中第一个是与哥德尔定理相关的证明理论意义，即在特定的演绎系统中，陈述既不可证明也不可反驳。此处不讨论的第二种意义与可计算性理论有关，它不适用于陈述，而是适用于决策问题，决策问题是可数的无限组问题，每个问题都需要一个是或否的答案。如果没有可计算的函数可以正确回答问题集中的每个问题（请参阅undecidablequestion），则称此类问题是不可判定的。
由于undecidable一词有两种含义，因此有时使用术语独立而不是undecidable来表示“既不可证明也不可反驳”的含义。
在特定演绎系统中，陈述的不可判定性本身并不能解决陈述的真值是否被明确定义或是否可以通过其他方式确定的问题。不可判定性仅意味着所考虑的特定演绎系统不能证明陈述的真假。是否存在所谓的“绝对不可判定”的陈述，其真值永远不知道或不明确，这是数学哲学中的一个争议点。
哥德尔和保罗科恩的联合工作给出了两个不可判定陈述的具体例子（在术语的第一个意义上）：连续统假设在ZFC（集合论的标准公理化）中既不能证明也不能反驳，选择在ZF中既不能被证明也不能被反驳（这是除了选择公理之外的所有ZFC公理）。这些结果不需要不完备性定理。哥德尔在1940年证明，这些陈述都不能在ZF或ZFC集合论中被证伪。在1960年代，科恩证明了两者都不能从ZF证明，而连续统假设也不能从ZFC证明。
1973年，SaharonShelah表明，群论中的怀特黑德问题在标准集理论中是不可判定的。[1]
GregoryChaitin在算法信息论中产生了不可判定的陈述，并在这种情况下证明了另一个不完备性定理。Chaitin的不完备性定理指出，对于任何可以表示足够算术的系统，都有一个上限c使得在该系统中无法证明特定数字的Kolmogorov複杂度大于c。哥德尔定理与说谎者悖论有关，而柴廷的结果与贝里悖论有关。
在更大的系统中可证明的不可判定的陈述
这些是哥德尔“真实但不可判定”句子的自然数学等价物。它们可以在一个更大的系统中得到证明，该系统通常被认为是一种有效的推理形式，但在诸如皮亚诺算术之类的更有限的系统中是不可判定的。
1977年，Paris和Harrington证明了Paris-Harrington原理，即无限Ramsey定理的一个版本，在（一阶）Peano算术中是不可判定的，但可以在更强的二阶算术系统中证明。柯比和帕里斯后来证明，古德斯坦定理是关于自然数序列的陈述，比帕里斯-哈灵顿原理稍微简单一些，在皮亚诺算术中也是不可判定的。
Kruskal的树定理在计算机科学中有应用，它也无法从Peano算术中确定，但在集合论中可以证明。事实上，克鲁斯卡尔的树定理（或其有限形式）在一个更强大的系统中是不可判定的，该系统编纂了基于称为谓词主义的数学哲学可接受的原则。相关但更一般的图小定理（2003）对计算複杂性理论有影响。
与可计算性的关係
不完备性定理与递归论中关于不可判定集的若干结果密切相关。
StephenColeKleene(1943)使用可计算性理论的基本结果证明了哥德尔的不完备性定理。一个这样的结果表明，停止问题是不可判定的：在给定任何程序P作为输入的情况下，没有计算机程序可以正确确定P在以特定给定输入运行时最终是否停止。Kleene表明，具有某些一致性属性的完整有效算术系统的存在将迫使停机问题是可判定的，这是一个矛盾。Shoenfield(1967,p.132)也提出了这种证明方法;查尔斯沃思(1980);和Hopcroft&Ullman(1979).
弗兰岑（2005年，第73页）解释瞭如何使用Matiyasevich对希尔伯特第10个问题的解决方案来获得对哥德尔第一不完备定理的证明。Matiyasevich证明了没有算法可以在给定具有整数係数的多元多项式p(x1,x2,...,xk)的情况下确定方程p=0是否存在整数解。因为具有整数的多项式如果多元整数多项式方程p=0确实有整数解，那麽任何足够强的算术系统T都可以证明这一点。此外，如果系统T是ω-一致的，那麽它永远不会证明一个特定的多项式方程有一个解，而实际上整数中没有解。因此，如果T是完全的且ω一致的，则可以通过仅枚举T的证明，直到找到“p有解”或“p没有解”，在算法上确定多项式方程是否有解，在与Matiyasevich定理相矛盾。因此，T不能是w-一致和完整。此外，对于每个一致的有效生成系统T，可以有效地生成一个多元多项式p在整数上，使得方程p=0在整数上没有解，但在T中无法证明缺乏解（Davis2006,第416页;琼斯1980）。
斯莫林斯基（1977年，第842页）展示瞭如何使用递归不可分集的存在来证明第一个不完备性定理。这个证明经常被扩展以表明像Peano算术这样的系统本质上是不可判定的（参见Kleene1967,p.274）。
Chaitin的不完备性定理给出了一种基于Kolmogorov複杂性生成独立句子的不同方法。就像上面提到的Kleene提出的证明一样，柴廷定理只适用于具有附加性质的理论，即它们的所有公理在自然数的标准模型中都是真的。哥德尔不完备定理的特点在于它适用于一致的理论，但这些理论仍然包括标准模型中错误的陈述；这些理论被称为ω-inconsistent。
第一个定理的证明草图
反证法具有三个基本部分。首先，选择一个符合建议标准的正式系统：
系统中的语句可以用自然数（称为哥德尔数）表示。这样做的意义在于，陈述的性质——例如它们的真假——将等价于确定它们的哥德尔数是否具有某些性质，因此可以通过检查它们的哥德尔数来证明陈述的性质。这部分最终构建了一个公式，表达了“陈述S在系统中是可证明的”这一思想（它可以应用于系统中的任何陈述“S”）。
在正式系统中，可以构造一个数，其匹配语句在解释时是自引用的，并且本质上说它（即语句本身）是不可证明的。这是使用一种称为“对角化”的技术完成的（之所以如此称呼，是因为它起源于康托尔的对角线参数）。
在正式系统中，该陈述允许证明它在系统中既不可证明也不可证明，因此该系统实际上不可能是ω-一致的。因此，提议的系统符合标准的原始假设是错误的。
语法的算术化
充实上述证明的主要问题是，一开始似乎要构造一个等同于“p无法证明”的陈述p，p必须以某种方式包含对p的引用，这很容易导致无限倒退。哥德尔的巧妙技术是表明语句可以与数字匹配（通常称为语法的算术），这样“证明一个语句”可以替换为“测试一个数字是否具有给定的属性”。这允许以一种避免任何无限回归定义的方式构建自引用公式。同样的技术后来被艾伦·图灵在他关于Entscheidungsproblem的工作中。
简单来说，可以设计一种方法，使系统中可以表述的每个公式或语句都有一个唯一的数字，称为它的哥德尔数，这样就可以在公式和哥德尔之间机械地来迴转换数字。所涉及的数字可能确实很长（就位数而言），但这不是障碍；重要的是可以构建这样的数字。一个简单的例子是如何将英语存储为每个字母的数字序列，然后组合成一个更大的数字：
该单词在ASCIIhello中编码为104-101-108-108-111，可以转换为数字104101108108111。
逻辑语句用ASCIIx=y=>y=x编码为120-061-121-032-061-062-032-121-061-120，可以转换为数字120061121032061062032121061120。
原则上，证明一个陈述的真假可以被证明等同于证明与该陈述匹配的数字具有或不具有给定的属性。因为形式系统足够强大，可以支持对一般数字进行推理，它也可以支持对錶示公式和陈述的数字进行推理。至关重要的是，由于系统可以支持对数字属性的推理，因此结果等同于对其等价陈述的可证明性的推理。
构建关于“可证明性”的陈述
已经表明，原则上系统可以间接地做出关于可证明性的陈述，通过分析那些表示陈述的数字的属性，现在可以展示如何创建一个实际做到这一点的陈述。
仅包含一个自由变量x的公式F(x)称为语句形式或类符号。一旦x被一个特定的数字代替，陈述形式就变成了一个真实的陈述，然后它要么在系统中可证明，要么不可证明。对于某些公式，可以证明对于每个自然数n，F(n)当且仅当它可以被证明时才为真（原始证明中的精确要求较弱，但对于证明草图来说这就足够了）。特别是，对于有限数量的自然数之间的每个特定算术运算都是如此，例如“2×3=6”。
陈述形式本身不是陈述，因此不能被证明或证伪。但是每个陈述形式F(x)都可以分配一个Gödel数，用G(F)表示。以F(x)形式使用的自由变量的选择与哥德尔数G(F)的分配无关。
可证明性的概念本身也可以用哥德尔数编码，方式如下：因为证明是遵守某些规则的陈述的列表，所以可以定义证明的哥德尔数。现在，对于每个陈述p，人们可能会问一个数字x是否是其证明的哥德尔数。p和x的哥德尔数之间的关係，即其证明的潜在哥德尔数，是两个数之间的算术关係。因此，有一个语句形式Bew(y)使用这种算术关係来说明存在y证明的哥德尔数：
Bew(y)=∃x(y是公式的哥德尔数，x是由y编码的公式证明的哥德尔数)。
Bew这个名字是beweisbar的缩写，是德语中“可证明的”的意思；这个名字最初是哥德尔用来表示刚刚描述的可证明性公式的。请注意，“Bew(y)”只是一个缩写，表示T的原始语言中的一个特定的、非常长的公式；字符串“Bew”本身并未声称是该语言的一部分。
公式Bew(y)的一个重要特徵是，如果陈述p在系统中是可证明的，则Bew(G(p))也是可证明的。这是因为p的任何证明都会有一个对应的哥德尔数，它的存在会导致Bew(G(p))得到满足。
对角化
证明的下一步是获得一个陈述，该陈述间接地断言它自己的不可证明性。儘管哥德尔直接构造了这个陈述，但至少有一个这样的陈述的存在来自对角引理，它说对于任何足够强的形式系统和任何陈述形式F都有一个陈述p使得系统证明
p↔F(G(p))。
令F为Bew(x)的否定，我们得到定理
p↔~Bew(G(p))
而由此定义的p大致说明了它自己的哥德尔数是一个不可证公式的哥德尔数。
语句p并不等于~Bew(G(p))；相反，p表示如果执行某个计算，则生成的哥德尔数将是一个不可证明的陈述。但是当执行这个计算时，得到的哥德尔数原来是p本身的哥德尔数。这类似于英语中的以下句子：
"，当它自己在引号中时，是不可证明的。"，当它自己在引号中时，是不可证明的。
这句话不直接指代它自己，但是当进行陈述的变换时，得到原句作为结果，因此这句话间接地断言了它自己的不可证明性。对角引理的证明採用了类似的方法。
现在，假设公理系统是ω-consistent，设p为上一节中得到的陈述。
如果p是可证明的，那麽Bew(G(p))将是可证明的，如上所述。但是p断言Bew(G(p))的否定。因此，该系统将是不一致的，既证明了陈述又证明了它的否定。这个矛盾表明p是不可证明的。
如果p的否定是可证明的，那麽Bew(G(p))将是可证明的（因为p被构造为等价于Bew(G(p))的否定）。但是，对于每个特定数字x，x不能是p证明的哥德尔数，因为p是不可证明的（来自上一段）。因此，一方面系统证明存在一个具有特定性质的数（即它是p证明的哥德尔数），但另一方面，对于每个特定数x，我们可以证明它不具有这个性质。这在ω一致系统中是不可能的。因此p的否定是不可证明的。
因此，陈述p在我们的公理系统中是不可判定的：它在系统内既不能被证明也不能被证伪。
事实上，要证明p是不可证明的，只需要假设系统是一致的。需要更强的ω一致性假设来证明p的否定是不可证明的。因此，如果为特定係统构造p：
如果系统是ω-一致的，它既不能证明p也不能证明它的否定，所以p是不可判定的。
如果系统是一致的，它可能有相同的情况，或者它可能证明p的否定。在后一种情况下，我们有一个错误但可证明的陈述（“notp”），并且系统不是ω-一致的。
如果试图“添加缺失的公理”以避免系统的不完整性，那麽必须添加p或“非p”作为公理。但是随后陈述的“成为证明的哥德尔数”的定义发生了变化。这意味着公式Bew(x)现在不同了。因此，当我们将对角引理应用于这个新的Bew时，我们得到了一个新的陈述p，与之前的不同，如果它是ω-consistent，它将在新系统中是不可判定的。
通过Berry悖论证明
GeorgeBoolos(1989)勾勒出第一个不完备性定理的替代证明，该定理使用Berry悖论而不是骗子悖论来构造一个真实但无法证明的公式。SaulKripke独立发现了类似的证明方法(Boolos1998,p.383).Boolos的证明通过为任何可计算的真算术句子集合S构造另一个为真但不包含在S中的句子来进行。这给出了第一个不完备性定理作为推论。根据Boolos的说法，这个证明很有趣，因为它为有效的、一致的算术理论的不完整性提供了“不同的理由”（Boolos1998，第388页）.
计算机验证的证明
不完备性定理是少数非平凡定理之一，这些定理已转化为可以通过证明辅助软件完全验证的形式化定理。与大多数数学证明一样，哥德尔对不完备性定理的原始证明是用自然语言编写的，旨在供人类读者阅读。
NatarajanShankar于1986年使用Nqthm宣布了第一个不完备定理版本的计算机验证证明（Shankar1994）,由RussellO'Connor在2003年使用Coq(O'Connor2005)以及JohnHarrison在2009年使用HOLLight(Harrison2009).LawrencePaulson在2013年使用Isabelle宣布了两个不完备性定理的计算机验证证明（Paulson2014）.
第二定理的证明草图
证明第二个不完备性定理的主要困难是证明在证明第一个不完备性定理中使用的关于可证明性的各种事实可以在系统S内使用可证明性的形式谓词形式化。一旦这样做了，第二个不完备性定理就通过在系统S本身内形式化第一个不完备性定理的整个证明来实现。
令p代表上面构造的不可判定的句子，并假设为了获得一个矛盾，系统S的一致性可以从系统S本身中得到证明。这相当于证明“系统S是一致的”这一陈述。现在考虑语句c，其中c=“如果系统S是一致的，则p是不可证明的”。句子c的证明可以在系统S中形式化，因此陈述c，“p不可证明”，（或同样，“不是P(p)")可以在系统S中证明。
然后观察，如果我们可以证明系统S是一致的（即c的假设中的陈述），那麽我们已经证明p是不可证明的。但这是一个矛盾，因为根据第一不完全性定理，这个句子（即句子c中隐含的内容，““p”不可证明”）是我们构造为不可证明的。请注意，这就是为什麽我们需要形式化S中的第一个不完全性定理：为了证明第二个不完全性定理，我们得到与第一个不完全性定理的矛盾，这只能通过证明该定理在S中成立。所以我们不能证明系统S是一致的。第二个不完备性定理陈述如下。
讨论和影响
不完备性结果影响了数学哲学，特别是形式主义的版本，它们使用单一的形式逻辑系统来定义其原理。
逻辑主义的后果和希尔伯特的第二个问题
不完备性定理有时被认为会对GottlobFrege和BertrandRussell提出的逻辑主义纲领产生严重后果，该纲领旨在根据逻辑定义自然数（Hellman1981，第451-468页）.BobHale和CrispinWright认为这对逻辑主义来说不是问题，因为不完备性定理同样适用于一阶逻辑，就像它们适用于算术一样。他们争辩说，只有那些相信自然数应该用一阶逻辑来定义的人才会有这个问题。
许多逻辑学家认为，哥德尔的不完备性定理对大卫希尔伯特的第二个问题造成了致命的打击，后者要求数学的有限一致性证明。尤其是第二个不完备定理，通常被视为使问题变得不可能。然而，并非所有数学家都同意这种分析，希尔伯特第二个问题的状态尚未确定（参见“关于问题状态的现代观点”）。
思想和机器
包括哲学家JRLucas和物理学家RogerPenrose在内的作者们就哥德尔的不完备性定理对人类智能的暗示进行了辩论。大部分争论都集中在人类思维是否等同于图灵机，或者根据Church-Turing论点，是否等同于任何有限的机器。如果是，并且如果机器是一致的，那麽哥德尔的不完备性定理将适用于它。
希拉里·普特南(HilaryPutnam)(1960)建议，虽然哥德尔定理不能应用于人类，因为它们会犯错误并因此不一致，但它可以应用于人类的科学或数学系。假设它是一致的，要么它的一致性不能被证明，要么它不能用图灵机来表示。
AviWigderson(2010)提出数学“可知性”的概念应该基于计算複杂性而不是逻辑可判定性。他写道：“当通过现代标准（即通过计算複杂性）来解释可知性时，哥德尔现象与我们息息相关。”
道格拉斯·霍夫施塔特（DouglasHofstadter）在他的着作《哥德尔、埃舍尔、巴赫和我是一个奇怪的循环》中引用了哥德尔的定理作为他所谓的奇怪循环的一个例子，一种存在于公理形式系统中的分层的、自我参照的结构。他认为这与在人类头脑中产生意识、“我”的感觉的结构相同。哥德尔定理中的自我参照来自于哥德尔句子在数学原理的形式系统中断言其自身的不可证明性，而人类思维中的自我参照来自大脑将刺激抽象和分类为“符号”的方式，或对概念做出反应的神经元组，在这实际上也是一个正式的系统中，最终产生了对进行感知的实体的概念进行建模的符号。Hofstadter认为，在一个足够複杂的形式系统中，一个奇怪的循环会导致“向下”或“颠倒”因果关係，一种因果关係的正常层次被颠倒过来的情况。在哥德尔定理的情况下，简而言之，这表现为以下内容：
“仅仅知道公式的含义，就可以推断出它的真假，而不用费力地以老式的方式推导出它，这需要人们有条不紊地从公理中“向上”跋涉。这不仅奇特，而且令人惊讶.通常，人们不能只看一个数学猜想的内容，而仅仅依靠该陈述的内容来推断该陈述的真假。（我是一个奇怪的循环。）
在心智这个更複杂的形式系统的情况下，这种“向下因果关係”在霍夫施塔特看来，表现为一种不可言喻的人类本能，即我们心智的因果关係在于高层次的慾望、概念、个性、思想和思想，而不是神经元甚至基本粒子之间的低水平相互作用，即使根据物理学，后者似乎具有因果力。
“因此，我们正常的人类感知世界的方式存在一种奇怪的颠倒：我们被构建为感知“大东西”而不是“小东西”，儘管微小的领域似乎是实际驱动电机的地方现实存在。”（我是一个奇怪的循环。）
副一致逻辑
儘管哥德尔定理通常在经典逻辑的背景下进行研究，但它们在研究准一致逻辑和内在矛盾的陈述（dialetheia）中也发挥着作用。GrahamPriest(1984,2006)认为，用通常的非正式证明概念代替哥德尔定理中的正式证明概念可以用来证明朴素数学是不一致的，并将其用作辩证神论的证据。这种不一致的原因是在系统语言中包含了系统的真值谓词（Priest2006,p.47）.StewartShapiro(2002)对哥德尔定理在辩证神论中的应用给出了更为複杂的评价。
诉诸其他领域的不完备性定理
有时对不完备性定理进行呼吁和类比，以支持超越数学和逻辑的论点。包括TorkelFranzén(2005)在内的几位作者对此类扩展和解释发表了负面评论；帕努·拉蒂凯宁(2005);AlanSokal和JeanBricmont（1999年）；和奥菲莉亚本森和杰里米斯坦格鲁姆（2006年）。Bricmont&Stangroom(2006年，第10页)例如，引用丽贝卡·戈德斯坦(RebeccaGoldstein)对哥德尔公开的柏拉图主义与他的思想有时被用于的反现实主义用途之间的差异的评论。Sokal&Bricmont(1999,p.187)批评RégisDebray在社会学背景下援引该定理；Debray为这种用法辩护为隐喻（同上）。
历史
哥德尔在1929年将他对完备性定理的证明作为博士论文发表后，为了适应他的能力，他转向了第二个问题。他最初的目标是获得希尔伯特第二个问题的正解（Dawson1997,p.63）。当时，自然数和实数类似于二阶算术的理论被称为“分析”，而仅自然数的理论被称为“算术”。
哥德尔并不是唯一致力于一致性问题的人。阿克曼在1925年发表了一个有缺陷的一致性证明进行分析，他试图使用最初由希尔伯特开发的ε-替代方法。那年晚些时候，冯·诺依曼能够在没有任何归纳公理的情况下纠正算术系统的证明。到1928年，阿克曼将修改后的证明传达给伯奈斯。这个修改后的证明使希尔伯特在1929年宣布他相信算术的一致性已经得到证明，并且分析的一致性证明可能很快就会出现。在不完全性定理的发表表明阿克曼的修正证明一定是错误的之后，冯诺依曼提出了一个具体的例子，表明其主要技术是不健全的（Zach2007，p.418；Zach2003，p.33）。
在他的研究过程中，哥德尔发现，虽然断言自己的错误的句子会导致悖论，但断言自己的不可证明性的句子不会。特别是，哥德尔知道现在称为塔斯基不可定义定理的结果，儘管他从未发表过。1930年8月26日，哥德尔向卡尔纳普、费格尔和怀斯曼宣布了他的第一个不完备定理；所有四人都将参加第二次精确科学认识论会议，这是下週在柯尼斯堡举行的一次重要会议。
公告
1930年的柯尼斯堡会议是三个学术团体的联合会议，当时许多重要的逻辑学家都出席了会议。Carnap、Heyting和vonNeumann分别就逻辑主义、直觉主义和形式主义的数学哲学发表了一小时的演讲（Dawson1996，第69页）。会议还包括希尔伯特在哥廷根大学离职时的退休致辞。希尔伯特在演讲中论证了他认为所有数学问题都可以解决的信念。他在演讲的结尾说：
对于数学家来说，没有Ignorabimus，而且，在我看来，自然科学也根本没有。...[没有人]成功找到无法解决的问题的真正原因是，在我看来，没有无法解决的问题。与愚蠢的无知者相反，我们的信条反对：我们必须知道。我们会知道的！
这篇演讲很快被称为对希尔伯特数学信仰的总结（其最后六个词，“Wirmüssenwissen。Wirwerdenwissen！”，在1943年被用作希尔伯特的墓誌铭）。儘管哥德尔很可能出席希尔伯特的演讲，但两人从未面对面（Dawson1996,p.72）。
哥德尔在会议第三天的圆桌讨论会上宣布了他的第一个不完备定理。除了冯·诺依曼的声明外，这一声明几乎没有引起人们的注意，他把哥德尔拉到一边进行交谈。那年晚些时候，冯·诺依曼独立工作，了解了第一个不完备性定理，获得了第二个不完备性定理的证明，他在1930年11月20日的一封信中向哥德尔宣布了这个证明（Dawson1996，第70页）。哥德尔独立获得了第二不完备定理并将其包含在他提交的手稿中，该手稿于1930年11月17日被MonatsheftefürMathematik收到。
哥德尔的论文于1931年发表在Monatshefte，标题为“ÜberformsunentscheidbareSätzederPrincipiaMathematicaundverwandterSystemeI”（“OnFormallyUndecidablePropositionsinPrincipiaMathematicaandRelatedSystemsI”）。正如标题所暗示的那样，哥德尔最初计划在下一卷Monatshefte中发表论文的第二部分；第一篇论文的迅速接受是他改变计划的一个原因（vanHeijenoort1967，第328页，脚註68a）.
泛化和接受
哥德尔于1933-1934年在普林斯顿就他的定理进行了一系列讲座，听众包括Church、Kleene和Rosser。此时，哥德尔已经掌握了他的定理所需的关键属性是系统必须是有效的（当时使用了“一般递归”这个术语）。罗瑟在1936年证明，如果哥德尔句子以适当的方式改变，ω-一致性假设是哥德尔原始证明的一个组成部分，可以用简单一致性代替。这些发展使不完备性定理基本上以现代形式存在。
根岑在1936年发表了他的一阶算术一致性证明。希尔伯特接受这个证明是“有限的”，儘管（正如哥德尔定理已经表明的那样）它不能在被证明是一致的算术系统内形式化。
不完备性定理对希尔伯特程序的影响很快就被意识到了。Bernays在GrundlagenderMathematik(1939)的第二卷中包含了对不完备性定理的完整证明，以及Ackermann关于ε-替代方法的附加结果和Gentzen的算术一致性证明。这是第二个不完备性定理的第一个完整的公开证明。
批评
芬斯勒
PaulFinsler(1926)使用理查德悖论的一个版本来构建一个错误的表达式，但在他开发的一个特定的、非正式的框架中是无法证明的。哥德尔在证明不完备性定理时并不知道这篇论文（CollectedWorksVol.IV.,p.9）。芬斯勒于1931年写信给哥德尔，告知他这篇论文，芬斯勒认为这篇论文对于不完备定理具有优先权。Finsler的方法不依赖于形式化的可证明性，与Gödel的工作只有表面上的相似之处（vanHeijenoort1967,p.328）.哥德尔阅读了这篇论文，但发现它存在严重缺陷，他对芬斯勒的回应表达了对缺乏形式化的担忧（道森，第89页））。芬斯勒在他的职业生涯的剩馀时间裡继续为他的数学哲学辩护，这种哲学避开了形式化。
策梅洛
1931年9月，恩斯特·策梅洛（ErnstZermelo）写信给哥德尔，宣布他所说的哥德尔论证中的“本质差距”（道森，第76页））。10月，哥德尔回復了一封10页的信（道森，第76页）,Grattan-Guinness,pp.512–513），他指出Zermelo错误地假设系统中的真值概念在该系统中是可定义的（塔斯基的不可定义定理通常不正确）。但策梅洛并没有松懈，他在印刷品上发表了他的批评，“对他的年轻竞争对手发表了相当严厉的段落”（Grattan-Guinness，第513页））。哥德尔认为进一步追究此事毫无意义，卡尔纳普同意（道森，第77页））。Zermelo的大部分后续工作都与比一阶逻辑更强大的逻辑有关，他希望藉此展示数学理论的一致性和分类性。
维特根斯坦
路德维希·维特根斯坦(LudwigWittgenstein)写了几篇关于不完备性定理的文章，这些文章在他死后发表在1953年的《数学基础评论》中，特别是有一段有时被称为“臭名昭着的段落”，他似乎混淆了“真实”和“可证明”的概念。罗素系统。哥德尔是维特根斯坦早期的理想语言哲学和逻辑哲学主宰着维也纳学派思想的时期的成员。关于维特根斯坦是误解了不完备定理还是只是表达不清楚，一直存在争议。哥德尔的Nachlass中的文字表达了维特根斯坦误解了他的想法的信念。
多位评论员认为维特根斯坦误解了哥德尔（Rodych2003），儘管JulietFloyd和HilaryPutnam（2000年）以及GrahamPriest（2004年）提供了文本解读，认为大多数评论误解了维特根斯坦。Bernays、Dummett和Kreisel在获释后，对维特根斯坦的言论发表了单独的评论，所有评论都非常负面（Berto2009，第208页）.这种批评的一致使维特根斯坦关于不完备定理的评论对逻辑界影响不大。1972年，哥德尔说：“维特根斯坦是不是疯了？他是认真的吗？他故意发表一些无关紧要的无意义的陈述”（Wang1996,p.179），并写信给KarlMenger，维特根斯坦的评论表明了对不完备性定理写作的误解：
从您引用的段落中可以清楚地看出，维特根斯坦不理解[第一个不完备性定理]（或假装不理解）。他将其解释为一种逻辑悖论，而实际上恰恰相反，即数学中绝对没有争议的部分（有限数论或组合学）中的数学定理。(王1996,p.179)
自2000年维特根斯坦的Nachlass发表以来，一系列哲学论文试图评估对维特根斯坦言论的原始批评是否合理。Floyd&Putnam(2000)认为，维特根斯坦对不完备性定理的理解比以前假设的要全面。他们特别关注将ω-不一致系统的哥德尔句子解释为实际上说“我不可证明”，因为该系统没有可证明性谓词对应于实际可证明性的模型。罗迪奇(2003)认为他们对维特根斯坦的解释在历史上是不合理的，而Bays(2004)反对弗洛伊德和普特南对可证明性谓词的哲学分析。贝托(2009)探讨了维特根斯坦的着作与平行逻辑理论之间的关係。
等一致性
在数理逻辑中，如果一种理论的一致性意味着另一种理论的一致性，则两种理论是等一致的，反之亦然。在这种情况下，粗略地说，它们“彼此一致”。
一般来说，不可能证明理论T的绝对一致性。相反，我们通常採用一个被认为是一致的理论S，并尝试证明如果S一致，则T也必须一致的较弱陈述——如果我们能做到这一点，我们就说T相对于S是一致的。如果S相对于T也是一致的，那麽我们说S和T是等一致的。
一致性
在数理逻辑中，形式理论作为数学对象进行研究。由于一些理论足够强大，可以对不同的数学对象进行建模，因此很自然地想知道它们自身的一致性。
希尔伯特在20世纪初提出了一个计划，其最终目标是使用数学方法显示数学的一致性。由于大多数数学学科都可以简化为算术，因此该程序很快成为通过算术本身可形式化的方法建立算术一致性的方法。
哥德尔的不完备性定理表明希尔伯特的程序无法实现：如果一个一致的递归可枚举理论足够强大，可以形式化它自己的元数学（无论某事是否是证明），即足够强大到可以模拟算术的弱片段（罗宾逊算术）够了），那麽该理论就无法证明其自身的一致性。关于代表元数学陈述“理论是一致的”的形式陈述需要满足哪些要求，有一些技术警告，但结果是，如果（足够强的）理论可以证明其自身的一致性，那麽要么没有可计算的方法确定一个陈述是否甚至是理论的公理，或者理论本身是不一致的（在这种情况下，它可以证明任何事情，包括错误的陈述，例如其自身的一致性）。
鑑于此，人们通常考虑相对一致性，而不是完全一致：让S和T成为形式理论。假设S是一个一致的理论。是否遵循T是一致的？如果是这样，那麽T相对于S是一致的。如果每个理论相对于另一个是一致的，则两个理论是等一致的。
一致性强度
如果T相对于S是一致的，但不知道S相对于T是一致的，那麽我们说S比T具有更大的一致性强度。在讨论这些一致性强度问题时，需要仔细解决讨论所在的元理论。对于二阶算术级别的理论，逆向数学程序有很多话要说。一致性强度问题是集合论的常见部分，因为这是一个递归理论，当然可以对大多数数学进行建模。集合论中使用最广泛的一组公理称为採埃孚。当一个集合论语句A与另一个B等价时，所声称的是在元理论中（在这种情况下是皮亚诺算术），可以证明理论ZFC+A和ZFC+B是等价的。通常，可以採用原始递归算术作为所讨论的元理论，但即使元理论是ZFC或它的扩展，这个概念也是有意义的。强制方法可以证明ZFC、ZFC+CH和ZFC+¬CH理论都是等一致的（其中CH表示连续统假设）。
在讨论ZFC的片段或它们的扩展时（例如，ZF，没有选择公理的集合论，或ZF+AD，有确定性公理的集合论），上述概念会相应地进行调整。因此，ZF与ZFC是等价的，如Gödel所示。
许多组合语句的一致性强度可以通过大基数来校准。例如：
对Kurepa假设的否定与不可接近的基数的存在是等价的，
特殊的不存在ω₂-Aronszajn树与Mahlo基数的存在是等价的，
的不存在ω₂-Aronszajn树与弱紧凑基数的存在是等价的。
线性顺序
在数学中，全阶或线性阶是任意两个元素可比较的偏阶。也就是说，一个全序是一个二元关係≤在某些片场X,满足以下所有一个,b和C在X：
a≤a（反身的）。
如果a≤b和b≤c然后a≤c（传递）。
如果a≤b和b≤a然后a=b（反对称）。
a≤b或者b≤a（强连接，以前称为total）。
总订单有时也称为简单、连接、或完整订单。一个有全序的集合是一个全序集；术语简单有序集合，线性有序集合，和losst也被使用。术语链有时被定义为全序集的同义词，但通常是指给定部分有序集的某种全序子集。
给定偏序到全序的扩展称为该偏序的线性扩展。
严格和非严格总顺序
一组严格的总顺序X是严格的偏序X其中任何两个不同的元素是可比较的。也就是说，一个全序是一个二元关係大于我们可能指的是由诱导的N上的阶拓扑（在这种情况下，它们恰好是相同的，但不会一般来说）。
由全序引起的序拓扑可能被证明是遗传正常的。
完整性
如果每个具有上界的非空子集都具有最小上界，则称完全有序集是完备的。例如，实数集R是完备的，但有理数集Q不完备。换句话说，完整性的各种概念（不要与“完全”混淆）不会延续到限制。例如，在实数上，关係≤的一个性质是R的每个具有上界的非空子集S都有一个R中的最小上限（也称为上界）。但是，对于有理数来说，这个上确性不一定是有理数，所以同样的性质不成立关係式≤对有理数的限制。
有许多结果将阶拓扑的属性与X的完整性相关联：
如果X上的有序拓扑是连通的，则X是完整的。
X在有序拓扑下连接当且仅当它是完整的并且X中没有间隙（间隙是X中的两个点a和b且a<b使得没有c满足a<c<b。）
X是完备的当且仅当在阶拓扑中闭的每个有界集都是紧的。
作为一个完全格的完全有序集（具有它的有序拓扑）是紧緻的。例如，实数的闭区间，例如单位区间[0,1]，以及彷射扩展实数係统（扩展实数线）。这些例子之间存在保序同胚。
顺序总和
对于任何两个不相交的总订单(A₁,≤1₁)和(一个A₂,≤₂),有一个自然顺序≤+在片场A₁∪A₂，这称为两个订单的总和，有时只是A₁+A₂：
为了x,y∈A₁∪A₂,x≤+y当且仅当以下条件之一成立时成立：
x,y∈A₁和x≤₁y
x,y∈A₂和x≤₂y
x∈A₁和y∈A₂
直观地说，这意味着第二组的元素被添加到第一组的元素之上。
更一般地说，如果(Ｉ,≤)是一个完全有序的索引集，并且对于每个i∈Ｉ结构(Aᵢ,≤ᵢ)是一个线性顺序，其中集合Aᵢ是成对不相交的，那麽自然全序⋃ᵢAᵢ定义为
为了x,y∈⋃i∈ＩAᵢ,x≤y如果：
要么有一些i∈Ｉ和x≤ᵢy或者有一些i<j在Ｉ和x∈Aᵢ,y∈Aⱼ
全序集的笛卡尔积上的顺序
为了增加强度，即减少对的集合，两个完全有序集合的笛卡尔积的三个可能的顺序是：
字典顺序：(a,b)≤(c,d)当且仅当a<c或(a=c且b≤d)。这是一个总订单。
(a,b)≤(c,d)当且仅当a≤c且b≤d（产品订单）。这是一个偏序。
(a,b)≤(c,d)当且仅当(a<candb<d)或(a=candb=d)（相应严格全序的直接乘积的自反闭包）。这也是一个偏序。
对于两个以上集合的笛卡尔积，可以类似地定义所有三个。
应用于向量空间Rn，它们中的每一个都使它成为一个有序的向量空间。
另请参阅部分有序集的示例。
在Rn的一个子集上定义的n个实变量的实函数定义了一个严格的弱序以及该子集上相应的总预序。
相关结构
反对称、传递和自反（但不一定是完全的）的二元关係是偏序关係。
具有兼容全序的群是全序群。
只有少数非平凡结构是（可定义为）总阶的约简。忘记方向会导致介数关係。忘记末端的位置会导致循环顺序。忘记这两个数据会导致分离关係。
冯诺依曼宇宙
在集合论和相关的数学分支中，冯诺依曼宇宙或冯诺依曼集合层次，用V表示，是遗传有根据的集合的类。该集合由Zermelo-Fraenkel集合论(ZFC)形式化，通常用于提供ZFC公理的解释或动机。这个概念是以约翰·冯·诺依曼的名字命名的，儘管它是由ErnstZermelo在1930年首次发表的。
有充分根据的集合的等级被归纳定义为大于该集合所有成员等级的最小序数。[1]特别是，空集的秩为零，并且每个序数都有一个等于它自己的秩。V中的集合根据它们的等级分为超限层次Vα，称为累积层次。
定义
累积层次是由序数类索引的集合Vα的集合；特别地，Vα是所有秩小于α的集合的集合。因此对于每个序数α有一组Vα。Vα可以通过超限递归定义如下：
令V0为空集：
V₀:=∅.
对于任何序数β，令Vβ+1为Vβ的幂集：
Vβ+1:=P(Vᵦ).
对于任何极限序数λ，令Vλ是迄今为止所有V阶段的并集：
Vλ:=⋃β<λ/Vβ.
关于这个定义的一个关键事实是，在ZFC的语言中只有一个公式φ(α,x)声明“集合x在Vα中”。
集合Vα称为阶段或等级。
V类被定义为所有V阶段的并集：
V:=⋃α/Vα.
等效定义集
Vα:=⋃β<α/P(Vᵦ)对于每个序数α，其中P(X)是幂集X.
集合S的秩是最小的α，使得S⊆Vα.另一种计算排名的方法是：
ranks(S)=⋃{rank(z)+1∣z∈S}.
冯诺依曼宇宙的初始部分。序数乘法与我们通常的约定相反；请参阅序数运算。
层次结构的有限和低基数阶段
前五个冯诺依曼阶段V0到V4可以如下可视化。（空框表示空集。仅包含空框的框表示仅包含空集的集合，依此类推。）
该序列表现出正向生长。集合V5包含216=65536个元素；集合V6包含265536个元素，大大超过了已知宇宙中的原子数；对于任何自然的n，集合Vn+1包含2↑↑n个元素，使用Knuth的向上箭头符号。因此，累积层次结构的有限阶段不能在阶段5之后明确写下。集合Vω具有与ω相同的基数。集合Vω+1具有与实数集相同的基数。
应用和解释
V作为集合论模型的应用
如果ω是自然数的集合，那麽Vω是遗传有限集的集合，它是没有无穷公理的集合论模型。
Vω+ω是“普通数学”的宇宙，是Zermelo集合论的模型。支持Vω+ω充分性的一个简单论据是观察到Vω+1对于整数是足够的，而Vω+2对于实数是足够的，并且可以构建大多数其他正常数学作为这些集合中的各种关係，无需替换公理即可超出Vω+ω。
如果κ是不可接近的基数，那麽Vκ是Zermelo-Fraenkel集合论(ZFC)本身的模型，而Vκ+1是Morse-Kelley集合论的模型。（注意每个ZFC模型也是一个ZF模型，每个ZF模型也是一个Z模型。）
将V解释为“所有集合的集合”
V不是“所有集合的集合”，原因有二。首先，它不是一个集合；儘管每个单独的阶段Vα是一个集合，但它们的并集V是一个适当的类。其次，V中的集合只是有根据的集合。基础公理（或正则性）要求每个集合都是有根据的，因此在V中，因此在ZFC中每个集合都在V中。但是其他公理系统可能会省略基础公理或用强否定代替它（例如Aczel的反基础公理）。这些没有充分根据的集合论并不常用，但仍然可以研究。
对“所有集合的集合”解释的第三个反对意见是，并非所有集合都必然是“纯集合”，它们是使用幂集和并集从空集构造的。Zermelo在1908年提出了包含ureelements，他在1930年从中构建了一个超限递归层次结构。这种ureelements在模型理论中被广泛使用，特别是在Fraenkel-Mostowski模型中。
V和正则公理
公式V=⋃αVα通常被认为是一个定理，而不是一个定义。Roitman声明（没有参考文献）认为正则公理等价于ZF集合到累积层次结构的等价性是由于冯诺依曼。
V的存在状态
由于V类可能被认为是大多数数学的舞台，因此确定它在某种意义上“存在”是很重要的。由于存在是一个困难的概念，人们通常用一致性问题代替存在问题，即概念是否没有矛盾。哥德尔的不完备性定理构成了一个主要障碍，它有效地暗示了在ZF集合论本身中证明ZF集合论的一致性是不可能的，只要它实际上是一致的。
冯诺依曼宇宙的完整性从根本上取决于作为构造中秩参数的序数的完整性，以及构建序数和冯诺依曼宇宙的超限归纳的完整性。可以说序数结构的完整性依赖于冯诺依曼1923年和1928年的论文。通过超限归纳构造V的完整性可以说是在Zermelo1930年的论文中确立的。
历史
累积类型层次结构，也称为冯诺依曼宇宙，GregoryH.Moore(1982)声称不准确地归因于冯诺依曼。冯·诺依曼宇宙的第一份出版物是ErnstZermelo在1930年出版的。
1928年vonNeumann为Zermelo-Fraenkel集合论和Neumann自己的集合论（后来发展为NBG集合论）证明了集合的一般超限递归定义的存在性和唯一性。在这两篇论文中，他都没有应用他的超限递归方法来构建所有集合的宇宙。Bernays和Mendelson对vonNeumann宇宙的介绍都归功于vonNeumann的超限归纳构造方法，儘管没有将其应用于构造普通集的宇宙。
符号V不是对冯·诺依曼名字的致敬。它在1889年被Peano用于集合的宇宙，字母V表示“Verum”，他将其用作逻辑符号并表示所有个体的类别。Whitehead和Russell在1910年也採用Peano的记法V来表示所有集合的类。vonNeumann在他1920年代关于序数和超限感应。PaulCohen明确地将他对字母V的使用（用于所有集合的类）归因于Gödel1940年的一篇论文，儘管哥德尔很可能从怀特黑德和罗素等早期资料中获得了这个符号。
哲学观点
有两种方法可以理解冯诺依曼宇宙V与ZFC的关係（以及每种方法的许多变体，以及它们之间的阴影）。粗略地说，形式主义者倾向于将V视为源自ZFC公理的东西（例如，ZFC证明每个集合都在V中）。另一方面，现实主义者更有可能将冯·诺依曼层次结构视为直觉可以直接访问的东西，并将ZFC的公理视为命题，我们可以在V中给出其真实性的自然语言直接论证。一个可能的中间位置是冯诺依曼层次的心理图景为ZFC公理提供了动机（因此它们不是任意的），但不一定描述真实存在的对象。
超限归纳
超限归纳是数学归纳对有序集合的扩展，例如对序数或基数的集合。它的正确性是ZFC的一个定理。
案例归纳
让P(α)是为所有序数定义的属性α.假设每当P(β)对所有人都是正确的β<α，然后P(α)也是如此。那么超限归纳告诉我们P对所有序数都是正确的。
通常证明分为三种情况：
零案例：证明P(0)是真的。
后继案例：证明对于任何后继序数α+1,P(α+1)从P(α)（并且，如有必要，P(β)对所有人β<α）。
极限情况：证明对于任何极限序数λ,P(λ)从P(β)
对所有人β<λ.
除了考虑的序数类型外，所有三种情况都是相同的。它们在形式上不需要单独考虑，但在实践中，证明通常如此不同，以至于需要单独介绍。零有时被认为是极限序数，然后有时可能在证明中与极限序数相同。
序数的表示高达ω^ω.螺旋的每一圈代表一个力量ω.超限归纳需要证明一个基本情况（用于0）、一个后继情况（用于那些有前任的序数）和一个极限情况（用于没有前任的序数）。
超限递归
超限递归类似于超限归纳；然而，我们没有证明某些东西适用于所有序数，而是构造了一个对象序列，每个序数都有一个。
例如，可以通过选择一个向量来创建一个（可能是无限维的）向量空间的基础v0并且对于每个序数α选择一个不在向量范围内的向量{vᵦ∣β<α}.当无法选择向量时，此过程停止。
更正式地说，我们可以将超限递归定理表述如下：
超限递归定理（第1版）。给定一个类函数G:V→V（其中V是所有集合的类），存在一个唯一的超限序列F:Ord→V（其中Ord是所有序数的类）使得
F(α)=G(F↾α)对于所有序数α，其中↾表示F的域对序数<α的限制。
与归纳的情况一样，我们可以分别处理不同类型的序数：超限递归的另一种表述如下：
超限递归定理（第2版）。给定一个集合g1和类函数G2,G3，存在一个唯一函数F:Ord→V使得
F(0)=g1,
F(α+1)=G2(F(α))，对于所有α∈Ord，
F(λ)=G3(F↾λ),对于所有限制λ≠0。
请注意，我们要求G2、G3的域足够宽以使上述属性有意义。满足这些性质的序列的唯一性可以使用超限归纳来证明。
更一般地，可以通过对任何有根据的关係R进行超限递归来定义对象。（R甚至不需要是一个集合；它可以是一个适当的类，只要它是一个类似集合的关係；即对于任何x，所有y的集合使得yRx是一个集合。）
与选择公理的关係
使用归纳和递归的证明或构造通常使用选择公理来产生可以通过超限归纳处理的有序关係。然而，如果所讨论的关係已经是良序的，人们通常可以使用超限归纳而不调用选择公理。例如，许多关于Borel集的结果是通过对集合的序数秩进行超限归纳来证明的；这些等级已经有序，因此不需要选择公理来对它们进行有序排列。
以下Vitali集的构造显示了选择公理可用于超限归纳证明的一种方式：
首先，对实数进行良序（这是选择公理通过良序定理进入的地方），给出一个序列⟨rα|α<β⟩,其中β是具有连续统的基数的序数。令v0等于r0。然后让v1等于rα1，其中α1是最小的，使得rα1-v0不是有理数。继续;在每一步使用r序列中的最小实数，它与迄今为止在v中构造的任何元素没有有理差序列。继续直到r序列中的所有实数都用完。最后的v序列将枚举Vitali集。
上述论证在一开始就以一种基本的方式使用了选择公理，以便对实数进行良好排序。在这一步之后，选择公理不再使用。
选择公理的其他用途更为微妙。例如，通过超限递归的构造通常不会为Aα+1指定唯一值，给定直到α的序列，但只会指定Aα+1必须满足的条件，并认为至少存在一个设置满足这个条件。如果不可能在每个阶段定义这样一个集合的唯一示例，那么可能有必要调用（某种形式的）选择公理来在每个步骤中选择一个这样的公理。对于可数长度的归纳和递归，依赖选择的较弱公理足够了。因为存在满足依赖选择公理但不满足选择公理的集合理论家感兴趣的Zermelo-Fraenkel集合论模型，所以特定证明只需要依赖选择的知识可能是有用的。
幂
在数学中，集合S的幂集（或幂集）是S的所有子集的集合，包括空集和S本身。在公理集合论中（例如在ZFC公理中发展起来的），任何集合的幂集的存在都是由幂集公理假设的。S的幂集不同地表示为P(S),𝒫(S),P(S),P(S)，或2S。使用符号2S表示从S到给定两个元素的集合（例如{0,1}）的所有函数的集合，因为S的幂集可以被识别为、等价于或双射的集合从S到给定的两个元素集的所有函数。
P(S)的任何子集称为S上的集合族。
例子
如果S是集合{x,y,z}，那麽S的所有子集都是
{}（也表示∅或者∅，空集或空集）
{x}
{是}
{}_
{x,y}
{x,z}
{y,z}
{x,y,z}
因此S的幂集是{{},{x},{y},{z},{x,y},{x,z},{y,z},{x,y,z}}.
特性
如果S是具有基数的有限集|小号|=n（即集合S中所有元素的个数为n），则S的所有子集的个数为|P(小号)|=2n。该事实以及表示幂集P(S)的符号2S的原因在下面进行说明。
具有基数的集合S的子集A的指示函数或特徵函数|小号|=n是从S到两个元素集合{0,1}的函数，记为IA:S→{0,1}，表示S的一个元素是否属于A；如果S中的x属于A，则IA(x)=1，否则为0。S的每个子集A由指示函数IA标识或等价于指示函数IA，并且{0,1}S作为从S到{0,1}的所有函数的集合，由所有子集的所有指示函数组成年代。换句话说，{0,1}S与幂集P(S)等价或双射。由于S中的每个元素对应于{0,1}S中任意函数下的0或1，则{0,1}S中所有函数的个数为2n。由于数字2可以定义为{0,1}（参见例如冯诺依曼序数），因此P(S)也表示为2S。显然|2秒|=2|S|持有。一般来说，XY是所有函数的集合Y到X和|XY|=|X||Y|.
康托尔的对角线论证表明，一个集合的幂集（无论是否无限）总是具有严格高于集合本身的基数（或者非正式地，幂集必须大于原始集）。特别是，康托尔定理表明，可数无限集的幂集是不可数无限的。自然数集的幂集可以与实数集一一对应（参见连续统的基数）。
集合S的幂集，连同并、交和补的运算，可以看作是布尔代数的典型例子。事实上，可以证明任何有限布尔代数都同构于有限集的幂集的布尔代数。对于无限布尔代数，这不再正确，但每个无限布尔代数都可以表示为幂集布尔代数的子代数（参见斯通的表示定理）。
集合S的幂集在用对称差分运算考虑时形成一个阿贝尔群（以空集作为单位元素，每个集合都是它自己的逆），当用交集运算考虑时形成可交换么半群.因此可以证明，通过证明分配定律，与这两个操作一起考虑的幂集形成布尔环。
将子集表示为函数
在集合论中，XY是表示从Y到X的所有函数的集合的符号。因为“2”可以定义为{0,1}（例如，参见冯诺依曼序数），所以2S（即{0,1}S）是从S到{0,1}的所有函数的集合.如上所示，2S和S的幂集P(S)在集合论上被认为是相同的。
这种等价性可以应用于上面的例子，其中S={x,y,z}，以获得从0到2n-1的数字的二进製表示的同构，其中n是集合中元素的数量S或|S|=n。首先定义枚举集{(x,1),(y,2),(z,3)}，其中每个有序对中的数字代表S的配对元素的位置在二进制数字序列中，例如{x,y}=011(2)；S的x位于该序列的右起第一个，y位于该序列的右起第二个，序列中的1表示S的与它在序列中的位置对应的元素存在于S的子集中序列while0表示没有。
对于S的整个幂集，我们得到：
这种从P(S)到整数的双射映射是任意的，因此S的所有子集的这种表示不是唯一的，但枚举集的排序顺序不会改变其基数。（例如，{(y,1),(z,2),(x,3)}可用于构造另一个从P(S)到整数的双射，而不改变一一对应的数量。）
然而，只有当S可以被枚举时，这种有限的二进製表示才是可能的。（在本例中，x、y和z分别用1、2和3作为二进制数字序列的位置进行枚举。）即使S具有无限基数（即S中的元素个数），枚举也是可能的是无限的），例如整数或有理数的集合，但不可能，例如如果S是实数的集合，在这种情况下我们不能枚举所有无理数。
与二项式定理的关係
二项式定理与幂集密切相关。来自某个集合的k元素组合是k元素子集的另一个名称，因此组合的数量，表示为C(n,k)（也称为二项式係数）是一组具有k个元素的子集的数量n个元素；换句话说，它是具有k个元素的集合的数量，这些元素是具有n个元素的集合的幂集的元素。
例如，具有三个元素的集合的幂集具有：
C(3,0)=1个包含0个元素的子集（空子集），
C(3,1)=3个具有1个元素的子集（单例子集），
C(3,2)=3个具有2个元素的子集（单例子集的补集），
C(3,3)=1个具有3个元素的子集（原始集本身）。
递归定义
如果小号是一个有限集，然后是一个递归定义磷(小号)进行如下：
如果S={}，然后P(S)={{}}.
否则，让e∈S和T=S∖{e};然后P(S)=P(T)∪{t∪{e}：t∈P(T)}.
用一句话来说：
空集的幂集是一个单例，其唯一元素是空集。
对于非空集S，让e是集合的任何元素并且T其相对补；那麽幂集小号是一个幂集的并集T和一个幂集T其每个元素都扩展为e元素。
有限基数的子集
基数小于或等于κ的S的子集集有时记为Pκ(S)或[S]κ，基数严格小于κ的子集集有时记为P<κ(S)或[S]<κ.类似地，S的非空子集的集合可以表示为P≥1(S)或P+(S).
幂对象
集合可以被视为没有非平凡运算或定义方程的代数。从这个角度来看，X的幂集作为X的子集的概念自然地推广到代数结构或代数的子代数。
一个集合的幂集，当通过包含排序时，总是一个完整的原子佈尔代数，并且每个完整的原子佈尔代数都是作为某个集合的所有子集的格出现的。对任意代数的推广是，一个代数的子代数集，再次通过包含排序，总是一个代数格，并且每个代数格都是作为某个代数的子代数格出现的。因此，在这方面，子代数的行为类似于子集。
然而，子集有两个重要的性质通常不会延续到子代数中。首先，儘管一个集合的子集形成一个集合（以及格），但在某些类中，可能无法将代数的子代数组织为该类中的代数，儘管它们总是可以组织为格子。其次，虽然一个集合的子集与从该集合到集合{0,1}=2的函数是双射的，但不能保证一个代数类包含一个可以以这种方式扮演2的代数.
某些类别的代数同时具有这两种性质。第一个属性比较常见，两者兼有的情况比较少见。两者兼有的一类是multigraphs。给定两个多重图G和H，同态h:G→H由两个函数组成，一个将顶点映射到顶点，另一个将边映射到边。从G到H的同态集合HG然后可以组织为图，其顶点和边分别是出现在该集合中的顶点和边函数。此外，多重图G的子图与从G到多重图Ω的图同态是双射的-在其中一个顶点处循环。因此，我们可以将G的子图组织为多重图ΩG，称为G的幂对象。
多重图作为代数的特别之处在于它的运算是一元的。多重图有两种元素形成顶点集合V和边E，并且有两个一元运算s,t:E→V给出每条边的源（开始）和目标（结束）顶点。所有运算都是一元的代数称为预层。每类预滑层都包含一个预滑层Ω，它扮演子代数的角色，2扮演子集的角色。这样一个类是基本拓扑的更一般概念的一个特例，它是一个封闭的范畴（而且笛卡尔封闭）并且有一个对象Ω，称为子对象分类器。儘管术语“幂对象”有时与指数对象YX同义使用，但在拓扑理论中，Y必须为Ω。
函子和量词
在范畴论和初等拓扑理论中，全称量词可以理解为幂集间函子的右伴随物，集间函数的逆像函子；同样，存在量词是左伴随。