书中很多术语看起来挺”外星人”语言的, 按照我初次阅读完的内容理解, 下面定理所说的协调的与现代常说的相容性是一个意思.

阅读需要知道的定义:

句子: 一个合式公式$X$, 若不包含任何变量的自由出现, 就称为一个句子.
合式公式按照以下步骤构造
- 若$X$是一个原子公式, 则$[X]$是一个合式公式
- 若$X$和$Y$是合式公式, 则$[\lnot X]$, $[X\lor Y]$, $[X\land Y]$, $[X\supset Y]$, $[X\equiv Y]$是合式公式
- 若$X$是一个合式公式, 而$y$(代表任意的变量)不在$X$的量词中出现, 也就是说$X$不包含$(\exists y)$或$(\forall y)$, 则$[(\exists y)X]$和$[(\forall y)X]$是合式公式.
前束范式: 在$L$中的一个合式公式$X$, 若$X$是有原子公式先经逻辑连接符(可以没有)再经量词(也可以没有)作用而构成, 则称$X$是前述范式.
协调的: 一个句子集若有一个模型, 就称为协调的.
超滤: 设$D$是$I$的子集族, 且满足: (i) $\varnothing\notin D$; (ii) 若$A\in D$, $B\in D$, 则$A\cap B\in D$; (iii) 若$A\in D$且$A\subset B\subset I$, 则$B\in D$; (iv) 若任何$A\subset I$, 或者有$A\in D$或者有$I-A\in D$. 则称$D$是$I$上的一个超滤(ultrafilter). 或说是$I$的子集族组成的Boole代数中的极大对偶理想.

graph LR;
  A[合式公式]-->|先经逻辑连接符再经量词作用成|E[前束范式];
  F[原子公式]-->|加括号,逻辑连接词,量词|A;
  A-->|不出现任何变量|B[句子];
  B-->|有模型的句子集|G[协调的];

定理: 令$K$是一个句子集, 若$K$的每个有穷子集是协调的, 则$K$是协调的.

证明:

Step 1: 不妨设$K$的一切句子都是前束范式, 否则用前束范式定理将相应的句子替换为等价的前束范式的句子, 得到新的句子集$K_{0}$.

若$K$的每个有穷子集是协调的, 且$K_{0}’$是$K_{0}$的一个有穷子集.

则$K_{0}’$对应$K$的有穷子集$K’$, $K’$中的句子通过前束范式等价替换与$K_{0}’$一一对应.

因$K’$是协调的, $K’$上的模型也是$K_{0}’$上的模型. 即$K_{0}’$也是协调的. 反之亦然.

对于前束范式的句子, 一个解释的方式是Skolem和Hilbert给出的, 并由Herbrand进一步发展.

考虑句子$X=(\forall x)(\exists y)Q(x,y)$, 其中$Q(x,y)$是一个合式公式.

$X$在结构$M$内成立是指: 对于每个个体常项$a$, 它对应于$M$的一个个体, 即恒存在一个个体常项$b$使得$Q(a,b)$在$M$内成立.

由选择公理, 对每个$a$, 可以选出这样的$b$. 因此可以说存在一个定义在个体常项集(对应$M$的个体), 且取值在同一集上的函数$\phi(x)$, 称为Skolem函数或函子, 使得在此集内的每个$a$, $Q(a,\phi(a))$在$M$内成立. 这里, $\phi$是个体常项($L$内的事物)到个体常项的函数.

因此若$a,b$分别对应$M$内的个体$a’,b’$, 且$b=\phi(a)$, 则也可记作$b’=\phi(a’)$.

而从函数$\phi$的存在性推出句子$(\forall x)(\exists y)Q(x,y)$在$M$内成立.

表达式$Q(x,\phi(x))$是形式语言之外的, 称为Skolem开形句子.

称$Q(x,\phi(x))$在$M$内成立, 就是对于任何个体常项$a$, 它对应$M$的个体, 有$Q(a,\phi(a))$在$M$内成立.

Step 2: 假定$K$是一个前束范式的句子集, 且$K$的每个有穷子集是协调的.

