二阶和高阶逻辑（二）

基于量词结构的层次结构是比较不同系统中概念的可定义性的有用方法。在一阶逻辑中，很早就观察到公式可以转化为逻辑上等效的 Prenex 范式，其中所有量词都出现在公式的开头。这在二阶逻辑中也是可能的，并且证明本质上是相同的。此外，使用等价性（这让人想起称为选择公理的集合论原理，我们将在第 5.4 节中返回它），因为在下面的公式中，关系 Y 在某种意义上为每个 x 选择一个 X 并将它们放在一起成一个关系 Y – 有关该主题的更多信息，请参阅选择公理上的条目。）

∀x∃X ψ ∃ Y ∀ x ψ ′,

其中 Y 的元数比 X 的元数高 1，而 phi′ 是通过用 Y(x,t1,…,tn) 替换所有 X(t1,…,tn) 来从 phi 获得的，可以使每一秒-将逻辑公式排序为逻辑等效的范式

Q1X1…QnXnφ,

其中每个 Qi 是 ∃ 或 ∀，并且 phi 是一阶。即公式的所有二阶量词都在前面。

符号 (4) 中的 Qi 为：

Σ

1

1

一切存在主义

Π

1

1

全部通用

Σ

1

2

首先是存在性的，然后是普遍性的

Π

1

2

首先是普遍性的，然后是存在性的

⋮⋮

符号 该公式在逻辑上等价于：

Δ

1

1

两者都是Σ

1

1

和 Π

1

1

公式

Δ

1

2

两者都是Σ

1

2

和 Π

1

2

公式

⋮⋮

表 1：二阶公式的层次结构。

通过限制 Prenex 范式 (4) 的序列 Q1X1…QnXn 可以包含什么样的量词，我们得到 Σ 的类

1

n

-, Π

1

n

- 和 Δ

1

n

-式，如表1所示。例如，二阶公式(1)和(2)为Π

1

1

- 公式。

上面我们只考虑了绑定关系变量的量词，但如果我们绑定了函数变量，情况完全相同。

这些类型的公式具有一些明显的闭包属性：在 ∧、∨ 和一阶量词下，它们都是封闭的，直到逻辑等价。此外，层次结构是正确的，因为对于所有 n≥1

Σ

1

n

⊈Π

1

n

和 Π

1

n

⊈Σ

1

n

,

这可以用对角化论证来证明。类别 Δ

1

n

在 ∧、∨、Ø 和一阶量词下是封闭的。根据克雷格插值定理，Δ

1

1

- 公式在逻辑上等价于一阶公式 [2]。

从某种意义上说，Π

1

1

，或等效的 Σ

1

1

，已经具有二阶逻辑的全部能力，尽管上面的层次结构结果（5）表明这实际上不可能是真的。看看这个，即看看二阶逻辑约简到它的 Π 是怎样的

1

1

-part 表示，设 L 为词汇表，E 为二元关系符号，U 为一元关系符号，两者都不在 L 中。设 θ 为二阶 Π

1

1

-公式

∀X(Φ1∧Φ2∧Φ3),

在哪里

ψ1 为 ∀x∀y(∀z(E(z,x)↔E(z,y))→x=y)

phi2 是 ∀x∀y(E(x,y)→(U(x)∧ØU(y)))

ψ3 是 ∀x(X(x)→U(x))→∃y∀z(X(z)↔E(z,y))。

很容易看出[3] θ 的模型在同构上是模型 M，其中 M=UM∪P(UM), UM∩P(UM)=∅ 并且对于所有 a,b∈M, EM(a ,b)↔a∈b.在这样的模型中，UM 上的一元二阶公式 ψ 可以简化为 M 上的一阶公式 ψ*。这种简化由 Hintikka (1955) 提出并由 Montague (1963) 进一步发展，表明 Π

1

1

- 单独的公式足以表达带有额外谓词的任何二阶属性。这个想法可以扩展到三阶和更高阶逻辑，也可以扩展到非一元二阶逻辑。

因此，检查二阶句子 的有效性可以递归地简化为检查 Σ 的有效性

1

1

-句子 θ → ψ 。同样，检查二阶句子 是否有基数 κ 的模型可以简化为询问 Π 是否

1

1

-句子 θ∧phi* 具有基数 2κ 的模型。这意味着整个二阶逻辑的洛文海姆数[4]和汉夫数[5]与片段Π的洛文海姆数[4]和汉夫数[5]相同

1

1

