05 一阶逻辑的表达能力

本文我们将讨论一阶逻辑的表达能力。一个逻辑系统的表达能力是指，当我用系统内的符号写出一组公式时，这组公式是否描述且仅描述我所想表达的数学对象。例如，假如我用逻辑符号写出一组自然数算术的公理，是否所有满足这组公理的解释都恰好就是自然数算术系统，或者某个与自然数算术在数学上同构的系统？还是说无论如何我们都不可能写出一组自然数算术的公理，使得满足这组公理的所有解释都同构于自然数算术。

我们首先要介绍紧性定理，作为研究一阶逻辑的表达能力的重要工具。

紧性定理

在[[04 哥德尔完备性定理|基于相继式演算的一阶逻辑的完备性的证明]]中，我们反复用到了关于无穷集合的有限子集的论证。具体地，有：

• $\Phi \vdash \varphi$当且仅当：存在$\Phi$的有限子集$\Phi_0$满足$\Phi_0\vdash \varphi$
• $\text{Con }\Phi$当且仅当：$\Phi$的所有有限子集$\Phi_0$都有$\text{Con }\Phi_0$
• $\text{Sat }\Phi$当且仅当：$\Phi$的所有有限子集$\Phi_0$都有$\text{Sat }\Phi_0$

我们把这三条定理统称为紧性定理(The Compactness Theorem)。证明：

• 第一条，右推左显然；左推右，任何证明都是有限长的，因此证明中用到的前提也必定是有限个；
• 第二条，左推右：假设$\text{Con }\Phi$，如果存在一个有限子集$\Phi_0$使得$\text{Inc }\Phi_0$，那么存在一个$\varphi$使得$\Phi_0\vdash \varphi$且$\Phi\vdash \neg \varphi$，所以$\Phi \vdash \varphi$且$\Phi \vdash \neg\varphi$，这与$\text{Con }\Phi$矛盾；右推左，假设所有有限子集都一致而$\Phi$不一致，那么说明$\Phi$能推出矛盾，根据第一条一定存在$\Phi$的一个有限子集能推出矛盾，那么这个有限子集不一致，矛盾；
• 第三条，由可靠性和完备性，可满足性等价于一致性；

为什么用“紧性”这个词呢？这其实借用了拓扑学中的概念：如果一个集合的任何开覆盖都存在一个有限子集覆盖，就称这个集合是一个紧集。紧性就是这种“有限覆盖”的性质。

有限覆盖如何体现在一阶逻辑上呢？对于任意$S$-formula $\varphi$，我们令$\text{Mod}^S(\varphi)$表示所有能够满足$\varphi$的解释的集合，也即$\text{Mod}^S(\varphi):=\{\mathfrak{I} \mid \mathfrak{I}(\varphi)=true\}$。进一步定义，对于任意$S$-公式集$\Phi$，令$\text{Mod}^S(\Phi):=\{\mathfrak{I}\mid \mathfrak{I}(\Phi)=true\}$。那么，我们有$\text{Mod}^S(\Phi)=\bigcap\limits_{\varphi_0 \in \Phi}\text{Mod}^S(\varphi_0)$。

现在我们证明：对于任意公式集$\Phi$和某个公式$\varphi$，$\text{Mod}^S(\varphi)\subseteq\bigcap\limits_{\varphi_0 \in \Phi}\text{Mod}^S(\varphi_0)$当且仅当存在$\Phi$的一个有限子集$\Phi_0$使得$\text{Mod}^S(\varphi)\subseteq\bigcap\limits_{\varphi_0 \in \Phi_0}\text{Mod}^S(\varphi_0)$。证明：右推左显然；左推右：已知$\text{Mod}^S(\varphi)\subseteq\bigcap\limits_{\varphi_0 \in \Phi}\text{Mod}^S(\varphi_0)$。下面证明$\{\neg \varphi_0\mid \varphi_0 \in \Phi\}\models \neg\varphi$。对于任意$\mathfrak{I}$满足$\mathfrak{I}(\{\neg \varphi_0\mid \varphi_0 \in \Phi\})=true$，我们要证明$\mathfrak{I}(\neg\varphi)=true$。即证$\mathfrak{I}(\varphi)=false$。也即$\mathfrak{I}\not\in \text{Mod}^S(\varphi)$。因为我们假设了$\text{Mod}^S(\varphi)\subseteq\bigcap\limits_{\varphi_0 \in \Phi}\text{Mod}^S(\varphi_0)$，所以我们只需证明$\mathfrak{I} \not\in \bigcup\limits_{\varphi_0\in \Phi}\text{Mod}^S(\varphi_0)$。这等价于$\mathfrak{I} \in \overline{\bigcup\limits_{\varphi_0\in \Phi}\text{Mod}^S(\varphi_0)}=\bigcap\limits_{\varphi_0\in \Phi}\overline{\text{Mod}^S(\varphi_0)}=$ $\bigcap\limits_{\varphi_0\in \Phi}\text{Mod}^S(\neg\varphi_0)=\text{Mod}^S(\{\neg\varphi_0\mid \varphi_0\in \Phi\})$，成立。因此$\{\neg \varphi_0\mid \varphi_0 \in \Phi\}\models \neg\varphi$。那么应用紧性定理，可知存在$\Phi$的一个有限子集$\Phi_0$使得$\{\neg \varphi_0\mid \varphi_0 \in \Phi_0\}\models \neg\varphi$。然后我们就可以证明$\text{Mod}^S(\varphi)\subseteq\bigcap\limits_{\varphi_0 \in \Phi_0}\text{Mod}^S(\varphi_0)$：要证对于任意$\mathfrak{I} \in \text{Mod}^S(\varphi)$，有$\mathfrak{I} \in \bigcap\limits_{\varphi_0 \in \Phi_0}\text{Mod}^S(\varphi_0)=\bigcap\limits_{\varphi_0\in \Phi_0}\overline{\text{Mod}^S(\neg\varphi_0)}=$ $\overline{\bigcup\limits_{\varphi_0\in \Phi_0}\text{Mod}^S(\neg\varphi_0)}$，因此只需证$\mathfrak{I}\not \in \bigcup\limits_{\varphi_0\in \Phi_0}\text{Mod}^S(\neg\varphi_0)$。反证法，如果$\mathfrak{I}\in \bigcup\limits_{\varphi_0\in \Phi_0}\text{Mod}^S(\neg\varphi_0)$，那么由$\{\neg \varphi_0\mid \varphi_0 \in \Phi_0\}\models \neg\varphi$可知$\mathfrak{I}(\varphi)=false$。也即$\mathfrak{I}\not\in \text{Mod}^S(\varphi)$，矛盾。因此$\mathfrak{I}\not \in \bigcup\limits_{\varphi_0\in \Phi_0}\text{Mod}^S(\neg\varphi_0)$。证毕。

