二阶和高阶逻辑（一）

一、简介

2. 二阶逻辑的语法

3.二阶逻辑的语义

3.1 二阶逻辑的 Ehrenfeucht-Fraïssé 博弈

4. 二阶公式的性质

5.二阶逻辑臭名昭著的力量

5.1 二阶逻辑和一阶逻辑之间的放置距离

5.2 完备性定理的崩溃

5.3“披着羊皮的集合论”

5.4 二阶逻辑是否依赖于选择公理？

6.二阶逻辑中真理的非绝对性

7.二阶逻辑模型论

7.1 二阶可表征结构

7.2 二阶逻辑和大基数

7.3 一般模型和Henkin模型的模型理论

8. 可判定性结果

9.二阶逻辑公理

9.1 通用模型和Henkin模型

9.2 无穷公理

10. 类别性

11. 一阶和二阶之间的逻辑

12. 高阶逻辑与类型理论

13. 数学基础

14.二阶算术

15.二阶集合论

16.有限模型理论

参考书目

学术工具

其他互联网资源

相关条目

一、简介

二阶逻辑[1]由弗雷格在他的 Begriffsschrift (1879) 中引入，他还在 (1884: §53) 中创造了术语“二阶”(“zweiter Ordnung”)。直到 20 世纪 30 年代，集合论开始成为数学的基础，它才被广泛应用于逻辑中。很难确切地说出为什么会发生这种情况，但与二阶和高阶逻辑（包括类型论）相比，集合论基于一个二元谓词 x∈y，因此具有一定的简单性。哲学家们对二阶逻辑优点的讨论，特别是与集合论相比的优点，一直持续到今天（Shapiro 1991）。同时二阶逻辑已成为计算机科学逻辑，特别是有限模型理论的标准工具。理论计算机科学的核心问题，例如 P = NP？问题，可以看作是关于有限上下文中的二阶逻辑的问题。

归根结底，二阶逻辑只是另一种形式语言。通过在我们选择的数学元理论（我们选择集合论）中工作，可以给予它标准的处理，使语法、语义和证明理论变得精确。可以使用二阶逻辑本身作为元理论，但它会更复杂，仅仅是因为二阶逻辑不如集合论发达。

一阶逻辑和二阶逻辑之间的区别在初等数学中最容易理解。让我们考虑一下数论。我们研究的对象是自然数0、1、2……及其算术。通过一阶逻辑，我们可以使用原子表达式 x=y、x+y=z 和 x×y=z 结合命题运算 ∧、Ø、∨、→ 以及量词 ∀x 和 ∃x 来制定关于数论的陈述。这里变量 x、y、z…被认为在自然数范围内。使用二阶逻辑，我们可以表达更多：我们有变量 x、y、z……，就像数字的一阶逻辑一样。此外，我们还有用于表示数字属性和数字之间关系的变量 X、Y、Z、…以及用于这些变量的量词 ∀X 和 ∃X。我们有一阶逻辑的原子表达式以及 X(y1,…,yn) 形式的新原子表达式。

一个有趣且经过深入研究的问题出现了：自然数的哪些属性可以用一阶逻辑来表达，哪些可以用二阶逻辑来表达？一旦在这两种情况下都给出了合适的证明系统，如果“表达”被“证明”取代，这个问题同样有趣。我们可以用其他数学上下文来替换自然数，例如实数、复数等。

仅用常数 0 和一元函数 n↦n+（其中 n+ 表示 n+1），我们就可以用二阶逻辑表达归纳公理

∀X([X(0)∧∀y(X(y)→X(y+))]→∀yX(y)),

的自然数。这与公理 ∀xØ(x+=0) 和 ∀x∀y(x+=y+→x=y) 一起描述了自然数及其后继运算直至同构。在一阶逻辑中，任何具有可数无限模型的理论也具有不可数模型（根据向上 Löwenheim Skolem 定理）。因此(1)不能用一阶逻辑来表达。另一个典型的二阶表达式是实数线性阶 ≤ 的完备性公理：

