自指与悖论（三）

15. ¬K⟨λ⟩ 肯定前件式于 1,7

16.K⟨λ⟩∧¬K⟨λ⟩ 14 与 15 的合取

这完成了蒙塔古定理的证明。◻

上述证明直接模拟了知者悖论背后的推理。蒙塔古定理表明，在一阶算术的背景下，我们不可能有一个知识或可知性理论能够满足甚至基本原理 A1-A4。蒙塔古定理是塔斯基定理的推广。如果谓词符号 K 满足塔斯基模式 T，那么很容易看出它也满足公理模式 A1-A4。因此，公理模式 A1-A4 构成了 T 模式的弱化，而蒙塔古定理表明，即使是这个弱得多的 T 模式也足以产生不一致性。一种可能的回答是，即使是公理模式 A1–A4 也过于强大，应该进一步弱化。然而，正如之前对悖论的形式化一样，目前尚不清楚如何进一步弱化这些假设，因为对于我们正在形式化的概念（在本例中为可知性）而言，所有假设似乎都是合理且自然的。另一种摆脱不一致结果的可能方法是保留这些原则的当前形式，但仅将其应用于可用句子的子集（这意味着 A1–A4 仅需对某个子集 S 中 ϕ∈S 的句子成立）。这些原则应该适用于所有“正常”句子，但我们可能不想坚持要求它们对某些表达自指陈述的病态句子成立。然而，我们能否合理地指出哪些句子是正常的，哪些是病态的，这一点尚不明确。但我们或许仍然能够找到一些合理的子集，我们可以将我们的原则实例化到这些子集上，并且仍然拥有一致的理论。Revières 和 Levesque (1988) 证明，这些原理仅在所谓的常规句子上实例化时才保持一致，这一结果后来被推广到更具包容性的所谓 RPQ 句子 (Morreau 和 Kraus, 1998)。大多数解决悖论驱动的不一致结果的方法实际上都是这样的：对导致不一致的原理的适用性进行分层或限制，无论是真值原理、集合存在性原理、可知性原理​​还是其他第四个原理。我们将在第 3 节中对此进行更深入的探讨。

在一阶逻辑中将知识形式化为谓词被称为知识的句法处理。或者，也可以选择在合适的模态逻辑中将知识形式化为模态算子。这被称为知识的语义处理（参见“认识论逻辑”条目）。在知识的语义处理中，人们通常会避免自指涉问题，从而避免不一致，但这是以牺牲形式主义的表达能力为代价的（命题模态逻辑不承认任何与构造自指涉公式的对角引理等价的东西，从而避免了自指涉问题）。事实上，上述正则语句正是通过将一阶模态逻辑翻译成谓词逻辑而得到的，因此，仅在正则语句上实例化原理，既遵循了知识的句法处理，又通过将知识算子限制于其在语义处理中的表达能力，从而仍然确保了一致性。

2.4 关于可证明性和可计算性的推论

塔斯基定理证明中给出的核心论证与哥德尔第一不完备定理（Gödel, 1931）的核心论证密切相关。哥德尔定理可以表述如下：

哥德尔第一不完备定理。

如果一阶算术是ω-一致的，则它是不完备的。

如果对于每个包含x作为唯一自由变量的公式ϕ(x)，以下成立，则一个理论被称为ω-一致的：如果对于每个自然数n，⊢¬ϕ(n)（意味着：¬ϕ(n)是可证明的），则⊬∃xϕ(x)（意味着：∃xϕ(x)是不可证明的）。ω-一致性是比普通一致性更强的条件，因此任何ω-一致的理论也将是一致的。如果一个理论包含一个既不能被证明也不能被证伪的公式，那么它就是不完备的。

哥德尔第一不完备定理的证明简述。假设一阶算术既是ω-一致的又是完备的。我们需要证明这会导致矛盾。哥德尔在形式算术中构造了一个公式Bew（“Beweis”），满足：对于所有φ和所有n，