这意味着，对于任意公式集$\Phi$和某个公式$\varphi$，如果我们对于每个$\varphi_0\in \Phi$把$\text{Mod}^S(\varphi_0)$看作一个“开集”，那么只要$\{\text{Mod}^S(\varphi_0)\mid \varphi_0\in \Phi\}$构成$\text{Mod}^S(\varphi)$的一个开覆盖，它就一定有一个有限子覆盖。因此在我们的比喻下，任何公式$\varphi$对应的$\text{Mod}^S(\varphi)$都是一个“紧集”。有了这条性质，我们可以用“有限子覆盖”的观点重新理解紧性定理。例如，我们来看紧性定理的第一条。$\Phi \vdash \varphi$（也即$\Phi \models \varphi$）当且仅当$\text{Mod}^S(\Phi)\subseteq \text{Mod}^S(\varphi)$。这当且仅当$\overline{\text{Mod}^S(\varphi)} \subseteq \overline{\text{Mod}^S(\Phi)}$ $= \overline{\bigcap\limits_{\varphi_0\in \Phi}\text{Mod}^S(\varphi_0)}$ $= \bigcup\limits_{\varphi_0\in \Phi}\overline{\text{Mod}^S(\varphi_0)}$。这当且仅当$\text{Mod}^S(\neg \varphi)\subseteq \bigcup\limits_{\varphi_0\in \Phi}\text{Mod}^S(\neg\varphi_0)$，由上一段的证明这当且仅当存在$\Phi$的有限子集$\Phi_0$使得$\text{Mod}^S(\neg \varphi)\subseteq \bigcup\limits_{\varphi_0\in \Phi_0}\text{Mod}^S(\neg\varphi_0)$。这当且仅当$\overline{\text{Mod}^S(\varphi)}\subseteq \overline{\text{Mod}^S(\Phi_0)}$，也即$\text{Mod}^S(\Phi_0)\subseteq \text{Mod}^S(\varphi)$，也即$\Phi_0\models \varphi$。所以$\Phi\vdash \varphi\implies \Phi_0\vdash \varphi$。

勒文海姆-斯科伦定理

可靠性和完备性同时成立告诉我们：一致性和可满足性是当且仅当的。在完备性的证明中，我们得知任何一致的$S$-公式集$\Phi$，都存在一个包含它的公式集$\Psi \supseteq \Phi$，使得$\Psi$可以被term interpretation $\mathfrak{I}^\Psi$满足。进而，$\mathfrak{I}^\Psi$也可以满足$\Psi$。我们考虑$\mathfrak{I}^\Psi$的论域，它是$T^S$上的一个等价类。因此如果$S$是至多可数集，那么$T^S$也是至多可数集，因此$\mathfrak{I}^\Psi$的论域是至多可数集。这直接给出了下面这个结论：设符号集$S$是至多可数的（有限或可数无穷），那么任何可满足的$S$-公式集$\Phi$都有一个满足它的解释$\mathfrak{I}$，其中$\mathfrak{I}$的论域是至多可数集。这就是勒文海姆-斯科伦定理(The Löwenheim-Skolem Theorem)。

利用紧性定理，我们可以得到下面这个推论：选定符号集$S$，设$S$-formula集合$\Phi$满足对于任意$n\in \N$都存在论域大小恰好为$n$的解释$\mathfrak{I}_n$满足$\Phi$，那么存在一个论域无穷大的解释$\mathfrak{I}$满足$\Phi$。证明：对任意$n\geq 2$我们都可以构造一个公式$\varphi_n:=\exists v_1 \cdots \exists v_n \ \bigwedge\limits_{i \in [n]}\bigwedge\limits_{j\in [n]\land j \neq i}\neg v_i\equiv v_j$。可见任何一个满足$\varphi_n$的解释的论域大小必须大于$n$。由此我们构造公式集$\Psi:=\Phi \cup \{\varphi_n\mid n\geq 2\}$。我们证明$\Psi$是可满足的，根据紧性定理只需证$\Psi$的任意有限子集是可满足的。对$\Psi$的任意有限子集$\Psi_0$，一定存在$n_0\geq 2$使得$\Psi_0\subseteq \Phi \cup \{\varphi_i\mid 2\leq i\leq n_0\}$。根据假设，$\Phi$一定有一个论域大小为$n_0$的解释$\mathfrak{I}_{n_0}$，于是一定有$\mathfrak{I}_{n_0}(\Psi_0)=true$，也即$\Psi_0$是可满足的。因此$\Psi$是可满足的。但是，满足$\Psi$的解释不可能只有有限大的论域（假设存在一个论域为$m$的解释，那么它一定不满足$\varphi_{m+1}$），因此$\Psi$有无穷大论域的解释。所以$\Phi$也有无穷大论域的解释。

勒文海姆-斯科伦定理定理似乎只是term interpretation的一个平凡推论，但它却显示出一阶逻辑在表达能力上的局限性：

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

同时，公式集虽然能够左右论域的大小，却无法任意规定论域的大小。比如，考虑实数算数的structure $S_{\text{ar}}^{<}=\{\mathbb{R},+,\cdot ,0,1,<\}$：因为$S_\text{ar}^<$是一个可数集合，所以根据勒文海姆-斯科伦定理，任何$S_\text{ar}^<$-公式集一定有一个论域可数的解释。所以，我们不可能在符号集$S_\text{ar}^<$下找到一组公式$\Phi$，使得能满足$\Phi$的论域是不可数的。换言之，符号集$S_\text{ar}^<$下的公式集没有“规定论域为不可数集”的能力。

我们必须认识到，因为量词的存在，论域的大小是不能随意扩张的。假设$\Phi$有一个可满足的解释$\mathfrak{I}$，其论域为$A$。我们不能在$A$中加入一个新元素$a$，然后认为修改后的解释$\mathfrak{I}'$依然能满足$\Phi$：考虑$\Phi=\{\forall x\forall y \ x \equiv y\}$，那么满足$\Phi$的解释的论域必须大小为$1$，对论域做任何扩展都会导致解释变得不可满足。但我们可以证明，如果可满足的论域本身是无穷大，那么它可以任意做扩展：