∀X([∃yX(y)∧∃z∀y(X(y)→y≤z)]→∃z∀y(∃u(X(u)∧y≤u)∨z≤y)),

这与有序域公理一起描述了实数的有序域直至同构。在一阶逻辑中，任何具有无限模型的可数理论也具有可数模型（根据向下洛文海姆斯科勒姆定理）。因此，同样，(2) 不能用一阶逻辑来表达。

对于早期逻辑学家来说，将二阶逻辑与一阶逻辑同等地使用似乎是很自然的，就好像没有太大区别一样。其中包括拉塞尔、勒文海姆、希尔伯特和策梅洛。本质上只有 Skolem 强调了这种差异（参见 Moore 1988 关于一阶逻辑的出现）。 1929 年，哥德尔证明了他的完备性定理，并于次年证明了他的不完备性定理。人们逐渐发现二阶逻辑与一阶逻辑有很大不同。第一个指标是不完整性现象。哥德尔表明，任何有效的数论公理化都是不完整的。另一方面，二阶逻辑中存在一个简单的有限范畴——因此是完整的（§10）——结构（N，+，×）的公理化（另见与（1）相关的讨论）。这表明二阶逻辑不可能像一阶逻辑那样完全公理化。一阶逻辑中众所周知的哥德尔完备性定理根本不适用于二阶逻辑。

当亨金证明关于所谓的一般模型的二阶逻辑的完备性定理时，情况发生了一些变化（§9）。现在，只要记住语义是基于通用模型的，就可以像一阶逻辑一样使用二阶逻辑。二阶逻辑表征同构数学结构的能力并不能扩展到一般模型（除了内部范畴的形式——参见§10）。任何二阶理论，在可数词汇中，具有无限一般模型，都具有所有无限基数的一般模型，因此在一般模型的背景下不能是绝对的。我们将在第 9 节中讨论一般模型和相关的 Henkin 模型。

2. 二阶逻辑的语法

二阶逻辑中的词汇就像一阶逻辑中的词汇一样，即关系、函数和常数符号的集合L。每个关系和函数符号都有一个元数，它是一个正自然数。

二阶逻辑有多种变量。它具有用小写字母 x、y、z、… 表示的各个变量，可能带有下标。它具有由大写字母 X、Y、Z、... 可能带有下标表示的属性和关系变量。最后，它具有用大写字母 F、G、H、… 表示的函数变量，可能带有下标。有时函数变量会被省略，因为毕竟函数是特殊类型的关系。每个关系和函数变量都有一个元数，它是一个正自然数。我们用一元关系变量来识别属性变量。

值得注意的是，虽然我们有属性变量，但我们没有属性的属性变量。这些变量将是三阶逻辑形式主义的一部分，参见§12。

二阶逻辑的项递归地定义如下： 常数符号和单个变量是项。如果 t1,…,tn 是项，U 是 n 元函数符号，F 是 n 元函数变量，则 U(t1,…,tn) 和 F(t1,…,tn) 是项。请注意，术语表示个人，而不是关系或财产。因此 X 本身不是一个项，但 x 是一个项。

二阶逻辑的原子公式由项定义如下： 如果 t 和 t′ 是项，则 t=t′ 是原子公式。如果 R 是 n 元关系符号，t1,…,tn 是项，则 R(t1,…,tn) 是原子式。如果 X 是 n 元关系变量，则 X(t1,…,tn) 也是原子公式。 X(t1,…,tn) 的直观含义是元素 t1,…,tn 位于关系 X 中或由 X 谓词。我们不允许 X=Y 形式的原子公式，尽管它们会有一个明显的意思。我们通过使用量词达到同样的效果。

