二阶和高阶逻辑（五）

如果 \phi 是一个二阶句子，我们上面将 \Mod(\phi) 定义为类 \{\mm : \mm\models\phi\}。如果 \phi 表征 \mm 直至同构，则直至同构，

\Mod(\phi)=\{\mm\}。

用二阶句子公理化数学结构的项目在二十世纪上半叶非常成功，以至于卡尔纳普（Carnap）甚至在 Fraenkel（1919 [1928]）的启发下提出，有关这方面的更多信息，请参阅 Awodey 和 Reck 2002，每个数学结构由其二阶理论决定，直至同构。由于一些微不足道的基数原因，这不可能适用于所有大小为 2^\omega 及更大的模型。与非同构模型的数量相比，二阶理论根本不够。然而，卡尔纳普的提议对于有限模型来说是非常正确的，对于可数模型来说并非完全不合理。事实上，Ajtai（1979）表明，如果 ZFC 本身是一致的，那么有限词汇表中满足相同二阶句子的任何两个可数结构都是同构的，这与 ZFC 是一致的。 Ajtai证明，如果ZFC本身是一致的，那么在有限词汇表中有两个可数结构满足相同的二阶句子而不是同构，它也与ZFC一致。因此，卡尔纳普的猜想（对于可数模型）与 ZFC 无关。

Solovay 在 FOM（2006 [其他互联网资源]）中发表了一篇文章，其中他表明每个完整的二阶句子都是绝对的相关陈述，与 ZFC 无关。 Saarinen、Väänänen 和 Woodin（2024 [其他互联网资源]）表明，大基数，至少直到超紧凑基数，无法决定是否每个完整的二阶句子都是分类的，