选定任意一个符号集$S$，如果可满足的$S$-公式集$\Phi$存在一个满足它的论域无穷大的解释$\mathfrak{I}$，那么满足$\Phi$的解释的论域大小可以比任何集合都要大（也即，对于任意集合$U$，都可以找到一个满足$\Phi$的解释$\mathfrak{I}_U=(\mathfrak{A}_U=(A_U,\mathfrak{a}_U),\beta_A)$使得可以构造$U\to A_U$的单射）。证：对于给定的集合$U$，我们为$U$中的每一个元素$u \in U$创造一个常量符号$c_u$，然后把符号集扩展为$S\cup \{c_u\mid u\in U\}$。于是，我们可以构造一个$S\cup \{c_u\mid u\in U\}$-公式集$\Psi:=\Phi \cup \{\neg c_u\equiv c_v\mid u,v \in U,u\neq v\}$。显然，任何一个能满足$\Psi$的解释的论域都必须大过集合$U$（存在$U$到论域的单射）。并且既然这个解释可以在$S\cup \{c_u\mid u\in U\}$下满足$\Psi$，就一定可以在$S$下满足$\Phi$。但我们还需验证$\Psi$的确是可满足的：根据紧性定理，只需证明$\Psi$的任意有限子集都是可满足的。这等价于证明，$\forall n \in \N,\text{Sat }(\Phi \cup \{\neg c_{u_i}\equiv c_{u_j}\mid 1\leq i,j \leq n,i\neq j\})$。因为$\Phi$有一个可满足的论域无穷大的解释$\mathfrak{I}$，所以我们总可以从$\mathfrak{I}$的论域中挑出$n$个元素$b_1,\cdots,b_n$。只需令$\mathfrak{a}(c_{u_i})=b_i$，我们就修改得到了一个解释$\mathfrak{I}'$满足公式集$\Phi \cup \{\neg c_{u_i}\equiv c_{u_j}\mid 1\leq i,j \leq n,i\neq j\}$，证毕。

Remark: 这个定理在数学实践上也有重要的应用：它可以帮助我们证明任意大的代数结构的存在性。例如，我们只需要用一阶逻辑语言写出刻画群的性质的公式集$\Phi$，那么我们只需证明存在无穷大（比如可数无穷大）的群，就可以用上面的定理证明存在一个大于任意无穷大（比如大于不可数无穷大）的群。因为“存在无穷大的群”意味着$\Phi$有一个无穷大论域，于是上面的定理就告诉我们论域可以任意大。由此可见，这套方法为我们提供了一套研究代数结构的一般方法。这门学科称为“模型论(model theory)”。

初等类

下面我们把讨论范围从formula限定到sentences。沿用我们讨论紧性时所用的符号“$\text{Mod}$”，作如下定义：选定符号集$S$，对任意$S$-sentence集合$\Phi$，称集合$\text{Mod}^S(\Phi):=\{\mathfrak{A}\mid \mathfrak{A}(\Phi)=true\}$为$\Phi$的模型类(class of models)。注意，这里我们用structure $\mathfrak{A}$作定义而不用interpretation $\mathfrak{I}$，因为在讨论sentence时不需考虑自由变量的赋值。

模型类是由全体$S$-structure中的一部分构成的类(class)。我们用“类”是因为我们不想讨论“全体$S$-structure”到底是否能构成一个“集合”。我们特别关心两种$S$-structure类：

• 对于任意$S$-structure类$\mathfrak{K}$，如果存在某一个$S$-sentence $\varphi$使得$\mathfrak{K}=\text{Mod}^S(\varphi)$，就称$\mathfrak{K}$为一个初等类(elementary class)；
• 对于任意$S$-structure类$\mathfrak{K}$，如果存在某一个$S$-sentence $\Phi$使得$\mathfrak{K}=\text{Mod}^S(\Phi)$，就称$\mathfrak{K}$为一个$\Delta$-初等类($\Delta$-elementary class)；

探讨一阶逻辑的表达能力问题，就是在探讨“怎样的$S$-structure类是初等的”。如果一个$S$-structure类是初等类，那么它可以用单个$S$-sentence描述；如果一个$S$-structure类是$\Delta$-初等类，那么它可以用一组$S$-sentence描述。判断一个$S$-structure类是否是初等的，就是在判断这个structure类是否是“可公理化”的。

比如，取$S=\{\circ,e\}$，我们写出下面一组$S$-sentence：

• $\forall x\forall y\forall z \ (x\circ y)\circ z=x\circ(y\circ z)$
• $\forall x \ x \circ e = x$
• $\forall x \exists y \ x\circ y = e$

于是，任何一个群都可以作为这组公式的structure。现在问：所有有限群组成的structure类$\mathfrak{K}$是否是初等类或$\Delta$-初等类？答案是不可能。假设这个$\mathfrak{K}$是$\Delta$-初等类，那么存在sentence集合$\Phi$使得$\mathfrak{K}=\text{Mod}^S(\Phi)$。因此，任何一个有限群structure都落在都能满足$\Phi$，所以$\Phi$可以被任何论域有限的解释满足。但是，根据勒文海姆-斯科伦定理的推论，$\Phi$一定有一个论域无穷大的structure $\mathfrak{A}$满足它。因此$\mathfrak{A} \in \text{Mod}^S(\Phi)$而$\mathfrak{A} \not\in \mathfrak{K}$，这与$\mathfrak{K}=\text{Mod}^s(\Phi)$矛盾。所以$\mathfrak{K}$一定不是$\Delta$-初等类。这就是说，所有有限群组成的structure类是不可被“公理化”的。

初等等价性

我们证明过Isomorphism Lemma：如果$\mathfrak{A}\cong \mathfrak{B}$，那么对于任意$S$-sentence $\varphi$都有$\mathfrak{A}(\varphi)=\mathfrak{B}(\varphi)$。我们注意，“对于任意$S$-sentence $\varphi$都有$\mathfrak{A}(\varphi)=\mathfrak{B}(\varphi)$”这一条件是一阶逻辑表达能力的一个重要表述。如果两个structure在任意一个一阶逻辑sentence上的可满足性都是相同的，就意味着一阶逻辑语言无法区分这两个structure。Isomorphism Lemma就是在说：一阶逻辑语言无法区分两个同构的structure。

我们把这一性质定义为“初等等价性”：对于两个$S$-structure $\mathfrak{A},\mathfrak{B}$，如果对于任何$S$-sentence $\varphi$都有$\mathfrak{A}(\varphi)=true\iff \mathfrak{B}(\varphi)=true$，就称$\mathfrak{A},\mathfrak{B}$是初等等价(elementarily equivalent)的，记为$\mathfrak{A}\equiv \mathfrak{B}$。两个初等等价的structure对所有sentence都会做出相同的解释。于是Isomorphism Lemma可以表述为：同构的structure一定是初等等价的。

我们记得，Isomorphism Lemma的逆命题只对有限符号集成立。这意味着当符号集无限时，初等等价的structure不一定同构。这里已经出现了一阶逻辑的表达能力缺陷：当符号集无限时，总是存在两个不同构的structure是一阶逻辑无法区分的。

接下来我们要进一步证明，对任意符号集$S$，只要$\mathfrak{A}$是一个论域无穷大的structure，那么就一定存在一个与它初等等价的structure $\mathfrak{B}\equiv \mathfrak{A}$，使得$\mathfrak{B}$与$\mathfrak{A}$不同构。这体现了一阶逻辑表达能力的更大缺陷：任何一个论域无穷大的structure都有一个与它不同构的structure是一阶逻辑无法区分的，比如“自然数算术”或“实数算数”。