(1)

⊢Bew(n,⟨φ⟩) 当且仅当 n 是φ证明的哥德尔代码。

假设该理论是ω-一致的且完备的，我们可以证明：对于所有句子φ，

(2)

⊢∃xBew(x,⟨φ⟩) 当且仅当 ⊢φ。

(2) 的证明如下。首先，我们从左到右证明蕴涵式。如果 ⊢∃xBew(x,⟨ϕ⟩)，则存在某个 n 使得 ⊬¬Bew(n,⟨ϕ⟩)，根据 ω-一致性。对于该 n，根据完备性，我们得到 ⊢Bew(n,⟨ϕ⟩)。根据上面的 (1)，我们得到 n 表示 ϕ 的证明。也就是说，ϕ 是可证的，所以我们有 ⊢ϕ。为了从右到左证明这个蕴涵式，注意到如果 ⊢ϕ，则一定存在一个 n 使得 ⊢Bew(n,⟨ϕ⟩)，根据 (1)。由此我们得到 ⊢∃xBew(x,⟨ϕ⟩)，正如所要求的。这就完成了 (2) 的证明。现在，当在一个完备理论中我们有 (2) 时，我们还必须满足：

(3)

对于所有句子 ϕ，⊢∃xBew(x,⟨ϕ⟩)↔ϕ。

如果我们将∃xBew(x,⟨ϕ⟩)简写为T⟨ϕ⟩，则(3)变为：

对于所有句子 ϕ，⊢T⟨ϕ⟩↔ϕ。

这就是T模式！因此，如果我们假设一阶算术是ω-一致且完备的，那么模式T就可以在其中得到解释。现在，上面的塔斯基定理表明，不存在这样的一致理论，因此我们得到了矛盾。◻

在上面的证明中，我们将哥德尔不完备定理简化为塔斯基定理的一个应用，以表明两者之间的紧密联系（此版本的证明由Bolander于2002年提出）。哥德尔非常清楚这种联系，事实上，哥德尔甚至似乎在塔斯基本人之前就证明了塔斯基定理（Feferman，1984）。哥德尔定理可以解读为，它表明了纯粹形式化程序所能实现的目标存在局限性。它指出，如果一阶算术是ω一致的（人们普遍认为如此），那么必然存在一些算术语句既不能被一阶算术的形式化程序证明，也不能被其证伪。人们最初可能认为这种局限性可以通过添加额外的公理来解决，但哥德尔证明了，当用任意一组有限的公理模式（或者更一般地说，任意一组递归的公理）扩展一阶算术时，不完备性结果仍然成立。因此，我们得到了一个普遍的限制性结论：不存在一个形式化的证明程序，可以证明任何给定的算术语句成立或不成立。有关哥德尔不完备定理的更多详细信息，请参阅库尔特·哥德尔条目。

哥德尔定理的极限结果与另一个被称为停机问题的不可判定性的极限结果密切相关。这个结论表明，计算能力是有限的。我们将在下文中展示这个结论。这个结论基于图灵机的概念，图灵机是在具有无限内存的计算机上运行的计算机程序的通用模型。因此，任何计算机上运行的任何程序都可以被认为是图灵机（有关更多详细信息，请参阅图灵机条目）。运行图灵机时，它要么在有限数量的计算步骤后终止，要么永远运行下去。如果它在有限数量的计算步骤后终止，我们称它停止运行。停机问题就是寻找一台能够判断其他图灵机是否停止运行的图灵机。如果以下条件成立，我们称图灵机 H 能够判定停机问题：

H 以一对 (⟨A⟩,x) 作为输入，该对由图灵机 A 的哥德尔编码 ⟨A⟩ 和任意字符串 x 组成。如果图灵机 A 在给定输入 x 时停机，H 返回答案“是”，否则返回“否”。