。

总结一下，在第一次检查时，水平 Σ

1

n

和 Π

1

n

随着 n 的增加，二阶公式的层次结构的表达能力严格增长，但更仔细的分析表明，第一级 Σ

1

1

∪Π

1

1

拥有所有级别的力量 Σ

1

n

,Π

1

n

即使这种力量有些隐秘并且需要被曝光。

在集合论中，存在 Σn 和 Πn 公式的 Levy 层次结构（Lévy 1965）。所有量词都有界的公式，即对于某些 x 和 y，形式为 ∀x∈y 或形式 ∃x∈y，称为 Σ0 或等效的 Π0。 ∀xphi 形式的公式称为 Πn+1，其中 phi 是 Σn。 ∃xphi 形式的公式称为 Σn+1，其中 phi 为 Πn。这是一个严格的层次结构，大致与二阶 Σ 的层次结构相同的原因

1

n

- 和 Π

1

n

- 公式很严格。但没有已知的方法可以将任意公式的真实性简化为 Σ1∪Π1 级别上公式的真实性。事实上，如果将决策问题、Löwenheim-Skolem 数和 Hanf 数适当地定义为集合论的 Σn∪Πn-公式，则决策问题会变得越来越复杂，并且随着 n 的增加，获得的数字也越来越大（参见定理 4；Väänänen 1979）。

层次结构Σ

1

n

∪Π

1

n

二阶逻辑内部和集合论中的层次结构 Σn∪Πn 在第 7 节中进一步相互比较。

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

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

二阶逻辑具有一些显着的特性，我们现在将详细揭示它们。上面我们用式（1）来表征自然数的结构。二阶逻辑的这种应用也许是最著名和最重要的。我们现在以稍微更通用的形式重新表述它，以便从中获得更多的力量。假设 U 是一元关系变量（“自然数集”），G 是一元函数变量（“后继函数”），z 是单个变量（“零”）。设 θPA(U,G,z) 为句子

U(z)∧

∀x(U(x)→(U(G(x))∧ØG(x)=z))∧

∀x∀y((U(x)∧U(y)∧G(x)=G(y))→x=y)∧

∀X([X(z)∧∀x((U(x)∧X(x))→X(G(x)))]→

∀x(U(x)→X(x))),