首先引入“一阶逻辑理论”的定义。选定符号集$S$，对于$S$-structure $\mathfrak{A}$，定义$\text{Th}(\mathfrak{A}):=\{\varphi \in L_0^S\mid \mathfrak{A}(\varphi)=true\}$。$\text{Th}(\mathfrak{A})$称为$\mathfrak{A}$的理论(theory)，它包含所有能被$\mathfrak{A}$满足的sentence集合。

下面证明，对于两个$S$-structure $\mathfrak{A},\mathfrak{B}$，$\mathfrak{A}\equiv \mathfrak{B}$当且仅当$\mathfrak{B}(\text{Th}(\mathfrak{A}))=true$。也即，满足某个模型的理论的模型一定与该模型初等等价。证明：左推右：因为$\mathfrak{A}(\text{Th}(\mathfrak{A}))=true$，而$\mathfrak{A}\equiv \mathfrak{B}$，所以$\mathfrak{B}(\text{Th}(\mathfrak{A}))=true$；右推左：对于任意一个$S$-sentence $\varphi$，如果$\mathfrak{A}(\varphi)=true$，那么$\varphi \in \text{Th}(\mathfrak{A})$，那么$\mathfrak{B}(\varphi)=true$。如果$\mathfrak{A}(\varphi)=false$，那么$\mathfrak{A}(\neg \varphi)=true$，所以$\neg\varphi \in\text{Th}(\mathfrak{A})$，因此$\mathfrak{B}(\neg\varphi)=true$，因此$\mathfrak{B}(\varphi)=false$。所以但对于任意$\varphi$都有$\mathfrak{A}(\varphi)=true\iff \mathfrak{B}(\varphi)=true$；证毕。

下面证明，对于论域无穷大的structure $\mathfrak{A}$，所有与它同构的structure构成的类$\{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}$不是$\Delta$-初等类。证明：假设$\{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}$是$\Delta$-初等类，那么存在sentence集合$\Phi$满足$\{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}=\text{Mod} (\Phi)$。因为$\mathfrak{A} \in \{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}$，所以$\mathfrak{A}(\Phi)=true$。这说明$\Phi$有论域无穷大的解释。由勒文海姆-斯科伦定理，$\Phi$可以有任意无穷大的解释（比如达到$\mathfrak{A}$的幂集那么大）。这说明存在一个与$\mathfrak{A}$不同构的structure $\mathfrak{C}\in \text{Mod}(\Phi)$，这与$\{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}=\text{Mod} (\Phi)$矛盾。证毕。

下面证明，对于论域无穷大的structure $\mathfrak{A}$，所有与它初等等价的structure构成的类$\{\mathfrak{B}\mid \mathfrak{B}\equiv \mathfrak{A}\}$是$\Delta$-初等类。因为$\mathfrak{A}\equiv \mathfrak{B}$当且仅当$\mathfrak{B}(\text{Th}(\mathfrak{A}))=true$，所以$\{\mathfrak{B}\mid \mathfrak{B}\equiv \mathfrak{A}\}=\{\mathfrak{B}\mid \mathfrak{B}(\text{Th}(\mathfrak{A}))=true\}=\text{Mod}(\text{Th}(\mathfrak{A}))$。因此$\{\mathfrak{B}\mid \mathfrak{B}\equiv \mathfrak{A}\}$是$\Delta$-初等类。

对于论域无穷大的structure $\mathfrak{A}$，由Isomorphism Lemma，我们得知$\{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}$一定是$\{\mathfrak{B}\mid \mathfrak{B}\equiv \mathfrak{A}\}$的子类。但前者不是$\Delta$-初等类，后者却是$\Delta$-初等类，这意味着$\{\mathfrak{B}\mid \mathfrak{B}\cong \mathfrak{A}\}$一定是$\{\mathfrak{B}\mid \mathfrak{B}\equiv \mathfrak{A}\}$的真子类。因此存在$\mathfrak{B}$，$\mathfrak{B}\equiv \mathfrak{A}$却$\mathfrak{B}\not\cong \mathfrak{A}$。

非标准模型

这意味着，自然数算术模型$\mathfrak{N}=(\N,+,\cdot,0,1)$，或带有序关系的实数域模型$\mathfrak{R}^<=(\R,+,\cdot,<,0,1)$，都存在着与之不同构但与之初等等价的模型。这样的模型称为非标准模型(nonstandard model)。下面以自然数算术为例。

考虑所有被标准自然数算术$\mathfrak{N}$满足的sentence集合，也即$\mathfrak{N}$的理论$\text{Th}(\mathfrak{N})$。由于$\mathfrak{N}$本身就是$\text{Th}(\mathfrak{N})$的一个论域无穷大的模型，所以由勒文海姆-斯科伦定理$\text{Th} (\mathfrak{N})$总是存在大于任意无穷大的模型$\mathfrak{A}$。因为$\mathfrak{A}(\text{Th}(\mathfrak{N}))=true$，我们证明过这当且仅当$\mathfrak{A}\equiv \mathfrak{N}$。所以我们就找到了一个大于任意无穷大的自然数算术的非标准模型。

斯科伦进一步证明了：可以找到一个可数无穷大的自然数算术的非标准模型。构造自然数算术符号集下的formula集合$\Psi:=\text{Th}(\mathfrak{N})\cup \{\neg x\equiv 0,\neg x \equiv 1, \neg x\equiv 2,\cdots\}$，其中$x$是任意一个变量名。我们证明$\Psi$是可满足的。由紧性定理只需证明$\Psi$的任意有限子集是可满足的。对于$\Psi$的任意有限子集$\Psi_0$，一定可以找到一个$n \in \N$，令$\beta(x)=n$，从而得到一个解释$\mathfrak{I}_0=(\N,\beta)$满足$\Psi_0$。因此$\Psi$是可满足的。勒文海姆-斯科伦定理说符号集有限时，任何可满足的公式集都有一个至多可数无穷大的解释满足它，所以$\Psi$有一个论域至多可数无穷大的解释$\mathfrak{I}=(\mathfrak{A},\beta)$。因为要满足所有自然数算术，$\mathfrak{A}$的论域$A$不可能是有限大的。由此可得$\mathfrak{A}$就是$\text{Th}(\mathfrak{N} )$的一个可数无穷大的模型。因为$\mathfrak{A}(\text{Th}(\mathfrak{N}))=true$，所以$\mathfrak{A}\equiv \mathfrak{N}$。接下来只需证明$\mathfrak{A}\not\cong \mathfrak{N}$。如果$\mathfrak{A}\cong \mathfrak{N}$，那么存在一个$A$与$\N$之间的双射$\pi$。因为$\mathfrak{I}(\Psi)=true$，所以对于任意$n \in \N$，一定有$\mathfrak{I}(\neg x \equiv n)=true$，也即$\beta(x)\neq n^{\mathfrak{A}}=\pi^{-1}(n^{\mathfrak{N}})$。也即，对于任意$n \in \N$都有$\pi(\beta(x))\neq n^{\mathfrak{N}}$，也即$\pi(\beta(x))\not\in \N$，这与$\pi$是双射矛盾。所以$\mathfrak{A}\not\cong \mathfrak{N}$，证毕。