因此，如果图灵机 H 能够判定停机问题，我们可以用它来判定对于任意图灵机 A 和任意输入 x，A 是否会在输入 x 时停机。停机问题的不可判定性是图灵 (1937) 提出的以下结论，即不存在这样的机器：

定理（停机问题的不可判定性）。

不存在能够判定停机问题的图灵机。

证明：假设存在一台图灵机 H 能够判定停机问题。我们需要证明该假设会导致矛盾。这个证明模仿了格雷林悖论。如果图灵机 A 在输入 ⟨A⟩ 时不停止，也就是说，如果 A 在给定其自身的哥德尔代码作为输入时不停止，我们称其为异逻辑的。使用 H，我们可以构造一个图灵机 G，当且仅当输入一个异逻辑图灵机的哥德尔代码时，它才会停止。G 的工作原理如下：

G 将图灵机 A 的哥德尔代码作为输入。然后，它对输入 (⟨A⟩,⟨A⟩) 运行 H。如果 H 对输入 (⟨A⟩,⟨A⟩) 返回“否”，则 G 停止。另一方面，如果 H 对输入 (⟨A⟩,⟨A⟩) 返回“是”，则 G 被迫进入无限循环（即永不停止）。

类似于格雷林悖论，我们现在可以问 G 是否是异逻辑图灵机。这导致了以下等价序列：

G 是异逻辑的

⇔G 在输入 ⟨G⟩ 时不停止（根据异逻辑的定义）

⇔H 在输入 (⟨G⟩,⟨G⟩) 时返回“否”（因为 H 决定了停止概率）。

⇔G 在输入 ⟨G⟩ 时停止（根据 G 的构造）

⇔G 不是异逻辑的（根据异逻辑的定义）

这给出了所需的矛盾。◻

从上面两个定理我们看到，在可证明性和可计算性领域，自指悖论转化为限制性结果：可证明的内容和可计算的内容是有限的。这实际上与语义学、集合论和认识论领域中发生的情况非常相似：自指悖论转化为定理，表明我们可以一致假设真谓词（塔斯基定理）、集合论（朴素集合论的不一致性）和知识谓词（蒙太古定理）所具有的属性存在限制。这些限制性结果很难接受，因为它们大多数与我们的直觉和期望相冲突。自指在所有这些结果中扮演的核心角色，可能会使它们更加难以接受，至少肯定会使它们更加令人费解。然而，我们被迫接受它们，并被迫接受这样一个事实：在这些领域，我们无法获得我们（否则）合理要求的一切。

3. 解决悖论

本节探讨如何解决——或者更确切地说，规避——悖论。要解决或规避悖论，必须弱化一些导致矛盾的假设。选择削弱哪些假设非常困难，因为悖论背后每一个明确陈述的假设似乎都是“显然正确的”——否则它就不能算作悖论。下面我们将探讨解决悖论最具影响力的方法。

到目前为止，本讲是根据悖论的类型进行的，也就是说，语义悖论、集合论悖论和认识论悖论已被分别处理。然而，也已证明这三类悖论在底层结构上是相似的，并且有人认为，解决一个悖论应该就是解决所有悖论的答案（统一解原则）。因此，下文的呈现将不再基于悖论类型，而是基于解决方案类型。下文所讨论的每种解决方案类型均可应用于任何自指悖论，尽管在大多数情况下，所涉及的构造最初仅针对一种悖论类型而开发。

3.1 构建显式层级

构建层级是一种规避集合论、语义学和认知论悖论的方法。罗素最初解决其悖论的方法——以及塔斯基最初解决真值不可定义性问题的方法——都是构建层级。在罗素的案例中，这导致了类型论的出现。在塔斯基的案例中，这导致了如今被称为塔斯基语言层级的理论。在这两种情况下，其思想是将论域（集合、句子）分层为多个层级。在类型论中，这些层级被称为类型。类型论的基本思想是引入一个约束，即给定类型的任何集合只能包含较低类型的元素（即，只能包含位于层级较低位置的集合）。这有效地阻止了罗素悖论，因为任何集合都不能成为其自身的成员。