在重要情况下，有一种强范畴性形式适用于 Henkin 结构，并且与完整 Henkin 模型情况下的通常范畴性概念一致。它建立在二阶逻辑表达其自身范畴的卓越能力之上。两个结构 (M,R) 和 (M',R') 的同构 (M,R)\cong(M',R') 可以表示为：二阶逻辑如下，设 \ma=(A,M,M',R,R')，其中 A 是包含 M\cup M', M=U^\ma, M'={U' 的任意集合}^\ma, R=P^\ma 和 R'=P'^\ma。现在

(M,R)\cong(M',R')\iff\ma\models\isom(U,P,U',P'),

其中 \isom(U,P,U',P') 是句子

\begin{align} &\exists F[ \forall x(U(x)\to U'(F(x))) \land {}\\ &\quad \forall x\,\exists y ( U'( x)\to ( U(y)\land x=F(y) ) ) \land {}\\ &\quad\forall x\,\forall y( ( U(x) \land U(y)) \到{}\\ &\quad[ (F(x)=F(y)\to x=y) \land {}\\ &\quad(P(x,y)\leftrightarrow P'(F(x),F(y) )) ] ) ]。 \结束{夕阳}

这表明带有二元谓词符号 P 的句子 \theta(P) 的类别可以等效地重新定义，[18] 令 \categ(\theta(P)) 为句子

\forall P\,\forall P'\,\forall U\,\forall U'\left(\left(\theta(P)^{U}\land\theta(P')^{U'}\right )\to\isom(U,P,U',P')\right),

作为

\tag{12}\label{redef}\models\categ(\theta(P))。

事实上，这就是 Tarski 在 Tarski (1956)（第 387 页）中定义类别的方式。这导致我们定义：

定义 15 我们说 θ(P) 是内分类的，如果

\tag{13}\label{内部}\vdash\categ(\theta(P))。

内部范畴也可以称为可证明范畴。 “内部范畴性”一词是在 Walmsley (2002) 的算术背景下引入的。 Väänänen (2012) 更普遍地提倡这一点，Väänänen 和 Wang (2015) 更详细地阐述了这一点。我们参考了 Button 和 Walsh（2016）以及 Maddy 和 Väänänen（2023）最近关于这一概念的讨论。

请注意，(\ref{internal}) 比 (\ref{redef}) 更强，因为可证明的句子当然是有效的。由于完备性定理，我们可以将 (\ref{internal}) 重写为

\tag{14}\label{internals} (\ma,\G)\models\categ(\theta(P))\text{ 对于所有 Henkin 模型 $(\ma,\G)$}。

因此，内部分类不仅意味着普通模型（即完整的 Henkin 模型）的分类，而且意味着任意 Henkin 模型内部的分类。请注意，类别是一个元理论概念，因为它指的是二阶逻辑的语义。在 \categ(\theta(P)) 中，\theta(P) 的范畴是用二阶逻辑语言编写的。也就是说，尽管范畴性是一个元理论概念，但却是用对象语言编写的。有人会问，这是否会导致我们产生不同的概念？尽管如此，当通过考虑元理论中的语义来揭示 \categ(\theta(P)) 的含义时，其含义与我们赋予 \theta(P) 的范畴性的含义相同在内部范畴性的概念中，我们通过从语义意义切换到证明理论意义来利用这种情况：我们坚持认为 \categ(\theta(P)) 是（不仅有效而且甚至）可证明的。证明理论比语义需要更少的元理论。即使在数论中，我们也可以通过使用数字来编码句子和证明来研究二阶句子的可证明性，就像哥德尔在证明不完备性定理中所做的那样。当然，完备性定理让我们回到了语义。

为了验证二阶句子的范畴性，我们必须以一种本质上需要集合论的方式经历无限的结构。内部范畴的情况则不同。要验证二阶句子的内部范畴性，只需提供一个证明。所以这是一个巨大的差异。而且内部范畴性仍然比范畴性更强。因此，如果一个人能够建立内在的范畴，那么建立范畴就是愚蠢的。幸运的是，分类句子的经典例子都是内部分类的：

定理 16 (Väänänen & Wang 2015) 接收到的表征结构 (\oN,＜) 和 (\oR,＜,+,\cdot,0,1) 的二阶句子是内部分类的。

内部范畴的概念提供了完整语义和 Henkin 语义之间的桥梁。它在两种情况下都以相同的方式工作，并表明完整的语义是 Henkin 语义的极限情况，但在分类方面并不具有垄断性。

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

一阶逻辑和二阶逻辑在某种意义上是两个相反的极端。它们之间有许多逻辑，即适当扩展一阶逻辑并适当包含在二阶逻辑中的逻辑。一个例子是通过称为 Henkin 量词的广义量词对一阶逻辑的扩展：

\left( \begin{array}{cc} \forall x&\exists y\\ \forall u&\exists v \end{array}\right)\phi(x,y,u,v,z_1,\ldots,z_n ）

这有什么意义

\存在f\，\存在g\，\对于所有x\，\对于所有u\，\phi(x，f(x)，u，g(u)，z_1，\ldots，z_n)。

Henkin 量词对一阶逻辑的外延 L(H) 几乎与二阶逻辑相同：它们具有相同的 Delta 外延 (Krynicki & Lachlan 1979)。 [19]

等基数或 Härtig 量词

Ixy\,\phi(x,z_1,\ldots,z_n)\psi(x,z_1,\ldots,z_n)

其含义是“满足 \phi(x,z_1,\ldots,z_n) 的元素 x 与满足 \psi(y,z_1,\ldots,z_n) 的元素 y 一样多”，即

\begin{align} &\存在 f[\forall x (\phi(x,z_1,\ldots,z_n)\leftrightarrow\psi(f(x),z_1,\ldots,z_n)) \land {}\\ &\quad\forall x\,\forall y((\phi(x,z_1,\ldots,z_n)\land \phi(y,z_1,\ldots,z_n)\land f(x)=f(y))\to x=y) \land {}\\ &\quad\forall y\,\存在 x(\psi (y,z_1,\ldots,z_n)\to (\phi(x,z_1,\ldots,z_n)\land f(x)=y)) ] \end{对齐}

Härtig 量词对一阶逻辑的外延 L(I) 比二阶逻辑弱[20]，因为它的 Löwenheim 数可以 ＜2^\omega，但如果 V=L，则 Delta 等价于二阶逻辑（Väänänen 1980，Väänänen 和 Welch 2023）。有关 L(I) 的更多信息，请参阅 Herre、Krynicki、Pinus 和 Väänänen (1991) 以及 Magidor 和 Väänänen (2011)。

以下是一些其他显然可以二阶定义的广义量词：

\begin{align} Q_0x\,\phi(x,z_1,\ldots,z_n)& \iff\exists X( |X|\ge\aleph_0 \land \forall x\in X\phi(x,z_1,\ ldots,z_n) )\\ Q_1x\,\phi(x,z_1,\ldots,z_n)&\iff\存在 X( |X|\ge\aleph_1 \land{} \forall x\in X\phi(x,z_1,\ldots,z_n) )\\ Q^{MM}_1xy\,\phi(x,y,z_1,\ ldots,z_n)&\iff\存在 X( |X|\ge\aleph_1 \land{} \forall x,y\in X\phi(x,y,z_1,\ldots,z_n) )\\ Q^{cof}_\omega xy\,\phi(x,y,z_1,\ldots,z_n)&\iff \{(x ,y):\phi(x,y,z_1,\ldots,z_n)\} \\ & \qquad\qquad\text{ 是共尾性的线性阶 } \omega \结束{对齐}

在弱二阶逻辑中，我们没有函数变量，关系变量仅在有限关系范围内。由此产生的逻辑在很多方面类似于广义量词 Q_0 对一阶逻辑的扩展。限制二阶逻辑能力的另一种方法如下：假设 \psi 是具有 n 元关系变量 X 并且没有非逻辑符号的一阶公式。对于无限 A，我们定义 \ma\models_s Q_{\psi}X\phi 当且仅当存在关系 P\subseteq M^n 使得 \ma\models_{s(P/X)}\phi\land \psi。量词 Q_{\psi} 允许对满足 \psi 的关系进行二阶量化。如果 \psi 是 \forall x(x=x)，我们就得到通常的二阶量词，记为 Q_{II}。此外，如果 n=1，我们获得一元二阶量词，表示为 Q_{mon}。如果 n=1 且 \psi 表示 X 是单例，我们就获得通常的一阶量词，现在将其表示为 Q_I。最后，如果 \psi 表示 X 是模型的排列图，我们用 Q_{1-1} 表示这个量词。令人惊讶的是，事实证明，在可解释性的正确概念下，量词 Q_I、Q_{mon}、Q_{1-1} 和 Q_{II} 是唯一具有双向可解释性的二阶量词 Q_{ \psi}（Shelah 1973）。

12. 高阶逻辑与类型理论

有很多方法可以进一步扩展二阶逻辑。最明显的是第三、第四等顺序逻辑。 Tarski（1933 [1956]）已经认识到的一般原则是，在高阶逻辑中，我们可以形式化低阶逻辑的语义（定义真理）。因此，通过使用高阶逻辑，人们肯定会获得表达能力。让我们以数论为例。通过一阶逻辑，我们可以表达诸如“n是素数”之类的属性以及诸如“素数有无限多个”、费马大定理和哥德巴赫猜想之类的命题。自然数的一阶属性属于称为算术层次结构的自然层次结构，其级别表示为 \Sigma^0_n 和 \Pi^0_n。通过二阶逻辑，我们可以讨论自然数集的属性，或者换句话说，实数的属性。特别是，我们可以定义有理数。实数上的连续函数由其有理数上的值确定。此外，开集是由它包含的有理点决定的。利用这些观察结果，我们可以讨论连续函数和开实数集。微积分中的基本事实，例如博尔扎诺定理指出“如果连续函数在区间内具有相反符号的值，则它在该区间内有根”可以用结构上的二阶逻辑来表达 (\oN,+, \cdot) 的自然数。自然数的二阶性质属于称为分析层次结构的自然层次结构，其层次表示为 \Sigma^1_n 和 \Pi^1_n。通过三阶逻辑，我们可以讨论实数集。我们可以用三阶逻辑写出连续统假设，并提出一个难题，即模型 (\oN,+,\cdot) 是否满足这句话。自然数的三阶性质同样具有自然层次结构，其层次表示为 \Sigma^2_n 和 \Pi^2_n。

显然，如果我们保持一个基本模型，例如 (\oN,+,\cdot) 固定，并转向越来越高阶的逻辑，我们可以表达越来越复杂的概念和命题。然而，三阶逻辑超过

\mn_1=(\oN,+,\cdot)

只不过是二阶逻辑而已

\mn_2=(\P(\oN),E,\oN,+,\cdot),

其中 E\subseteq \oN\times\P(\oN) 是关系 nEr\iff n\in r，这也只不过是一阶逻辑

\mn_3=(\P(\P(\oN))),E',\P(\oN),E,\oN,+,\cdot),

其中 E'\subseteq \P(\oN)\times\P(\P(\oN) 是关系 rE'X\iff r\in X。此外，\mn_1 上的二阶逻辑只不过是一阶逻辑当这种思路达到极限时，我们可以看到集合的累积层次结构上的一阶逻辑覆盖了层次结构的任何单个级别 V_\alpha 上的高阶逻辑。在累积层次结构上集合是 \mn_1 之上的非常非常高阶的逻辑。

\mn_2 从 \mn_1 产生的方式和 \mn_3 从 \mn_2 产生的方式有明显的相似性。在这两种情况下，我们只需在模型已有的基础上添加幂集构造即可。正如我们在第 5.3 节中看到的，仅二阶逻辑对于幂集来说非常好。其结果是，从二阶开始的所有高阶逻辑（任何有限阶，直到无限阶）都具有图灵等效的决策问题和相同的 Hanf 和 Löwenheim 数（参见§4）因此，尽管严格来说高于二阶逻辑比二阶逻辑强，但通过表达能力强度的通常标准看不出差异。

类型理论是高阶逻辑的系统方法。变量被分配类型，就像在二阶逻辑中我们有个体类型、关系类型和函数类型的变量一样。在高阶逻辑中，任何较低类型的对象之间的关系变量以及将较低类型的对象映射到较低类型的对象的函数都是有意义的。在集合论中，对象具有等级。集合中元素的等级低于集合本身。但是，集合理论等级和类型理论中的键入之间的差异是，在集合理论中，可以计算出集合时，而在类型理论中可以从对象的变量类型中看到对象的类型是的价值。从某种意义上说，类型理论是从语法中强加了一种类型的每个对象，而在集合理论中，一组具有语义给出的等级。可以说，由于其更简单的语法和语义，因此在1930年代之后的类型理论上获得了主导地位。另一方面，类型理论用于计算机科学，尤其是在编程语言理论中（请参阅类型理论的SEP输入）。

13. 数学基础

数学可以基于集合理论。这意味着数学对象被解释为集合，其属性源自集合理论的公理。集合理论背后的直观非正式图片是，集合和公理的累积层次结构v_ \ alpha（\ alpha a orpha）旨在描述此类集合的基本属性。这种数学的理论基础已在工作数学家中被广泛接受。有关更多详细信息，我们指的是集合理论的SEP条目。设定理论的替代方法至少是类别理论，建设性数学和二阶逻辑。

如果一个人试图跟随逻辑学家，那么数学家在研究中使用语言，人们就会不禁看到他们非常自由地使用二阶概念。例如，毫无疑问，诱导公理是在（\ ref {ind}）中描述的二阶形式中使用的。在他们的自然语言中，数学家会毫不犹豫地使用高级概念，甚至并不总是（需要）知道差异。

作为数学的基础，二阶逻辑集中在数学结构上，而不是数学“对象”，如集理论所做的那样。原则上，每个结构都根据结构的特殊特征具有自己的“基础”。二阶逻辑的作用是为此提供一个共同的框架。结构上二阶逻辑背后的直观非正式图片是，所有n \ in \ in \ in \ in \ on on on on in和in in和in in in in in的所有n \的所有n \ in and a \ in All n \ in All n \ in in All n \ in All n \ in in in的所有n \ in \ in in in的所有n \ in \ in \ on，与A相关的A。与集合理论的非正式图片相比，我们只有子集，关系和功能的领域，而不是诸如集合集，一组集合等的迭代范围，依此类推。因此，二阶逻辑背后的直观图片更简单比集理论背后的图片。特别是，在所有序列上都没有跨越的迭代。数学中使用的大多数结构\ ma具有二阶表征\ theta_ \ ma，请参见第§10。此类结构的证明（二阶）属性\ phi是指从\ theta_ \ ma中得出\ phi。对于这种推导是否应该是使用二阶逻辑的某些（不完整）公理系统的句法（正式）推导的意见，或者是否应该是语义推导（“假设的每个模型”的形式（形式） （结论”）。对于工作数学家而言，没有太大的差异，并且可能会偏爱语义推导。