究竟什么样的自然数算术模型是可数的，但是与自然数算术不同构？在上面构造的满足$\Psi$的模型$\mathfrak{A}$中，我们证明了$\mathfrak{A}$的论域中包含了一个$\N$中没有的元素$\beta(x)$。我们可以想象，标准模型$\mathfrak{N}$中所有元素都是沿一条数轴排列的，这是由于公式集$\text{Th}(\mathfrak{N})$会规定了我们必须这么做：每个数都有一个比它恰好大1的数；每一个非零的数都有一个恰好比它小1的数；等等。那么，一定有比$\beta(x)$恰好大1的数，而由于$\beta(x)$不是0，一定也有比$\beta(x)$恰好小1的数。进而，有比$\beta(x)+1$恰好大1的数；$\beta(x)-1$不能是0，否则意味着$\beta(x)=1$，因此还有比$\beta(x)-1$恰好小1的数；……这意味着，模型$\mathfrak{A}$中有一条包含$\beta(x)$的数轴，这条数轴是完全与$\N$平行的，并且是往两侧无限延申的。进一步，$\beta(x)+\beta(x)$在哪条数轴上呢？假如$\beta(x)$和$\beta(x)+\beta(x)$在同一条数轴上，那么不失一般性，存在$n\in \N$使得$\beta(x)+n=\beta(x)+\beta(x)$。由自然数算术的左消去律， 得到$n=\beta(x)$，矛盾。所以$\beta(x)+\beta(x)$又形成了一条独立的双向数轴。由此可见，初步分析已经说明非标准模型$\mathfrak{A}$中存在无数条双向数轴。

所以，为了研究标准模型$\mathfrak{A}$上的结论，并不一定需要在标准模型$\mathfrak{A}$上研究，而可以采用任何非标准模型$\mathfrak{A}'$。在非标准模型$\mathfrak{A} '$上证出的结论$\mathfrak{A}'(\Phi)\implies \mathfrak{A}'(\varphi)$总可以还原到形式系统$\Phi \vdash \varphi$上。此时再用标准模型$\mathfrak{A}$做解释，我们就能得出标准模型上的结论$\mathfrak{A}(\varphi)\implies \mathfrak{A}(\varphi)$。

由此可见，尽管非标准模型的存在是一阶逻辑表达能力的缺陷，但它却为我们带来了用全新的模型研究数学的可能性。最著名的实践就是非标准分析(nonstandard analysis)。1960年代，亚伯拉罕·鲁宾逊绕开了传统分析学繁琐的$\varepsilon-\delta$定义，建立了一套把无穷大和无穷小作为论域中的元素的数学分析方法。

二阶逻辑

我们已经证明了，不可能写出一组一阶逻辑公式，使得任何满足这组公式的模型都与自然数算术模型$\mathfrak{N}$同构。下面我们证明，如果改用二阶逻辑(Second Order Logic)语言，就可以做到这一点。

在alphabet上，二阶逻辑相比于一阶逻辑引入了“关系变量(relation variables)”。对于任何$n \in \N^+$，都可以使用可数无穷个$n$元关系变量$V_0^n,V_1^n,\cdots$。通常我们可以用大写字母$X,Y,\cdots$来表示关系变量。

二阶逻辑只引入“关系变量”，而没有引入“函数变量”，这是一种处于简洁性考虑的设计。函数从数学上是一种特殊的关系：$f(x,y)=z$可以写成$R(x,y,z)=true$。我们可以证明，假如我们设计了一套带有函数变量的二阶逻辑，那么这套逻辑一定可以等价地还原到不带有函数变量的二阶逻辑。深入下去，我们就再次回到了关于命题“范式(normal forms)”的讨论，就像我们在命题逻辑中所做的那样，在此不再详细展开。

二阶逻辑关于term的语法就是一阶逻辑term的语法；

一个二阶逻辑formula，除了所有一阶逻辑formula的语法的定义之外，还包括以下两条归纳定义：

• 如果$X$是一个$n$元关系变量，$t_1,\cdots,t_n$都是term，那么$Xt_1\cdots t_n$是一个formula；
• 如果$X$是一个$n$元关系变量，$\varphi$是formula，那么$\exists X \varphi$是formula；（由功能完全性，我们不需要定义$\forall X\varphi$）

在符号集$S$下，全体满足二阶逻辑语法的formula集合记为$L^S_{\text{II}}$。

由于二阶逻辑和一阶逻辑在符号集的定义上完全相同，所以一个二阶逻辑structure $\mathfrak{A}=(A,\mathfrak{a})$的定义与一阶逻辑相同。而在一个二阶逻辑解释$\mathfrak{I}=(\mathfrak{A},\gamma)$中，$\gamma$需要对所有关系变量做赋值。任何一个$n$元关系变量$V_i^n$的赋值$\gamma(V_i^n)$都是$A^n$的一个子集。

由此，我们在一阶逻辑的基础上定义二阶逻辑的语义：

• $\mathfrak{I}(X t_1\cdots t_n) =true$当且仅当在数学事实上$n$元组$(\mathfrak{I}(t_1),\cdots,\mathfrak{I}(t_n))\in \gamma(X)$；
• 对于$n$元关系变量$X$，$\mathfrak{I}(\exists X \varphi)=true$当且仅当在数学事实上存在$C\subseteq A^n$使得$\mathfrak{I} \dfrac{C}{X}(\varphi)=true$；其中，$\mathfrak{I}\dfrac{C}{X}:=(\mathfrak{A},\gamma\dfrac{C}{X})$，$\gamma\dfrac{C}{X}(Y):=\begin{cases}C&,Y=X\\ \gamma(Y) & ,\text{otherwise}\end{cases}$；

皮亚诺公理

现在回到自然数算术上来。下面这组用二阶逻辑语言写出的公式就是刻画自然数算术模型$\mathfrak{N}=(\N,+^\N,\cdot^\N,0^\N,1^\N)$的皮亚诺公理(Peano Axioms)：

• $\forall x \ \neg x+1\equiv 0$
• $\forall x \ 0+x \equiv x$
• $\forall x \ x \cdot 0\equiv 0$
• $\forall x\forall y \ (x+1\equiv y+1\to x\equiv y)$
• $\forall x\forall y(x+(y+1)\equiv (x+y)+1)$
• $\forall x\forall y(x \cdot (y+1)\equiv (x\cdot y)+x)$
• $\forall P(((P0)\land \forall k(Pk\to P(k+1)))\to (\forall y \ Py))$