在塔斯基的案例中，分层是通过以下方式实现的。假设我们想为语言 L0 配备一个真值谓词。根据塔斯基定理（第 2.1 节）可知，这个真值谓词不能是语言 L0 本身的一部分——至少在我们想要真值谓词满足模式 T 的情况下不能。相反，我们可以构建一个语言层次结构，L0,L1,L2,…，其中每种语言 Li+1 都有一个真值谓词 Ti+1，它仅适用于 Lj,j≤i 的句子。在这个层次结构中，L0 被称为对象语言，对于所有 i，Li+1 被称为 Li 的元语言。这个层次结构有效地阻止了说谎者悖论，因为现在一个句子只能表达较低层次句子的真或假，因此像说谎者悖论这样表达自身假的句子无法形成。

罗素的类型理论可以被视为罗素悖论的一个解决方案，因为类型理论展示了如何“修复”集合论，从而使悖论消失。同样，塔斯基的层次结构可以被视为说谎者悖论的一个解决方案。罗素和塔斯基的解决方案都基于相同的分层思想。需要注意的是，罗素悖论和说谎者悖论都关键依赖于循环概念（自成员和自指）。通过分层，使对象只能包含或指涉较低层次的对象，循环性便会消失。在认识论悖论中，可以通过明确区分一阶知识（关于外部世界的知识）、二阶知识（关于一阶知识的知识）、三阶知识（关于二阶知识的知识）等等，获得类似的分层。这种分层实际上在知识的语义处理中自然而然地存在，其中知识被形式化为模态算子。

构建明确的层级结构足以避免循环性，从而足以阻止标准的自指悖论。然而，也存在一些悖论，例如亚布洛的悖论，它们并不依赖于循环性和自指。这类悖论也可以通过层级结构来阻止，但需要进一步要求层级结构有理有据，即拥有最低层级。否则，非理有据悖论仍然可能被表述出来。例如，亚布罗悖论可以用语言的降序结构形式化。降序结构由语言 L0、L-1、L-2、… 组成，其中每种语言 L-i 都有一个真值谓词，该谓词仅适用于语言 L-j,j>i 的句子。类似地，集合论中关于非良基悖论的悖论可以用允许负类型的类型论来表述。由此​​得出的结论是，宇宙的分层本身并不足以避免所有悖论——这种分层也必须是良基的。

如今，大多数人认为，构建一个明确的（良基的）层次结构来解决悖论是一种过于激进和粗暴的方法。这些层级结构引入了许多在“平坦宇宙”中不存在的复杂技术细节，即使悖论确实消失了，所有非悖论的自指现象也会消失。克里普克（1975）给出了一个取自日常话语的说明性例子。设N是尼克松的以下陈述：

(N)

琼斯关于水门事件的所有言论均为真；

设J是琼斯的以下陈述：

(J)

尼克松关于水门事件的大部分言论均为假。

在塔斯基的语言层级结构中，句子N必须位于琼斯所有言论的更高层级，反之，句子J必须位于尼克松所有言论的更高层级。由于N是尼克松的话语，而J是琼斯的话语，因此N必须处于比J更高的层次，而J又必须处于比N更高的水平。这显然是不可能的，因此在像塔斯基这样的层级结构中，这些句子甚至无法被表述出来。句子N和J实际上都是间接自指的，因为N指的是包含J在内的整体，而J指的是包含N在内的整体。然而，在大多数情况下，N和J是无害的，不会产生悖论。只有在琼斯的所有话语（可能除了J之外）都为真，而尼克松的话语恰好有一半为假（不考虑N）的特殊情况下，才会产生悖论。克里普克利用N和J仅在特定特殊情况下成问题的事实，来反驳那种完全排除表述N和J的可能性的方法。