现在构造一个$K$的超积形状的模型.

将$K$的一切有穷子集的集定义为指标集$I$, 从而$I$不空.

对每个$\nu\in I$, 选择相应的结构$M_{\nu}$, 使得在某个特殊映射$C_{\nu}$下$M_{\nu}$是$\nu$的一个模型.

按照假设, 对于每个$\nu\in I$, 结构$M_{\nu}$是存在的, 但当$I$是无穷集时, 断言带指标的集合$Q=\left\{ M_{\nu}\right\} _{\nu\in I}$的存在性需要选择公理.

对于每个$\nu$, $C_{\nu}$是$\nu$的句子中个体常项与关系符号到$M_{\nu}$的相应个体和关系上的映射.

如果$M_{\nu}$内不同的关系被$K$内的同一个关系符号所对应, 就把它们看成是同一个关系.

因为关系符号$R$在$\nu$的句子中可以不出现. 如果对于某个$\nu$, $K$的一个关系符号$R$不对应$M_{\nu}$内的任何关系. 则在$M_{\nu}$内任意定义一个相应的关系$R’$, $R’$与$R$有相同个数的变量, 如规定$R’$对$M_{\nu}$内的任何一组个体都不成立.

由此保证了$Q=\left\{ M_{\nu}\right\} $中的所有结构都是相似的. 下面在$I$上选择一个适当的超滤$D$.

Step 3: 对每个$\nu\in I$, 令

$d_{\nu}=\left\{ \mu\in I:\nu\subset\mu\right\},$

令$D_{0}=\left\{ d_{\nu}\right\} _{\nu\in I}$. 则$D_{0}$有下列性质:

(i). $\varnothing\notin D_{0}$. 因为若$A\in D_{0}$, 则对某个$\nu\in I$, 有$A=d_{\nu}$, 从而$\nu\in A$, 所以$A\ne\varnothing$.

(ii). 若$A\in D_{0}$, 且$B\in D_{0}$, 则$A\cap B\in D_{0}$.

证明: 若$A\in D_{0}$, 且$B\in D_{0}$, 则$I$中有$\nu,\mu$使得$A=d_{\nu}$, $B=d_{\mu}$. 令$\sigma=\nu\cup\mu$, 则$\sigma$是$K$的一个有限子集, 从而是$I$中的元素.

若$\rho\in A\cap B$, 则$\rho\supset\nu$, $\rho\supset\mu$. 从而$\rho\supset\mu\cup\nu$. 因此$\rho\in d_{\sigma}$. 而$\rho\in d_{\sigma}$推出$\rho\supset\sigma$, $\rho\supset\nu$, $\rho\supset\mu$, 所以$\rho\in A$, $\rho\in B$, $\rho\in A\cap B$.

所以$A\cap B=d_{\sigma}$, 从而$A\cap B\in D_{0}$.

考虑一切$D_{0}$的扩张并满足上述条件(i)和(ii)的$I$的子集的集合. 有Zorn引理, 这些集合有极大元, 令$D$是这样的极大元. 则$D$有性质:

(iii) 若$A\in D$, 且$A\subset B\subset I$, 则$B\in D$.

证明: 令
$D'=\left\{ B\mid B\subset I\text{ 且对于某个 }A\in D\text{ 有 }A\subset B\right\} .$
则$D’$是$I$的子集族, $D\subset D’$.

若$B\in D’$, 因为$B$包含一个$D$的元素$A$为子集, 而$A$不能是空集, 所以$B\ne\varnothing$.

若$B$和$B’$都属于$D’$, 则有$A,A’\in D$, 使得$B\supset A$, $B’\supset A’$. 所以$B\cap B’\supset A\cap A’$.

由于$D$是$D_{0}$在满足(i), (ii)时的扩张, 由(ii)知, $A\cap A’\in D$. 所以$B\cap B’\in D’$.

因此$D’$也是$I$的子集的集合, 并满足(i), (ii). 由$D$是极大元, 所以$D=D’$.