把这组公式记为$\Pi$。前六条都可以看作一阶逻辑命题。只有最后一条是二阶逻辑命题，它刻画了“归纳法”。我们证明任何满足$\Pi$的模型$\mathfrak{A}$都有$\mathfrak{A}\cong \mathfrak{N}$。

我们首先把符号限制到单个“后继函数符$\sigma$”以及“加法单位元$0$”上。写出下面这组公式，记为$\Pi'$：

• $\forall x \ \neg \sigma x \equiv 0$
• $\forall x\forall y (\sigma x\equiv \sigma y\to x\equiv y)$
• $\forall P(((P0)\land \forall k(Pk\to P(\sigma k)))\to (\forall y \ Py))$

我们在数学事实上定义$\N$上的函数$s:\N\to \N$，$s(n)=n+1$。那么模型$\mathfrak{N}_\sigma=(\N,s^\N,0^\N)$显然满足$\Pi'$。下面我们证明任何满足$\Pi'$的模型$\mathfrak{A}_0$都有$\mathfrak{A}_0\cong \mathfrak{N}_\sigma$。设$\pi:\N \to A_0$，令$\pi(0^\N)=0^{\mathfrak{A}_0}$，对任意$n\in \N$，$\pi(s^\N(n))=\sigma^{\mathfrak{A}_0}(\pi(n))$。那么要证明$\pi$是$\mathfrak{A}_0$和$\mathfrak{N}_\sigma$的同构映射，只需证明$\pi$是$\N$到$A_0$的双射。先证$\pi$是满射：即证对于任意$a_0 \in A_0$，都存在$n \in \N$使得$\pi(n)=a_0$。由于$\mathfrak{A}_0$满足$\Pi'$，因此$\mathfrak{A}_0(\forall P(((P0)\land \forall k(Pk\to P(\sigma k)))\to (\forall y \ Py)))=true$，也即对于任何$A_0$上的一元关系$P^{\mathfrak{A}_0}$，要证$P^{\mathfrak{A}_0}=A_0$只需证：① $0^{\mathfrak{A}_0}\in P^{\mathfrak{A}_0}$；② 对任意$a_0 \in A_0$只要$a_0 \in P^{\mathfrak{A}_0}$就有$\sigma^{\mathfrak{A}_0}(a_0) \in P^{\mathfrak{A}_0}$。令$P$为$\{a \mid \exists n \in \N,\pi(n)=a\}$。先证①：$\pi(0)=0^{\mathfrak{A}_0}$，因此$0^{\mathfrak{A}_0}\in P$；再证②:对于任意$a_0 \in A_0$，假设$a_0 \in P$，也即存在$n_1$使得$\pi(n_1)=a_0$，那么存在$n_2=n_1+1$使得$\pi(n_2)=\pi(n_1+1)=\pi(s(n_1))$ $=\sigma^{\mathfrak{A}_0}(\pi(n_1))$ $=\sigma^{\mathfrak{A}_0}(a_0)$，所以$\sigma^{\mathfrak{A}_0}(a_0)\in P$；由此可见$P=A_0$，也即对于任意$a_0\in A_0$都存在$n \in N$使得$\pi(n)=a_0$，因此$\pi$是满射；再证$\pi$是单射：即证对于任意的$n,m\in \N$，$n\neq m\implies \pi(n)\neq \pi(m)$。我们用数学事实上的归纳法。当$n=0$时，要证对于任意$m \in \N,m\neq 0\implies \pi(m)\neq 0^{\mathfrak{A}_0}$。因为$m\neq 0$，可以设存在$k \in \N$使得$m=k+1$，因此$\pi(m)=\pi(k+1)=\sigma^{\mathfrak{A}_0}(\pi(k))$。因为$\mathfrak{A}_0$满足$\Pi'$，所以$\mathfrak{A}_0(\forall x \ \neg \sigma x \equiv 0)=true$，也即任意$a_0 \in A_0$都有$\sigma^{\mathfrak{A}_0}(a_0)\neq 0^{\mathfrak{A}_0}$，因此$\sigma^{\mathfrak{A}_0}(\pi(k))\neq 0^{\mathfrak{A}_0}$。归纳步骤，设对于某个$k$有：对于任意$m \in \N,m \neq k$ $\implies \pi(m)\neq \pi(k)$，要证对于任意$m\in \N,m\neq k+1\implies \pi(m)\neq \pi(k+1)$。如果$m=0$，那么$\pi(m)=0^{\mathfrak{A}_0}$，而$\pi(k+1)=\sigma^{\mathfrak{A}_0}(\pi(k))$，同理应用$\Pi'$中的第一条可得$\sigma^{\mathfrak{A}_0}(\pi(k))\neq 0^{\mathfrak{A}_0}$。如果$m \neq 0$，那么存在$u \in \N$使得$m=u+1$，于是$u\neq k$，并且$\pi(m)=\sigma^{\mathfrak{A}_0}(\pi(u))$。因为$\mathfrak{A}_0(\forall x\forall y (\sigma x\equiv \sigma y\to x\equiv y))=true$，所以对于任意$x_0,y_0\in A_0$，$\sigma^{\mathfrak{A}_0}(x_0)=\sigma^{\mathfrak{A}_0}(y_0)\implies x_0=y_0$。根据$u\neq k$，有$\pi(u)\neq \pi(k)$，所以$\sigma^{\mathfrak{A}_0}(\pi(u))\neq \sigma^{\mathfrak{A}_0}(\pi(k))=\pi(k+1)$，也即$\pi(m)\neq \pi(k+1)$；证毕。

对于任意满足$\Pi$的模型$\mathfrak{A}=(A,+^\mathfrak{A},\cdot^\mathfrak{A},0^\mathfrak{A},1^\mathfrak{A})$，我们可以定义符号$\sigma$，并在$\mathfrak{A}$上赋予它语义$\forall a \in A,\sigma^\mathfrak{A}(a):=a+^\mathfrak{A} 1^\mathfrak{A}$。下面证明模型$\mathfrak{A}_\sigma=(A,\sigma^\mathfrak{A},0^\mathfrak{A})$满足$\Pi'$：$\mathfrak{A}_\sigma(\forall x \ \neg \sigma x \equiv 0)=true$当且仅当$\forall a \in A,\sigma^\mathfrak{A}(a)\neq 0^\mathfrak{A}$，当且仅当$\forall a \in A,a+^\mathfrak{A} 1^\mathfrak{A}\neq 0^\mathfrak{A}$，当且仅当$\mathfrak{A}(\forall x \neg x+1\equiv 0)$，成立；$\mathfrak{A}_\sigma(\forall x\forall y (\sigma x\equiv \sigma y\to x\equiv y))=true$当且仅当$\forall a,b \in A,\sigma^\mathfrak{A}(a)=\sigma^\mathfrak{A}(b)$ $\implies a= b$，当且仅当$\forall a,b \in A,a+^\mathfrak{A} 1^\mathfrak{A}=b+^\mathfrak{A} 1^\mathfrak{A}$ $\implies a= b$，当且仅当$\mathfrak{A}(\forall x\forall y \ (x+1\equiv y+1\to x\equiv y))$，成立；同理，$\mathfrak{A}_\sigma(\forall P(((P0)\land \forall k(Pk\to P(\sigma k)))\to (\forall y \ Py)))=true$当且仅当$\mathfrak{A}(\forall P(((P0)\land \forall k(Pk\to P(k+1)))\to (\forall y \ Py)))=true$。因此$\mathfrak{A}_\sigma(\Pi')=true$。这意味着$\mathfrak{A}_\sigma\cong \mathfrak{N}_\sigma$。