定义1 二阶逻辑公式定义如下： 原子公式是公式。如果 ψ 和 ψ 是公式，则 ψ 、 ψ ∧ ψ 、 ψ ∨ ψ 、 ψ → ψ 和 ψ ↔ ψ 也是公式。如果 phi 是公式，x 是单个变量，X 是关系变量，F 是函数变量，则 ∃xphi、∀xphi、∃Xphi、∀Xphi、∃Fphi 和 ∀Fphi 是公式。

有趣的是，在二阶逻辑中，我们实际上可以将恒等式 t=t′ 定义为∀X(X(t)↔X(t′))，并根据蕴涵的性质证明熟悉的恒等公理。

一个重要的特殊情况是一元二阶逻辑，其中不允许使用函数变量，并且关系变量必须是一元（也称为一元），即元数为一。

我们没有将 X=Y 作为原子公式（尽管我们可以），但引入了我们可以使用的量词

∀x1…∀xn(X(x1,…,xn)↔Y(x1,…,xn))

作为 X=Y 的替代。将 X=Y 作为基本原子公式的优点是使用 (3) 会带来额外的量词。有时，最小化公式中量词的数量很有趣。此外，(3) 赋予恒等式 X=Y 一种外延风味，与可能不同的内涵解释相反。

公式中变量的自由出现和绑定出现的概念以通常的方式定义。如果一个公式没有自由变量，则它被称为一个句子。公式中的项对于变量而言是自由的概念被定义为一阶逻辑。

3.二阶逻辑的语义

为了定义二阶逻辑的语义，我们必须就我们的元语言是什么达成一致。这个事实与二阶逻辑无关，而是语义的一般特征（Tarski 1933 [1956]）。二阶逻辑最常用的元语言是集合论。因此，我们给出了二阶逻辑的集合论解释，将“属性”解释为本身就是集合的域中的集合。这是最常见的选择，并体现了二阶逻辑的主要特征。我们不能用集合来解释所有属性，例如与自己相同的属性。但是，如果将单个变量范围内的域视为一个集合，那么我们可以有意义地将该域中的个体属性解释为集合。如果我们想要解释一个太大而不能成为集合的域中的二阶逻辑，我们可以使用类的集合论概念（有关类的更多信息，请参阅集合论条目）。

我们使用与一阶逻辑相同的 L 结构（或等效的 L 模型）概念。也就是说，L-结构M有一个域M，它是任何非空集，L的任何常数符号c的解释cM∈M，L的任何n元关系符号R的解释RM⊆Mn，以及任何n元函数符号H或L的解释HM:Mn→M。原则上，域可以是一个类，但我们在这里忽略这种可能性。对于这种情况下集合/类区别的讨论，我们参考 Shapiro (1991, p. 16)。

约定：每当我们使用大写 Fraktur 字母（例如 M、N 等）来命名结构时，我们都会使用这些字母的大写斜体版本（例如 M、N 等）来命名结构的域。

给定 L 结构 M，赋值是从变量到 M 的域 M 的函数 s，使得： 如果 x 是单个变量，则 s(x) ∈ M；如果X是n个关系变量，则s(X)⊆Mn；如果F是n个函数变量，则s(F):Mn→M。我们使用 s(P/X) 来表示赋值，除了 X 处的值已更改为 P 之外，其他情况下为 s。类似地，s(a/x) 和 s(f/F)。

请注意，0 元关系变量本质上是命题。他们对作业的解释是真值（真、假）。 0 元函数变量本质上是单独的变量，因为赋值将 0 元函数符号简单地映射到 M 的元素。0 元关系符号或变量同时是原子公式和非逻辑符号。我们在当前的演示中忽略了这种潜在的符号混乱。

在解释 s 下模型 M 中项 t 的值 tM⟨s⟩ 被定义为一阶逻辑。

现在，可以通过首先定义满足 M 中 phi 的赋值 s 的辅助概念 M⊨sphi 来定义 M 中句子 phi 的真值概念 M⊨ phi （有关更多详细信息，请参阅 Tarski 真值定义的条目）：

