chx$$\def\lra{\leftrightarrow} \def\tx#1{\text{#1}} \def\line#1#2{\ & #1 \quad & \rm{(#2)}\\} \def\linet#1#2{\ & #1 \quad & \rm{#2}\\} \def\fa{\forall} \def\ex{\exists} \def\A{\mathcal{A}} \def\B{\mathcal{B}} \def\C{\mathcal{C}} \def\D{\mathcal{D}} \def\E{\mathcal{E}} \def\G{\mathcal{G}} \def\H{\mathcal{H}} \def\I{\mathcal{I}} \def\J{\mathcal{J}} \def\K{\mathcal{K}} \def\Ax{{\bf Ax}} \def\ax{\Lambda} \def\bl{\begin{aligned}} \def\el{\end{aligned}} \def\T{\mathscr{T}} \def\t{ {\bf t} } \def\f{ {\bf f} } \def\L#1{L(#1)} \def\eq{\equiv} \def\inp{\leftarrow} \def\la#1{\langle #1\rangle} \def\ov#1{\overline{#1}} \def\wff{{\bf Wff}} \def\so{{\scr O}} \def\vd{\vdash_{L(N)}}$$
如果语言 $L$ 上的公式集 $\Gamma$ 是一致的, 那么存在模型满足 $\Gamma$ .
We prove the theorem in the case that the language $L$ is countable.
考虑构造一个 $L$ 上的结构使之满足公式集 $\Gamma$ . 我们首先扩充语言得到 $L(\N)$ 并且固定两个遍历 $L(\N)$ 中全部语句的序列 $\la{\A_i:i\in\N},\la{\B_i:i\in\N}$ 并且他们分别满足：
- 对于任意 $i,j\in\N$ 存在 $k>j$ 使得 $\A_i=\A_k$ , 对 $\la{\B_i}$ 我们也作类似的要求,
- 对于任意 $i\in\N$ , 语句 $\B_i$ 具有 $\ex x\C$ 的形式, 其中 $\C$ 是 $L$ 上的公式.
之后我们如是构造两个 $L(\N)$ 上的公式集合的序列 $\la{\Gamma_i:i\in\N},\la{\Delta_i:i\in\N}$ , 首先令 $\Gamma_0:=\Gamma$
$$\Delta_k:= \left\{ \begin{aligned} &\Gamma_k & \Gamma_k\vdash_{\L\N}\neg\A_k\\ &\Gamma_k+\A_k & {\rm otherwise} \end{aligned} \right.$$$$\Gamma_{k+1}:= \left\{ \begin{aligned} &\Delta_k+\C[x\inp\ov i_k]& \Delta_k\vdash_{\L\N}\B_{k}\,,\B_k\eq\ex x\C\\ &\Delta_k & {\rm otherwise} \end{aligned} \right.$$其中常元 $\ov i_k$ 是最小的那个 $j\in\N$ 满足 $\ov j$ 不在 $\A_0,\A_1...\A_k,\B_0,\B_1...\B_k$ 中出现的所对应的在 $L(\N)$ 中新引入的那个常数符号. 之后我们令 $L(\N)$ 上的公式集
$$\Gamma_\omega:=\bigcup_{k\in\N}\Gamma_k$$$\Gamma_\omega$ 是 $L(\N)$ 上的一致公式集.
若不然, 存在 $L(\N)$ 上的公式 $\D$ 使得 $\Gamma_\omega\vdash_{L(\N)}\D,\neg\D$ , 由于推理是有穷的, 故存在 $\Gamma_\omega$ 的有穷子集 $\Gamma'$ 使得 $\Gamma'\vdash_{L(\N)}\D,\neg\D$, 从而存在某个 $n\in\N$ 使得 $\Gamma_n$ 不一致（在 $L(\N)$ 中）. 接下来利用归纳法来证明我们证明对于 $k\in\N$ 均有 $\Gamma_k$ 是一致的.
首先验证 $\Gamma_0$ , 即$\Gamma$ , 若不一致, 则存在 $\L\N$ 上的公式 $\G$ 使得 $\Gamma\vdash_{\L\N}\G,\neg\G$ , 由于 $\L\N$ 只是在 $L$ 中添加了常数符号，所以存在 $L$ 上的公式 $\E[x_1...x_m]$ 使得 $\E[e_1...e_m]\eq\G$ 其中 $e_1...e_m$ 是新添加的常数符号, 而 $\Gamma\vdash_{\L\N}\G,\neg\G$ 即为 $\Gamma\vdash_{\L\N}\E[e_1...e_m],\neg\E[e_1...e_m]$ , 由 I.4.15 , 可取一组没出现过的变元 $z_1...z_m$ 使得 $\Gamma\vdash_L\E[z_1...z_m]$ 且 $\Gamma\vdash_L\neg\E[z_1...z_m]$ 从而 $\Gamma$ 不是 $L$ 上一致的, 与假设矛盾.
之后对于 $k\in\N$ , 由 I.H. 可以轻易得出 $\Delta_k$ 是一致的 , 假如 $\Gamma_{k+1}$ 不一致, 那么一定是 $\Delta_k\vdash_{\L\N}\B_k$ 并且 $\Gamma_{k+1}=\Delta_k+\C[x\inp \ov i]$ 这种情形, 因此存在某个 $\L\N$ 上的公式 $\H$ 使得 $\Delta_k+\C[x\inp\ov i]\vdash_{\L\N}\H,\neg\H$ , 又由于 $\Delta_k\vdash_{\L\N}\ex x\C$ 并且 $\C[x\inp\ov i]$ 是语句, 即没有自由变元, 故由 I.4.27 可得 $\Delta_k\vdash_{\L\N}\H,\neg\H$ , 矛盾.
$\Gamma_\omega$ 是 $\L\N$ 上完全的.
对于任意 $\L\N$ 上的语句 $\C$ , 根据我们的构造, 存在 $n\in\N$ 使得 $\A_n\eq\C$ , 于是假设 $\Gamma_n\vdash_{\L\N}\neg\C$ , 那么由于 $\Gamma_n\subseteq\Gamma_\omega$ 所以 $\Gamma_\omega\vdash_{\L\N}\neg\C$ ; 而另一方面如果 $\Gamma_n\not\vdash_{\L\N}\neg\C$ , 那么 $\C\in\Delta_k$ , 而由于 $\Delta_k\subseteq\Gamma_\omega$ 故 $\C\in\Gamma_\omega$ .
之后我们构造一个 $\N$ 上的关系
$$\sim:=\{(n,m)\in\N\times\N:\Gamma_\omega \vdash_{\L\N}\ov n=\ov m\}$$由 I.16 , I.17 可得 $\sim$ 是一个等价关系, 之后可以在这个关系的基础上构造出一个 $\N$ 上的函数
$$\bl {\scr O}:&\N\to\N\\ &x\mapsto \min\{y:x\sim y\} \el$$根据这个构造我们可以得到对于全体 $n\in\N$ 有 $n\sim \so(n)$ , 之后萃取 $\N$ 的子集
$$N:=\so[\N]$$并扩充语言得到 $L(N)$ , 之后对于每个 $\L\N$ 中的公式 $\C$ , 将公式中所有形如 $\ov i,i\in\N$ 的项都对应地替换为 $\ov{\so(i)}$ 所得到的公式记为 $\C^N$ , 那么显然 $\C^N$ 是 $\L N$ 上的公式. 于是我们可以导出一个 $\L N$ 上的公式集
$$\Gamma_*:=\{\C^N:\C\in\Gamma_\omega\}$$之后我们可以得到如下的 $\L\N$ 中的公式与 $\L N$ 中的公式的关系
对于 $\L\N$ 上的公式 $\C$ , $\Gamma_\omega\vdash_{\L\N}\C$ 当且仅当 $\Gamma_*\vdash_{\L N}\C^N$ .
($\inp$) 由于 $\L N$ 是 $\L\N$ 的子语言, 所以 $\Gamma_*\vdash_{\L N}\C^N$ 蕴涵 $\Gamma_*\vdash_{\L\N}\C^N$ , 而根据 I.18 可得, 对于任意的 $\L\N$ 上的公式 $\I$ 均有 $\Gamma_\omega\vdash_{\L\N}\I\lra\I^M$ , 从而对于任意 $\G\in\Gamma_*$ , 根据定义存在 $\H\in\Gamma_\omega$ 使得 $\G\eq\H^N$ , 并且 $\Gamma_\omega\vdash_{\L\N} \H\lra\H^N$ , 故 $\Gamma_\omega\vdash_{\L\N}\G$ , 从而必定有 $\Gamma_\omega\vdash_{\L\N}\C^N$ .
($\to$) 通过对$\L\N$ 上的 $\Gamma_\omega$ 的证明序列施以归纳来证明.
当 $\C\in\ax_{\L\N}$ 时, $\C^N\in\ax_{\L N}$ ; 当 $\C\in\Gamma_\omega$ 时, 根据定义有 $\C^M\in\Gamma_*$ .
(MP) 如果 $\Gamma_\omega\vdash_{\L\N} \D\to\C,\D$ , 那么根据 I.H. 有 $\Gamma_*\vdash_{\L N}\D^N\to\C^N,\D^N$ , 因此有 $\Gamma_*\vdash_{\L N}\C^N$ .
($\ex$-introduction) 假定 $\C\eq\ex x\D\to\E$ 并且 $\Gamma_\omega\vdash_{\L\N}\D\to\E$ , 其中 $x$ 不在 $\E$ 中自由出现, 则根据 I.H. 有 $\Gamma_*\vdash_{\L N}\D^N\to\E^N$ 并且根据 $\E^N$ 定义, 变元符号 $x$ 也不在 $\E^N$ 中出现, 故$\Gamma_*\vdash_{\L N}\ex x\D^N\to\E^N$ , 即 $\C^N$ .
并且我们可以接着得到如下的关于公式集 $\Gamma_*$ 的一些结果
$\Gamma_*$ 是 $\L N$ 上的一致公式集.
若不然, 则存在 $\L N$ 上的公式 $\C$ 使得 $\Gamma_*\vdash_{\L N}\C,\neg\C$ , 由于 $\L N$ 是 $\L\N$ 的子语言, $\C$ 也是 $\L\N$ 上的公式, 并且 $\C^N\eq\C$ , 从而由 Lem 3 可得 $\Gamma_\omega\vdash_{\L\N}\C,\neg\C$ , 故 $\Gamma_\omega$ 不一致, 与先前的结果矛盾.
$\Gamma_*$ 是 $\L N$ 上完全的.
对于任意 $\L N$ 上的语句 $\C$ , 显然它也是 $\L\N$ 上的, 并且 $\C^N\eq\C$, 由于 $\Gamma_\omega$ 可以在 $\L\N$ 上判定 $\C$ , 因此由 Lem 3 , $\Gamma_*$ 可以在 $\L N$ 上判定 $\C^N$ , 也就是 $\C$ 本身.
$\Gamma_*$ 具有 $\L N$ 上的 witness property.
对于任意 $\L N$ 上形如 $\ex x\C$ 的语句 $\D$ , 首先 $\D$ 也是 $\L\N$ 上的语句, 并且有 $\D^N\eq\D$ , 假如 $\Gamma_*\vdash_{\L N}\D$ , 则 $\Gamma_\omega\vdash_{\L\N}\D$ , 则根据对 $\Gamma_\omega$ 与语句序列 $\la{\B_i}$ 的构造, 存在 $n\in\N$ 使得 $\Delta_n\vdash_{\L\N}\D$ 且 $\B_n\eq\D$ , 从而存在某个 $i\in\N$ 使得 $\C[x\inp\ov i]\in\Gamma_\omega$ , 故 $\C[x\inp\ov{\so(i)}]\in\Gamma_*$ .
借助这些结果我们可以构造出一个 $L$ 上的结构 $M:=(N,\T)$ , 我们主要描述 $\T$ 的组成部分,
对于 $L$ 上的 $k$ 元谓词符号 $P$ , 定义它在 $M$ 中的对应如下
$$P^M:=\{\la{i_1...i_k}\in N^k:\Gamma_*\vdash_{\L N}P(\ov{i_1}...\ov{i_k})\}$$对于 $L$ 上的 $k$ 元函数符号 $f$ , 首先显然有, 对于任意的 $\la{i_1...i_k}\in N^k$ 均有 $\vdash_{\L N}(\ex x)x=f(\ov{i_1}...\ov{i_k})$ , 由 Lem 6 可知存在某个 $j\in N$ 使得 $\Gamma_*\vdash_{\L N}\ov j=f({\ov{i_1}...\ov{i_k}})$ , 并且根据我们对 $\so$ 与 $N$ 的构造这个 $j$ 是唯一的, 于是这就导出了 $f$ 在 $M$ 中的对应
$$f^M:=\{\la{i_1...i_k,j}\in N^{k+1}:\Gamma_*\vdash_{\L N}\ov j=f(\ov{i_1}...\ov{i_k})\}$$对于 $L$ 上的常数符号 $c$ , 同理函数符号的情形可得存在唯一 $c'\in N$ 使得 $\Gamma_*\vdash_{\L N}c=\ov{c'}$ , 于是 $c$ 在 $M$ 中的对应
$$c^M:=c'$$
之后我们将 $\T$ 拓充到新引入的常数符号上, 并考虑证明如下的一个结论.
对于 $\L N$ 上的任意闭项 $t$ 均有 $\Gamma_*\vdash_{\L N} t=\ov{t^{M}}$ .
通过对项 $t$ 施以归纳来证明.
当 $t$ 是 $L$ 中的常数符号或者新引入的常数符号时, 根据我们对 $M$ 的构造结论成立.
当 $t\eq f(t_1...t_k)$ 时, 根据递归定义, $t^M=f^M(t_1^M...t_k^M)$ , 根据我们对 $M'$ 的构造, $f^{M}(t_1^{M}...t_k^{M})$ 是那个唯一的 $s\in N$ 使得 $\Gamma_*\vdash_{\L N}\ov s=f(\ov{t_1^M}...\ov{t_k^M})$ 即 $s=t^M$ , 从而 $\ov s\eq \ov{t^M}$, 由 I.H. 对于 $i=1,2,...k$ 均有 $\Gamma_*\vdash_{\L N}t_i=\ov{t_i^M}$ , 从而根据 I.18 有 $\Gamma_*\vdash_{\L N}\ov s=f(t_1...t_k)$ 即 $\Gamma_*\vdash_{\L N}\ov s=t$ .
之后可以得到主引理.
对于 $\L N$ 上语句 $\C$ 均有: $\C^M=\t$ 当且仅当 $\Gamma_*\vdash_{\L N}\C$ .
我们对语句 $\C$ 施以归纳.
当 $\C$ 是原子公式时, 如果 $\C\eq P(t_1...t_k)$ , 则 $\C^M=\t$ 当且仅当 $\la{t_1^M...t_k^M}\in P^M$ , 根据对 $M$ 的构造, 它等价于 $\Gamma_*\vdash_{\L N} P(\ov{t_1^M}...\ov{t_k^M})$ , 再由 Lem 7 以及 I.18 可得 $\Gamma_*\vdash_{\L N}P(\ov{t_1^M}...\ov{t_k^M})\lra P(t_1...t_k)$ , 从而 $\Gamma_*\vdash_{\L N} P(\ov{t_1^M}...\ov{t_k^M})$ 当且仅当 $\Gamma_*\vdash_{\L N}P(t_1...t_k)$ 即 $\C$ ; 如果 $\C\eq t_1=t_2$ , 则 $\C^M=\t$ 当且仅当 $t_1^M=t_2^M$ , 由 $\Ax.3$ 得 $\vdash_{\L N}\ov{t_1^M}=\ov{t_2^M}$ , 从而再由 Lem 7 以及 I.19 可得 $\Gamma_*\vdash_{\L N}t_1=t_2$ , 而另一方面若 $t_1^M\not=t_2^M$ , 则根据我们对 $N$ 的构造可知 $\Gamma_*\not\vdash_{\L N}\ov{t_1^M}=\ov{t_2^M}$ , 从而不可能有 $\Gamma_*\vdash t_1=t_2$ , 不然由 Lem 7 以及 I.19 可以推出 $\Gamma_*\vdash_{\L N}\ov{t_1^M}=\ov{t_2^M}$ .
对于逻辑连词的情况, 如果 $\C\eq\neg\D$ , 则 $\C^M=\t$ 当且仅当 $\D^M=\f$ , 根据 I.H. 这等价于 $\Gamma_*\not\vdash_{\L{N}}\D$ , 而由于 $\Gamma_*$ 是完全的故 $\Gamma_*\vdash_{\L N}\neg\D$ , 也就是 $\C$ ; 如果 $\C\eq\D\or\E$ , 则 $\C^M=\t$ 当且仅当 $\D^M=\t$ 或者 $\E^M=\t$ , 这根据 I.H. 这等价于 $\Gamma_*\vd\D$ 或者 $\Gamma_*\vd\E$ , 而 $\vd\D\to\D\or\E,\E\to\D\or\E$ , 因此 $\C^M=\t$ 蕴涵 $\Gamma_*\vd\D\or\E$ , 即 $\Gamma_*\vd\C$ , 另一方面如果 $\Gamma_*\not\vd\D,\E$ 则根据完全性有 $\Gamma_*\vd\neg\D,\neg\E$ 从而有 $\Gamma_*\vd\neg\D\and\neg\E$ 从而 $\Gamma_*\vd\neg\C$ , 而由一致性可得 $\Gamma_*\not\vd\C$ .
对于量词的情况, 假设 $\C\eq\ex x\D$ , 则 $\C^M=\t$ 当且仅当存在 $i\in N$ 使得 $(\D[x\inp\ov i])^M=\t$ , 根据 I.H. 这等价于 $\Gamma_*\vd\D[x\inp\ov i]$ , 如果 $\C^M=\t$ 则取出这样的 $i$ 并得到 $\Gamma_*\vd\D[x\inp\ov i]$ 之后再由 $\Ax.2$ 可得 $\Gamma_*\vd\ex x\D$ , 而另一方面如果 $\Gamma_*\vd\ex x\D$ 则由 witness property 可知这样的 $i$ 存在, 所以 $\C^M=\t$ .
最后我们来验证 $M\vDash_L\Gamma$ . 对于任意的 $\C\in\Gamma$ , 由于 $\C$ 是 $L$ 上的公式故 $\C^N\eq\C$ , 又因为 $\Gamma\subseteq\Gamma_\omega$ 故 $\C\in\Gamma_\omega$ 从而 $\C\in\Gamma_*$ , 而对于 $\C$ 的任意 $M$-instance $\C'$ , 由 I.4.12 可得 $\Gamma_*\vd\C'$ , 又由于 $\C'$ 是 $\L N$ 上的语句所以 $\C'^M=\t$ , 因此有 $M\vDash_L\C$ .