最后证明$\mathfrak{A}\cong \mathfrak{N}$。根据$\mathfrak{A}_\sigma\cong \mathfrak{N}_\sigma$，我们有$\N \to A$的双射$\pi$，满足$\pi(0^\N)=0^\mathfrak{A}$，对任意$n \in \N,\pi(\sigma^\N(n))=\sigma^\mathfrak{A}(\pi(n))$。所以为了证明$\mathfrak{A}\cong \mathfrak{N}$，只需证明$\pi$对$+^\N,\cdot^\N,1^\N$也保持结构：

乘法单位元：$\pi(1) = \pi(\sigma^\N(0)) = \sigma^\mathfrak{A}(\pi(0)) = 0^\mathfrak{A} +^\mathfrak{A} 1^\mathfrak{A}$。由$\Pi$的第二条$\forall x \ 0+x \equiv x$，得证。

加法：要证$\forall n,m\in \N,\pi(n+^\N m)=\pi(n)+^\mathfrak{A} \pi(m)$。对$m$做数学事实上的归纳法。基例：$m = 0$。我们有$\pi(n +^\N 0) = \pi(n) = \pi(n) +^\mathfrak{A} 0^\mathfrak{A}$（由$\Pi$的第二条$\forall x \ x + 0 \equiv x$）。归纳：假设 $\pi(n + m) = \pi(n) +^\mathfrak{A} \pi(m)$，要证 $\pi(n + m + 1) = \pi(n) +^\mathfrak{A} \pi(m + 1)$。我们有$\pi(n + m + 1)$。代入归纳假设，得到$(\pi(n) +^\mathfrak{A} \pi(m)) +^\mathfrak{A} 1^\mathfrak{A}$。只需证$(\pi(n) +^\mathfrak{A} \pi(m)) +^\mathfrak{A} 1^\mathfrak{A}$ $=\pi(n) +^\mathfrak{A} (\pi(m) +^\mathfrak{A} 1^\mathfrak{A})$。由$\Pi$的第五条$\forall x \forall y (x + (y + 1) \equiv (x + y) + 1)$，得证。

乘法：要证$\forall n,m\in \N,\pi(n\cdot^\N m)=\pi(n)\cdot^\mathfrak{A} \pi(m)$。对$m$做数学事实上的归纳法。基例：$m = 0$。我们有$\pi(n \cdot^\N 0) = \pi(0) = \pi(n) \cdot^\mathfrak{A} 0^\mathfrak{A}$（由$\Pi$的第三条$\forall x \ x \cdot 0\equiv 0$）。归纳：假设 $\pi(n \cdot m) = \pi(n) \cdot^\mathfrak{A} \pi(m)$，要证 $\pi(n \cdot(m + 1)) =$ $\pi(n) \cdot^\mathfrak{A} \pi(m + 1)$。我们有$\pi(n \cdot(m + 1)) =\pi(n\cdot m+n)=\pi(n\cdot m)+^\mathfrak{A}\pi(n)$。由归纳假设，得到$\pi(n \cdot m) =\pi(n) \cdot ^\mathfrak{A} \pi(m)$。因此只需证$\pi(n) \cdot ^\mathfrak{A} \pi(m)+^\mathfrak{A} \pi(n)$ $=\pi(n) \cdot^\mathfrak{A} (\pi(m) +^\mathfrak{A} 1^\mathfrak{A})$。由$\Pi$的第六条$\forall x\forall y(x \cdot (y+1)\equiv (x\cdot y)+x)$，得证。

综上，我们证明了任何满足皮亚诺公理的模型都与自然数算术的标准模型$\mathfrak{N}$同构。我们把任何满足皮亚诺公理的模型都称为一个皮亚诺系统(Peano System)，任何皮亚诺系统都是同构的。全体皮亚诺系统构成的一个模型类，我们证明过不存在一组一阶逻辑公理的模型类为全体皮亚诺系统。而皮亚诺公理中除了最后一条“归纳公理”以外都是一阶逻辑公式，所以不存在一组一阶逻辑公理刻画“归纳公理”。这是一阶逻辑表达能力的局限性。必须把一阶逻辑扩展到二阶逻辑，才可以对自然数算术系统做“同构的刻画(characterize up to isomorphism)”。

二阶逻辑的完备性不成立

然而，二阶逻辑尽管相比于一阶逻辑在表达能力上有所增强，却失去了完备性。

让我们首先来证明，二阶逻辑中紧性定理的第三条“$\text{Sat }\Phi$当且仅当$\Phi$的所有有限子集$\Phi_0$都有$\text{Sat }\Phi_0$”是不成立的：

我们知道在数学事实上，对任意集合$A$，如果$A\to A$的任何函数只要是单射就能推出满射，那么$A$必须是有限集合。那么我们可以写出二阶逻辑公式$\varphi_{\text{fin}}:=\forall X((\forall X(\exists ^{=1}yXxy)\land \forall x\forall y \forall z((Xxz\land Xyz)\to x\equiv y)))\to \forall y\exists x Xxy$用来刻画论域是有限集合（其中，$\exists^{=1}x\varphi$是$\exists x\varphi \land \forall y(\varphi\dfrac{y}{x}\to x\equiv y)$的缩写。我们再次对任意$n\geq 2$引入$\varphi_n:=\exists v_1 \cdots \exists v_n \ \bigwedge\limits_{i \in [n]}\bigwedge\limits_{j\in [n]\land j \neq i}\neg v_i\equiv v_j$用来刻画论域的有限下界。由此，我们构造出一个sentence集合$\Phi:=\varphi_{\text{fin}} \cup \{\varphi_n\mid n\geq 2\}$。那么，任何大小为$n$的structure都能满足$\varphi_{\text{fin}}$，但不能满足$\varphi_{n+1}$。所以$\Phi$不存在有限大的structure满足它。但是，$\Phi$的任何有限子集确实都是可满足的。所以如果紧性定理成立就会推出$\Phi$也是可满足的，矛盾。因此对于二阶逻辑，紧性定理不成立。

但是，紧性定理是完备性的直接推论。回顾我们对紧性定理的证明就会发现，其证明过程没有用到任何一阶逻辑独有的而二阶逻辑没有的特殊性质。那么，假设二阶逻辑有完备性，那么我们应该能够证明上面这条紧性定理成立，矛盾。于是我们只能得出结论：此时完备性不成立。