定义 2（塔斯基的真值定义）二阶逻辑的真值定义通过以下子句扩展了一阶逻辑的相应真值定义：

M⊨sX(t1,…,tn) 当且仅当 (t

中号

1

⟨英石

中号

n

⟨s⟩)∈s(X)，如果 X 是 n 元。

M⊨s∃Xphi 当且仅当 M⊨s(P/X)phi 对于某些 P⊆Mn，如果 X 是 n 元。

M⊨s∃Fphi 当且仅当 M⊨s(f/F)phi 对于某些 f:Mn→M，如果 F 是 n 元。

对于全称量词也是如此。对于句子 phi，我们定义 M⊨phi 来表示所有（等价的）s 的 M⊨sphi，然后说 phi 在 M 中为真。

在上述定义的第 1 条中，我们遵循对谓词 X(t1,…,tn) 给出集合论解释的常见做法。将 X 解释为 Mn 的子集后，我们将谓词 X(t1,…,tn) 解释为隶属度 (t

中号

1

⟨英石

中号

n

⟨s⟩)∈s(X)。在第 2 条中，我们将对属性和关系的量化解释为对笛卡尔积 Mn 的子集的量化。分别地，在第 3 节中，我们将函数的量化解释为集合论意义上的函数 Mn→M 的量化。

现在已经定义了二阶逻辑的语义，我们可以定义公式 ψ 有效以及两个公式 ψ 和 ψ 逻辑等价的含义。与一般逻辑一样，如果 M⊨sphi 对于所有 M 和所有 s 都成立，则 phi （逻辑上）有效。同样，如果 ψ↔ψ 有效，我们将 ψ 和 ψ 定义为逻辑上等价的 ψ ψ ψ 。两个模型 M 和 N 被称为二阶等价，在符号 MeqL2N 中，如果对于所有句子 ψ 我们有 M⊨ψ⟺N⊨ψ。

真值定义涉及“对于某些 P⊆Mn”和“对于某些 f:Mn→M”的概念。由于我们假设集合论作为我们的元语言，因此我们可以在集合论的意义上解释它们。因此，我们将“对于某些 P⊆Mn”解释为“对于某些集合 P⊆Mn”，而“对于某些 f:Mn→M”解释为“对于某些作为函数 f:Mn→M 的集合”。

对于无限 M，Mn 的子集集合和函数 Mn→M 的集合是出了名的复杂。目前集合论（ZFC）甚至无法决定无限集合有多少个子集。这种情况与一阶逻辑完全不同。相对而言，“对于某些a∈M”的相应概念是没有问题的。当然，根据 M 是什么，“对于某些 a∈M”也可能是相当有问题的。为了反映寻找 P⊆Mn 或 f:Mn→M 所涉及的困难，我们有时会说我们“猜测”P⊆Mn 或 f:Mn→M。

当我们使用集合论作为一阶逻辑语义的元理论时，对元理论的依赖程度低于我们使用集合论作为二阶逻辑语义的元理论时。解释这种差异的核心概念是绝对性。详情请参见§6。

3.1 二阶逻辑的 Ehrenfeucht-Fraïssé 博弈

Ehrenfeucht-Fraïssé 博弈是一种博弈论工具，用于研究两个模型的相似程度（有关 Ehrenfeucht-Fraïssé 博弈的一般介绍，请参阅逻辑和博弈条目）。两个同构模型会非常相似，但通常我们感兴趣的是非同构模型的相似性。二阶逻辑的 Ehrenfeucht-Fraïssé 博弈表征了 A≡L2N，即完全相同的二阶句子在 A 和 B 中为真命题，正如一阶逻辑的 Ehrenfeucht-Fraïssé 博弈表征了一阶初等等价A=N。有关初等等价的更多信息，请参阅一阶模型理论条目。

