04 一阶逻辑：表达能力

---

title: 一阶逻辑的表达能力
date: 2024-09-13 02:40:00
categories: 数理逻辑
mathjax: true
katex:
enable: true
allpost: true
copy_tex: true
description: 一阶逻辑的表达能力

---

The Löwenheim-Skolem Theorem

在完备性的证明中，我们用term interpretation $\mathfrak{I}^\Phi$作为interpretation。这告诉我们每个可满足的公式集都可以选取“项的等价类”来作为universe。因此，假设符号集$S$是至多可数的（有限或可数无穷），那么我们有$T^S$是可数的，因此项的等价类大小必定是可数的。这说明一个可数符号集下的公式集一定有一个universe可数的解释，这称为Löwenheim-Skolem定理。

Löwenheim-Skolem定理似乎只是term interpretation的一个平凡推论，但它却显示出了一阶逻辑在表达能力上的局限性：

首先我们注意到，当我们为一个公式集寻找一个interpretation时，并不能任意规定universe，因为公式集本身具有刻画universe的能力。比如，考虑$\Phi=\{\forall x\forall y \ x \equiv y\}$，任何$\mathfrak{I}$只要满足$\mathfrak{I}\models \Phi$，那么意味着$\mathfrak{I}$的universe中的任意两个元素都相等，也即universe大小必须为$1$；考虑$\Phi=\{\forall x\forall y$ $(fx\equiv fy\to x\equiv y),$ $\neg \forall x\exists yfy\equiv x\}$，满足这个公式集的universe必须是无穷集合，因为有限集不可能有到自己的单射而不是满射。

反之，公式集虽然有刻画universe的能力，却没有任意刻画universe的能力。比如，考虑实数算数的structure $S_{\text{ar}}^{<}=\{\mathbb{R},+,\cdot ,0,1,<\}$，是否存在一个公式集使得满足这个公式集的解释的universe一定和实数集等势（不可数）？不可能，因为根据Löwenheim-Skolem定理它一定有一个universe可数的解释。这说明$S_{\text{ar}}^<$这套符号不足够具备刻画实数不可数的能力。

The Compactness Theorem

在完备性的证明中，我们还反复用到了称为紧性(compactness)的概念。这源于拓扑学中的概念：如果一个集合的任何开覆盖都存在一个有限子集覆盖了这个集合，就称这个集合是一个紧集。我们抽象出这种“有限覆盖”的性质，把“$\Phi \vdash \varphi$当且仅当存在$\Phi$的有限子集$\Phi_0$满足$\Phi_0\vdash \varphi$”以及“$\text{Con }\Phi$当且仅当$\Phi$的所有有限子集$\Phi_0$都有$\text{Con }\Phi_0$”称为紧性。我们完整地给出这两个紧性的证明：第一条，右推左显然；左推右，任何证明都是有限长的，因此证明中用到的前提也必定是有限个，证毕。第二条，左推右显然；右推左，假设所有有限子集都一致而$\Phi$不一致，那么说明$\Phi$能推出矛盾，根据第一条一定存在$\Phi$的一个有限子集能推出矛盾，那么这个有限子集不一致，矛盾，证毕。

我们可以从这两条性质出发，探索一阶逻辑的表达能力。