另一个反对层级结构方法的论点是，明确的分层并非日常话语的一部分。因此，将其引入正式场合，其唯一目的或许是为了规避悖论，这或许有些临时。日常话语中没有明确的分层，显然并不意味着不存在潜在的、隐含的分层，但至少在我们的语法中没有明确体现。

以上论证是罗素和塔斯基的著作未被考虑作为悖论最终解决方案的原因之一。许多替代解决方案已被提出。例如，人们可以尝试寻找隐含的层次结构，而不是显含的层次结构。隐含的层次结构是指未在语言的语法中明确体现的层次结构。在下一节中，我们将探讨通过此类隐含分层获得的一些悖论解决方案。

3.2 构建隐含层级结构

塔斯基的语义悖论层级方法一直主导着该领域，直到1975年克里普克发表了他著名且影响深远的论文《真理论概要》。这篇论文极大地影响了后来大多数关于真理论和语义悖论的研究方法。然而，值得注意的是，马丁和伍德拉夫（1975）同时且独立地发展了与克里普克非常相似的想法，而吉尔摩（1974）则在集合论的背景下独立地发展了一种类似的方法。

3.2.1 克里普克的真理论

克里普克的思想基于对塔斯基层级方法所涉及问题的分析。克里普克列举了一些反对语言层级结构的论据，即每个句子都处于由其句法形式决定的固定层级。他提出了一种仍然沿用层级概念的替代解决方案，但这些层级并未成为语法的明确组成部分。相反，这些层级成为真值谓词迭代构造的阶段。为了解释克里普克的构造，需要一些额外的技术手段。

在克里普克构造的每个阶段，真值谓词都只是部分定义的，也就是说，它仅适用于该语言中的部分句子。为了处理这种部分定义的谓词，需要使用三值逻辑，即除了真值真和假之外，还使用第三个值“未定义”进行运算的逻辑。第三个值通常表示为“u”或“⊥”（底部）。部分定义的谓词仅在应用于已定义谓词的某个术语时，才会接收经典真值之一“真”或“假”，否则接收“未定义”的值。有几种不同的三值逻辑可用，它们处理第三个值的方式不同。这里仅简要介绍其中一种，称为克莱尼强三值逻辑。关于此逻辑及相关逻辑的更多详细信息，请参阅多值逻辑条目。

在克莱尼的强三值逻辑中，值⊥（未定义）可以解释为“尚未定义”。因此，可以将值为⊥的公式视为实际上具有经典真值（真或假）的公式，只是尚未确定。这种对未定义的解释反映在下面给出的逻辑真值表中。上面的真值表用于析取，下面的真值表用于否定：

∨ 真 假 ⊥

真 真 真 真

假 真 假 ⊥

⊥ 真 ⊥ ⊥

¬

真 假

假 真

⊥ ⊥

这些真值表完整地定义了三值逻辑。因为∨和¬被视为构成一组充分的连接词，而存在量词和全称量词分别被视为无限析取和合取。

为了处理部分定义的真值谓词，有必要引入部分模型的概念。在一阶语言的部分模型中，每个n元谓词符号P都由模型定义域上的一对不相交的n元关系(U,V)解释。U称为P的外延，V称为P的反外延。在该模型中，P对U中的对象为真，对V中的对象为假，否则为未定义。这样，任何原子语句在模型中都会获得真值真、假或未定义之一。非原子公式在模型中通过使用克莱尼强三值逻辑对连接词求值来赋予真值。

给定部分模型的定义，部分解释语言是一对 (L,M)，其中 L 是一阶语言，M 是 L 的部分模型。Kripke 递归地定义了一系列部分解释语言 L0、L1、L2、…，它们的区别仅在于对真值谓词 T 的解释。第一个语言 L0 被认为是任意语言，其中 T 的外延和反外延均为空集。因此，在 L0 中，真值谓词完全未定义。对于任何 α，语言 Lα+1 与 Lα 类似，只是 T 由如下外延/反外延对 (U,V) 解释：