为了简单起见，我们在本节中不允许使用函数和常量符号以及函数变量。假设 A 和 B 是同一有限关系词汇表的两个模型。在我们用G表示的游戏中

2

n

(A,B) 两个玩家 I 和 II 一次选择一个 A 的子集（或元素）或 B 的子集（或元素）。在游戏玩家的第 i 轮中，我可以选择 A 上的关系 Ai（或元素） A 的 ai），然后玩家 II 必须选择 B 上与 Ai 相同数量的关系 Bi（或 B 上的元素 bi），反之亦然：玩家 I 可以选择 B 上的关系 Bi（或元素 bi） B) 然后 II 选择一个关系A 上的 Ai 与 A 的 Bi（或元素 ai）具有相同的数量。n 轮后，所玩的元素对 (ai,bi) 在 A×B 上形成二元关系 R。如果这个关系是由所玩的关系 Ai 和 Bi 扩展的结构 A 和 B 的部分同构，即它保留了原子公式及其否定，我们就说 II 赢了。模型 A 和 B 满足相同的二阶句子当且仅当对于每个 n∈N 玩家 II 在 G 中有获胜策略

2

n

（A，B）。模型类（即固定词汇表的模型类，在同构下封闭）K 在二阶逻辑中是可定义的，当且仅当存在一个 n，使得 A ∈ K 且玩家 II 在 G 中具有获胜策略

2

n

(A,B)，则B∈K。

一阶G版

1

n

(A,B)，其中玩家仅玩单个元素，即不玩任何关系，这对于处理一阶逻辑非常有用。不幸的是游戏G

2

n

（A，B）要复杂得多。除了A≅B这种微不足道的情况外，为玩家II发明获胜策略是非常困难的。如果玩家 I 在 A 上玩二元关系 R，则玩家 II 应该能够在 B 上玩二元关系 R′，这样无论玩家 I 在游戏的其余部分中提出什么挑战，甚至涉及新的二元关系，关系 R 和 R ' 看起来很相似。如果 V=L，则可数二阶等效模型（具有有限词汇量）实际上是同构的（Ajtai 1979）。有关详细信息，请参阅第 10 节。因此，在可数模型中，除了同构之外，玩家 II 没有其他获胜策略。也许这解释了为什么游戏在二阶逻辑中不如在一阶逻辑中那么有用。然而，如果我们限制为一元二阶逻辑，就 Ehrenfeucht-Fraïssé 博弈而言，这意味着将博弈限制为一元谓词，情况就会发生变化。一元谓词只是将模型分为两部分。如果玩家I将A分成两部分，玩家II应该在B中找到类似的划分。这样更合理，并且对于玩家II来说实际上有有用的策略。有关有限上下文中的示例，请参阅第 16 节。

4. 二阶公式的性质

我们在一阶逻辑中习惯的许多语法操作在二阶逻辑中同样有效。其中之一就是相对化运算，我们希望将公式所表达的内容限制在宇宙的固定部分。例如，我们可以考虑将某个一元谓词 U 用于自然数集的模型。然后我们将算术公理与谓词 U 相对化。模型的某些其他部分可以用于自然数集的幂集。然后我们将幂集公理（参见第 5.3 节）与该部分相对化，依此类推。

如果 M 是结构且 A⊆M，则 MA 是通过将关系 RM 和函数 FM 限制到 A 来获得的。这并不总是会产生结构，但如果确实如此，则称为 M 到 A 的相对化。假设 phi = phi(x1,…,xn,X1,…,Xm,F1,…,Fk) 是二阶公式，U 是一元关系变量。有一个二阶公式 phiU，即 phi 与 U 的相对化，使得对于所有 MUM 为结构的 M：

M⊨ΦU⟺MUM⊨Φ。

直观上， ΦU 表示 UM，就像 Φ 表示 M 一样。为了从 Φ 获得 ΦU，需要将所有一阶量词限制为 U 的元素，将二阶量词限制为 U 上的子集、关系和函数。