那么 (N,A,g,a)⊨θPA(U,G,z) 当且仅当 (N,A,g,a) 同构于结构 (M,N,s,0)，其中 N⊆M并且s(n)=n+1。因此，我们使用二阶逻辑来表示 θPA(U,G,z) 的任何模型的 U 部分以及函数 G 和个体 z 与自然数 N 及其后继函数和零同构。有很多方法可以看出没有一阶句子可以具有此属性。例如，根据紧致定理，这样的句子也将具有非标准模型，其中某些元素与序列 z、G(z)、G(G(z))、G(G(G(z) ））），……这样的模型不能与自然数 N 及其后继函数和零同构。由此我们可以得出结论，紧致性定理对于二阶逻辑并不像它对于一阶逻辑的形式那样成立。

在 θPA(U,G,z) 模型中，公式 θ+(U,G,z,H)

{

∀x(U(x)→H(x,z)=x)∧

∀x∀y(U(x)→(U(y)→H(x,G(y))=G(H(x,y))))

以及公式 θ×(U,G,z,H,J)

{

∀x(U(x)→J(x,z)=z)∧

∀x∀y(U(x)→(U(y)→J(x,G(y))=H(J(x,y),x)))

定义唯一函数 m+n=H(m,n) 和 m⋅n=J(m,n)。算术的一阶句子 phi(+,⋅,0) 在 (N,+,⋅,0) 中为真当且仅当

∀U∀G∀z∀H∀J((θPA(U,G,z)∧θ+(U,G,z,H)∧θ×(U,G,z,H,J))→(ψ (H,J,z))U)

是有效的。根据 Gödel (1931 [1986: 144–195]) 和 Tarski (1933 [1956]) 的结果，我们知道 (N,+,⋅,0) 中的一阶句子的真值是不可判定的，甚至是不可算术的。这表明二阶逻辑不能通过有效手段完全公理化，甚至在空词汇中也不能确定。也就是说，不存在可判定的具有无限模型的二阶理论。这与一阶逻辑形成鲜明对比，其中以下理论是可判定的：具有空词汇的一阶逻辑、具有一元谓词的一阶逻辑、稠密线性顺序、Pressburger算术（(N,+,0)的一阶理论）、实闭域（(R,+,⋅,0,1) 的一阶理论）、代数闭域理论和 (C,+,⋅,0,1) 的一阶理论。在二阶逻辑中，没有一个相应的二阶理论是可判定的。然而，如果我们将二阶逻辑限制为一元二阶逻辑，我们将获得许多重要的可判定理论（参见§8）。

5.2 完备性定理的崩溃

完备性定理是我们理解一阶逻辑的基石之一。此外，一阶逻辑的许多扩展都有完备性定理，最显着的是通过广义量词“有不可数的多”和无限语言 Lω1ω 对一阶逻辑的扩展。现在我们将看到二阶逻辑没有完备性定理的希望。稍后在第 9.1 节中，我们将修改语义，以便可以证明完整性定理。

完备性定理失败的背后是这样一个事实：二阶逻辑——几乎根据定义——能够说一个集合是另一个集合的幂集。这意味着：设 L 为词汇表。令e为二进制，u是一个单一的关系符号，两者都不是在L中。让θpow（u，e）为二阶公式（6）。让我们考虑连词

θpa（u，g，z）∧θpow（u，e）。

该公式的模型是形式（m，∈，n，g，a）的同构，其中p（n）= m，n∩p（n）=∅和n是无限的。因此，模型必然是不可数的。这表明，与一阶逻辑不同，二阶逻辑具有带模型的句子，但仅具有无数的逻辑。因此，正如我们已经提到的那样，向下löwenheim-skolem定理的二阶逻辑失败了。 （8）与第5.1节中的观察结果结合得出以下结果（根据有效性，是指有效公式的Gödel数量集）：

定理3（Hintikka 1955; Montague 1963）在二阶逻辑中的有效性在（N，+，×，0）上不能定义。

因此，二阶逻辑中的有效性不是σ

1

n

对于任何n。由于可以迭代以θpow（u，e）风格的构建功率集，因此我们可以看到二阶逻辑中的有效性不是σ

米

n

对于任何M和N。我们将此结果进一步扩展到定理6中。

5.3“绵羊衣服的理论”

二阶逻辑隐藏在其语义中，这是设定理论的一些最困难的问题。用Resnik（1988：75）的话说：

W. V. Quine在逻辑哲学[Quine 1970]中，总结了数学逻辑学家的流行观点，将二阶逻辑称为“绵羊服装中的固定理论”。

让我们看看这种观点可能来自哪里。首先，我们观察到一个非常简单的，确实是一个非常基本的二阶公式可以说两组具有相同的基数：假设p和r是一致关系变量。令θ≤（p，r）为公式

∃F（∀X∀Y（（f（x）= f（y）→x = y）∧（p（x）→r（f（x））））。

现在，仅当| s（p）|≤| s（r）|时，现在m⊨sθ≤（p，r）。令θeq（p，r）为公式θ≤（p，r）∧θ≤（r，p）。现在，当且仅当| s（p）| = | s（r）|时，现在m⊨sθeq（p，r）。令θ

′

欧共体

（r）是

∃f∀x∀y（（f（x）= f（y）→x = y）∧r（f（x）））。

现在m⊨sθ

′

欧共体

（r）且仅当集合M和S（R）具有相同的基数。我们将使用这些公式对Continuum假设发动攻击，这是臭名昭著的理论问题，是Cohen于1963年与ZFC无关的（Cohen 1966）。

令θch为句子

∃e∃u∃g∃z（θpow（e，u）∧θpa（u，g，z）∧∀y（θ

′

欧共体

（y）∨θ≤（y，u））。

现在，θch是空词汇的一个句子，当且仅当连续假设CH成立时，才具有模型。类似地，有一个句θ-在且仅当连续假设CH不起时才具有模型。这表明，二阶逻辑语义对元评估集理论的依赖性是如此之深，以至于ZFC无法解决的问题也可以确定模型中句子的真实性或虚假性。

二阶逻辑的奇怪质量是，在足够大的空词汇模型中，诸如θch之类的句子的真实性等于固定理论宇宙中连续假设的真相。通过相同的技术，几乎所有设定的理论陈述都可以变成二阶逻辑的句子，在足够大的空词汇模型中的真相相当于集合理论宇宙中陈述的真相。以某种方式，二阶逻辑可以正确读取背景集理论。这是否意味着二阶逻辑是在“绵羊的服装”中设定的理论？

5.4二阶逻辑是否取决于选择的公理？

选择的公理（AC）是数学基础中的哲学难题。粗略地说，这个最初在集合理论中出现的公理说，如果我们有一组非空的脱节集，那么我们可以形成一个新的集合B，它包含来自A中每个集合的一个元素。被视为一个问题，是一个事实，当A是无限的，形成集合B似乎需要做出无限数量的选择。有关全面的定义和讨论，请参见“ Axiom”选择的条目。一方面，选择的公理似乎是神奇的，例如，当它暗示最疯狂的套装有井井有条时。另一方面，这似乎是无害的，例如，当它暗示着一个非空套家族的笛卡尔产品是非空的。选择的公理通常用于构造奇数“矛盾”集，例如非lebesgue可测量的实数集，实数的顺序良好，是球体的矛盾分解（请参阅集合理论的输入），等等。这种集合通常在某种意义上是不确定的。例如，如果有足够大的红衣主教，则必须在二阶逻辑（n，+，走气）中不可定义的一组实数集（请参阅大型红衣主教的条目和确定性）。

选择的令人困惑的公理也出现在二阶逻辑的中间：让θ为句子

∀X（∀X∃YX（X，Y）→∃F∀XX（x，f（x）））。

然后r⊨θ基本上说，如果二进制关系x与每个x∈R相关x布一个非空置{y∈R：x（x，y）}，则有一个函数f，为每个x∈R选择一个x∈R y = f（x），使得x（x，y）。在集合理论中，这是众多选择的方法之一，即选择的公理适用于R的（连续大小）子集的族。二阶逻辑的基本原则是存在固定域元素的“所有”特性我们可以对它们进行量化。用设定的理论术语，这意味着存在一组基数的所有子集存在是否存在，我们可以对其进行量化。本着这种精神，选择的公理似乎是无辜的，通常在二阶逻辑文献中被接受。

根据科恩（Cohen）的结果（1966年），有n和n'满足ZF的公理（没有选择的公理），因此“n⊨θ”在n中保存，但在n'中不存在。这进一步证明了二阶逻辑语义对元心理的依赖性。

6。二阶逻辑中真相的不含量

绝对性是最重要的逻辑概念之一。戈德尔（Gödel）在1939年已经使用了它在分析可构造集的层次结构（1939 [1990：46]），以证明连续假设的一致性。戈德尔三年前就与计算性概念有关（1936 [1986：397]）的简短提到。

从直觉上讲，如果其含义独立于所用的形式主义，或者换句话说，如果其在形式意义上的含义与“现实世界”中的含义相同，则是绝对的。这听起来很模糊和不精确。但是，绝对性在集合理论中具有完全确切的技术定义。

回想一下，如果a的每个元素都是a的元素，则a a称为传递。传递模型是一个模型（m，∈），因此m是传递的。通过Mostowski崩溃的引理（Mostowski 1949），延伸性公理的每个有良好的模型（M，E）与独特的传递模型都是同构的。传递模型（m，∈）的基本属性是，如果a，b∈M，则仅在a⊆b时，则是m⊨a⊆b。 （如果M中的A中的所有元素都在B中，则A的所有元素都在B中，如M的传递性，A的元素是M的元素。在传递模型中是绝对的。更普遍地，我们说集合理论的一阶语言的公式ϕ（x1，…，xn）是绝对相对于ZFC的，如果有有限的t⊆ZFC，则对于所有t的所有传递模型（m，∈），和所有a1，…，an∈M我们有

ϕ（a1，…，an）当且仅当（m，∈）⊨ϕ（a1，…，an）时。

绝对性的这种定义等效于以下更多的句法条件（Feferman＆Kreisel 1966）：有一个σ1-formula∃Y单ψ（y，x1，…，…，xn）和一个π1-formula∀yθ（y，x1，…，…，… xn）这样

ZFC⊢∀X1…∀Xn（ϕ（x1，…，xn）↔∃Yψ（y，x1，…，xn））

和

Zfc⊢∀x1…∀xn（ϕ（x1，…，xn）↔∀yθ（y，x1，…，xn））。

在这种情况下，我们说ϕ（x1，…，xn）为Δ

ZFC

1

。

对于一阶逻辑，可以证明“m⊨sc”是M，S和ϕ相对于ZFC的绝对属性。实际上，即使ZFC被较弱的kripke-platek集理论KP取代，这也是如此（参见Barwise 1972a）。一阶逻辑的通常Tarski真相定义可以用δ编写

ZFC

1