这里，要注意语词的使用。当我们讨论“二阶逻辑的完备性”时，不仅涉及命题所用的语言“二阶逻辑”，还涉及用于形式化证明的推导规则。紧性定理不成立意味着，我们不可能找到一组推导规则使得完备性成立。如果我们找到了，我们就一定能推出紧性定理成立。所以，严格的表述应该是：对于任何一组二阶逻辑的形式化证明规则$\vdash$，都可以找到一组二阶逻辑公式集$\Phi$和一个二阶逻辑公式$\varphi$，使得$\Phi \vdash \varphi\iff \Phi\models \varphi$不成立。

可见，正是因为二阶逻辑表达能力的增强，使得我们可以直接刻画“论域有限”这一性质。但正是因为表达能力的增强，使得“二阶逻辑的完备性”不再成立。随着逻辑系统的表达能力的增强，它会失去原有的良好性质。我们之后还将不断看到这一点。

数学论域

当讨论“语义”（模型、解释等等）时，我们总是强调“数学事实”，它是“客观”的。然而，这里的“客观”并不是指数学事实一定是本体论意义上的存在。每当我们讨论“语义”或“数学事实”时，我们其实已经涉及了“哲学”。这个“哲学”包括每个做出语义解释的人所采取的本体论假设和认识论假设。不同的人当然会有不同的本体论假设和认识论假设，所以严谨地来看每个人都只是在研究他自己的数学。但是，很多时候会有一群人对于“数学事实”会采取几乎完全相同的假设，所以可以认为当这些人共同讨论“语义”时，它们所指向的对象是“客观的”。我们称它们奉行同一种“主义”。在不同“主义”的人群看来，数学事实有可能完全不同的。

奉行同一种“主义”的人会在相同的模型下对数学事实做出相同的判断，但这并不意味着他们已经完全弄清了它们是如何“做出判断”的。人们总是在使用和习惯的过程中加深对数学的了解，而不是在一开始就已经彻底厘清数学在根基上所有的细节。归根结底，数学只是一种特殊的语言。可以想象，数学在最初只是一群人约定而成的模糊的直观。直到“公理化”被提出，数学家们才开始采用“证明”的方法来澄清对数学事实的判定过程。可以说，现代数学就是公理化的数学。

在公理化的数学中，必须小心对待公理中提出的数学对象。在以前，人们依赖于一些“不需加以解释的数学对象”，例如几何原本中的“点”和“线”，朴素集合论中的“集合”。然而正是这些人们曾以为“不需加以解释”的概念引发了问题。罗素悖论就产生于对“集合”概念的阐释不清。人们意识到，并不是任何一组东西组合在一起都可以被称为集合。

ZFC公理化集合论的提出，就是对“什么是集合”的澄清。有的人希望把ZFC集合论作为数学的根本理论。它声称一切数学对象都可以还原为集合，一切数学对象之间的关系都可以还原为$\in$关系，并提出了一套公理作为一切数学讨论的起点。既然所有东西都是集合，那么我们就不必区分数学对象在“类型(type)”上的区别，比如“自然数”或“群”或“映射”都是集合。同时，既然所有东西都是集合，那么这样一套理论肯定可以用一阶逻辑写出，再也不用担心“关系”或“函数”不是一阶对象不能填到量词中，因为现在“集合到集合的映射”也是“集合”，所有对象都是一阶对象。

既然ZFC公理系统可以用一阶逻辑表示。而一阶逻辑本身也是一个数学对象。所以，如果我们相信ZFC公理系统能表示所有数学，那么原则上一阶逻辑也可以表示所有数学。我们可以把ZFC的所有公理用一阶逻辑公式写出，而当我们对这组公式做语义解释时，我们使用一个论域$U$，它包含一切数学对象（一切集合）。在这个意义下他们认为，一切数学都可以用一阶逻辑“表达”。以皮亚诺算数为例，尽管我们已经证明我们不可能写出一组一阶逻辑公式使得满足这套公式的模型一定与自然数算术模型同构，但我们总是可以写出一组一阶逻辑公式来表示一个“皮亚诺系统”——任意某个“满足”“皮亚诺公理”这一数学对象的对象，其中关系词“满足”和名词“皮亚诺公理”最终都会被还原为“集合”。

注意，我们必须要区分“在观念上认同ZFC公理系统”和“研究‘ZFC公理’这个形式系统”，这二者截然不同。不采用ZFC系统的数学家也可以研究ZFC形式系统，因为本质上他只是在研究字符串的排列组合。但是，“在观念上认同ZFC公理系统”的人会应用“他观念中ZFC系统的结论”来预测ZFC形式系统的行为。也即，不同主义的数学家因为观念不同所以会使用不同的工具，而形式系统却是客观的（对于不同主义的人而言是相同的），因为形式系统是基于物理实体的（当然，“形式系统是客观的”是我本人的观点，某些唯心主义者可能并不认同）。ZFC公理系统的信仰者之间可以用符号把ZFC公理系统中的命题写出来，并且讨论它的含义，这时他们讨论的是他们所写的符号所指向的那个他们观念中共同的东西，这就是他们对他们所写的那串符号的语义的解释。他们也可以只做口头的交流，尽管只使用模糊的自然语言，但他们仍然能够指向他们共同观念中的东西。

这样，人们本质上把观念上的数学还原为了形式上的数学。我们可以把“ZFC公理系统”本身作为观念上的数学命题的判定标准。假如这么做真的有效，那么人们就从根本上解决了“什么是数学”的问题：数学对象只是形式符号，要判断数学命题的真假只需在形式系统中判断该命题是否可证。

然而随着对逻辑系统的进一步研究，人们却不得不承认这一做法过于简单化了。首先，人们证明了连续统假设（一个集合论命题）不可能由ZFC公理推出，同时又证明了连续统假设的否定也不可能由ZFC公理推出。这说明，ZFC并不具有否定完全性(negation completeness)。如果我们要求我们的数学观念中每个命题都要有一个真或假，那么我们肯定不能把ZFC公理系统作为我们的基本观念。哥德尔进一步证明了，这种否定完全性的丧失是形式化方法本身的缺陷，任何表达能力到达一定水平的公理系统都注定会丧失否定完全性。这说明了两个问题。第一，人们目前对数学的根基是什么尚且是无知的。第二，就算我们找到了数学的根基，它也不可能被公理系统描述。或许我们必须承认，人类的语言是有局限性的，总有一部分数学真理超越了语言所能描述的范畴。当然，只用简单的自然语言是无法讨论清楚这个问题。我们必须要在下一节看到哥德尔不完全性定理的证明之后，才能对此有更深刻的理解。

参考文献

[1] H.-D. Ebbinghaus, J.Flum, W. Thomas: Mathematical Logic