(iv) 若$A\subset I$, 则$A\in D$或$I-A\in D$.

证明: 由于$A\cap(I-A)=\varnothing$, 所以$A$和$I-A$不能都属于$D$.

假设$A\subset I$, 而$A$和$I-A$都不属于$D$. 定义
$D_{1}=\left\{ B\mid B=C\cap F,\text{ 其中 }A\subset C\subset I\text{ 且 }F\in D\right\} .$
若$F\in D$, 取$C=I$, 则$B=F\in D_{1}$, 所以$D\subset D_{1}$.

若$B\in D_{1}$且$B’\in D_{1}$, 有$D_{1}$的定义, 存在$C,F,C’,F’$, 满足$A\subset C\subset I$, $F\in D$, $A\subset C’\subset I$, $F’\in D$, 使得$B=C\cap F$, $B’=C’\cap F’$, 则$B\cap B’=(C\cap C’)\cap(F\cap F’)$, 其中$A\subset C\cap C’\subset I$, 且$F\cap F’\in D$, 从而$B\cap B’\in D_{1}$.

再在$D_{1}$的定义中取$C=A$, $F=I$, 就有$A\in D_{1}$.

由此$D_{1}$是满足条件(ii)的$D$的真扩张.

由$D$的极大性知, $D_{1}$不能满足条件(i), 所以$\varnothing\in D_{1}$, 即存在$F_{1}\in D$使得$A\cap F_{1}=\varnothing$.

类似地, 定义
$D_{2}=\left\{ B\mid B=C\cap F,\text{ 其中 }I-A\subset C\subset I\text{ 且 }F\in D\right\} .$
知存在$F_{2}\in D$使得$(I-A)\cap F_{2}=\varnothing$.

现在令$F_{3}=F_{1}\cap F_{2}$, 则$F_{3}\in D$, 且
$\begin{align*} F_{3} & =I\cap F_{3}=\left(A\cup(I-A)\right)\cap F_{3}\\ & =(A\cap F_{3})\cup\left((I-A)\cap F_{3}\right)\\ & =\left(A\cap(F_{1}\cap F_{2})\right)\cup\left((I-A)\cap(F_{1}\cap F_{2})\right)\\ & \subset(A\cap F_{1})\cup\left((I-A)\cap F_{2}\right)=\varnothing. \end{align*}$
矛盾.

Step 4: 由超滤的定义, $D$是$I$上的超滤. 下证: 在$K$的个体常项与关系符号的一个适当的解释$C_{K}$下, 超积$Q_{D}\left(Q=\left\{ M_{\nu}\right\} \right)$是$K$的一个模型.

对于$K$内的一个给定关系符号$R$, 把$R$看成是对应在所有$M_{\nu}$内都出现的一个关系$R’$.

由超积的定义, $R’$也出现在$Q_{D}$内, 定义在$C_{K}$下$R$对应到$Q_{D}$内的关系为$R’$. $K$的个体常项在$C_{K}$下的解释: 令$a$是出现在$K$中的个体常项, 即$a$至少在$K$的一个句子中出现.

在$I$上定义函数$f(\nu)$使得$f(\nu)\in M_{\nu}$. 若$\nu$的某个句子包含$a$, 则$M_{\nu}$包含个体$a’$, 它在$C_{\nu}$之下对应$a$, 就取$f(\nu)=a’$.

若$a$不出现在$\nu$中, $f(\nu)$取$M_{\nu}$中的任意元素.

令$X$是$K$的任意一个句子. 根据假设, $X$是前束范式.

要证明$X$在$Q_{D}$内成立, 或等价地, 证明在$Q_{D}$内能定义Skolem函数使其在$Q_{D}$内成立.

可以假定对于$X\in\nu$的所有$M_{\nu}$内已经选出了适当的Skolem函数, 并且$M_{\nu}$内的其它元素上已经随意定义好了, 且各函数值与相应的自变量分别属于同一个结构$M_{\nu}$.

接下来的证明是通过一个具体的例子给出的, 暂时略去.

Reference

¹. 非标准分析, Robison ↩