2.3. 一阶逻辑的语义

我们将要学习的对于真的刻画来自于 Tarski 的工作, 其后有更加丰富的哲学意蕴——但我们暂且放下这些讨论.

结构

定义 2.3.0.1. 对于某个语言 $L$ , 我们称满足以下条件的 $M = {M, F, P, -^{M}}$ 为这个语言的一个结构:

1.	$M$ 是集合, $F \subseteq {f : M^{(n)} \to M ∣ n \in ω}$ , $P \subseteq ⋃_{n \in ω} M^{(n)}$ .
2.	$-^{M} : L :: F \cup L :: P \to M :: F \cup M :: P$ 是双射.
3.	对函数符号 $f \in L :: F$ , $dom f^{M} = M^{L :: a_{F} (f)}$ .
4.	对谓词符号 $P \in L :: P$ , $P^{M} \subseteq M^{L :: a_{P} (P)}$ .

我们还将把形如 $ass : L :: X \to M$ 的函数称作这个结构上的一个原始赋值.

评注. 我们提醒读者一个集合论上的小问题: 我们定义有序对 $(a, b) = {{a}, {a, b}}$ , 然后递归地定义 $X^{(2)} = X \times X = {(a, b) ∣ a, b \in X}$ , $X^{(n + 1)} = X \times X^{(n)}$ . 虽然显然 $X^{(n)}$ 和 $X^{n} = {f : n \to X}$ 之间有典范的双射, 但从定义上它们是不一样的. 我们会把 $X^{n}$ 里的元素记为 $⟨ x_{0}, ..., x_{n - 1} ⟩$ , 而把 $X^{(n)}$ 里的元素记为 $(x_{0}, ..., x_{n - 1})$ .

同样的, 你会发现二元函数是 $f : X^{(2)} \to Y$ 而不是 $f : X^{2} \to Y$ , 因此我们简写的是 $f (x_{1}, x_{2}) = f ((x_{1}, x_{2}))$ 而非 $f (x_{1}, x_{2}) = f (⟨ x_{1}, x_{2} ⟩)$ , 这也与直观相符.

显然, 原始赋值会帮我们把

L

里的项实现为

M

可定义的一些集合, 进而把

L

里的公式翻译为

M

看到的一些集合论的事实. 我们下面来详细叙述这个操作.

定义 2.3.0.2. 给定 $L$ 的结构 $M$ 上的一个原始赋值 $ass$ , 我们递归地定义一个 $Ass : L :: Term \to M :: M$ 如下:

1.	$Ass (x_{n}) = ass (x_{n})$ .
2.	$Ass (f (t_{0}, ..., t_{n - 1})) = f^{M} (Ass (t_{0}), ..., Ass (t_{n - 1}))$ .

我们称这个 $Ass$ 为原始赋值 $ass$ 生成的赋值.

给定原始赋值 $ass$ , 我们对每个 $x_{n} \in L :: X$ 和 $a \in M$ 定义 $let_{a}^{x_{n}} (ass)$ 为一个新的原始赋值, 它除了将 $x_{n}$ 映到 $a$ 之外与原先的 $ass$ 保持一致. 这个新的原始赋值生成的赋值同样记为 $let_{a}^{x_{n}} (Ass)$ .

现在, 我们对所有的原始赋值 $ass$ 定义一个关系 $⊨$ , 对 $L :: Formula$ 的长度归纳:

1.	$(M, ass) ⊨ t_{0} \approx t_{1}$ 当且仅当 $Ass (t_{0}) = Ass (t_{1})$ .
2.	$(M, ass) ⊨ P (t_{0}, ..., t_{n - 1})$ 当且仅当 $(Ass (t_{0}), ..., Ass (t_{n - 1})) \in P^{M}$ .
3.	$(M, ass) ⊨ \neg φ$ 当且仅当 $\neg ((M, ass) ⊨ φ)$ , 右侧通常也简写为 $(M, ass) \neq ⊨ φ$ .
4.	$(M, ass) ⊨ (φ \to ψ)$ 当且仅当 $(M, ass) \neq ⊨ φ$ 或者 $(M, ass) ⊨ ψ$ .
5.	$(M, ass) ⊨ \forall x (ψ)$ 当且仅当对每个 $a \in M$ 都有 $(M, let_{a}^{x} (ass)) ⊨ ψ$ .

这个 $⊨$ 称作满足, $(M, ass) ⊨ φ$ 读作结构 $M$ 在赋值 $ass$ 下满足 $φ$ .

我们继续定义另一种

⊨

.

定义 2.3.0.3. 如果对任何满足公式集 $Γ$ 中所有公式的结构 $M$ 和其上的赋值 $ass$ 均有 $(M, ass) ⊨ φ$ , 则称 $Γ$ (语义) 蕴含 $φ$ , 记为 $Γ ⊨ φ$ . 我们同样将 ${ψ} ⊨ φ$ 简记为 $ψ ⊨ φ$ .

首先, 我们指出满足只与自由变元的赋值有关.

定理 2.3.0.4. 如果两个原始赋值 $ass_{1}$ 与 $ass_{2}$ 满足 $ass_{1} ∣_{fVar (φ)} = ass_{2} ∣_{fVar (φ)}$ , 则 $(M, ass_{1}) ⊨ φ$ 当且仅当 $(M, ass_{2}) ⊨ φ$ . 换言之, 只需要确定 $ass$ 在有穷集 $fVar (φ)$ 上的取值就足以确定是否有 $(M, ass) ⊨ φ$ .

证明. 对 $φ$ 的长度归纳. 首先, 不难归纳证明如果 $ass_{1}$ 与 $ass_{2}$ 满足对在某个项 $t$ 中出现的全体变元符号赋值相同, 则 $Ass_{1} (t) = Ass_{2} (t)$ .

1.	如果 $φ$ 形如 $P (t_{0}, ..., t_{n - 1})$ , 由上知 $Ass_{1} (t_{i}) = Ass_{2} (t_{i})$ , 因此显然有 $(M, ass_{1}) ⊨ φ$ 当且仅当 $(M, ass_{2}) ⊨ φ$ .
2.	如果 $φ$ 形如 $\neg ψ$ 或 $(ϕ \to ψ)$ , 证明是简单的.
3.	如果 $φ$ 形如 $\forall x (ψ)$ , 如果 $x$ 不是 $ψ$ 的自由变元则显然, 否则对 $ψ$ 运用归纳假设, 注意到 $φ$ 的自由变元恰好是 $ψ$ 的自由变元去掉 $x$ , 而根据这时候满足的定义我们会确定 $x$ 的赋值, 即得证.

$□$

推论 2.3.0.5. 对含 $n$ 个自由变元的公式 $φ (x_{m_{0}}, ..., x_{m_{n - 1}})$ , $(M, ass) ⊨ φ$ 可以记为 $M ⊨ φ [ass (x_{m_{0}}), ..., ass (x_{m_{n - 1}})]$ .

现在, 我们来建立一阶逻辑的可靠性定理. 我们先给出一个引理.

引理 2.3.0.6 (替换引理). 如果 $Sub_{t}^{x} (φ)$ , 则 $(M, ass) ⊨ sub_{t}^{x} (φ)$ 当且仅当 $(M, let_{Ass (t)}^{x} (ass)) ⊨ φ$ .

证明. 对公式 $φ$ 实行归纳.

1.	$φ$ 形如 $P (t_{0}, ..., t_{n - 1})$ . 此时 $(M, ass) ⊨ Sub_{t}^{x} (P (t_{0}, ..., t_{n - 1}))$ 当且仅当 $(Ass (Sub_{t}^{x} (t_{0})), ..., Sub_{t}^{x} (t_{n - 1})) \in P^{M}$ 当且仅当 $(let_{Ass (t)}^{x} Ass (t_{0}), ..., let_{Ass (t)}^{x} Ass (t_{n - 1})) \in P^{M}$ 当且仅当 $(M, let_{Ass (t)}^{x} ass) ⊨ P (t_{0}, ..., t_{n - 1})$ .
2.	$φ$ 形如 $t_{1} \approx t_{2}$ . 与上类似.
3.	$φ$ 形如 $\forall y (ψ)$ . 此时若 $x$ 不在 $φ$ 中自由出现, 则由自由变元决定性显然. 下讨论自由出现的情形: 注意到无冲突替换要求 $y$ 不在 $t$ 出现且 $t$ 在 $ψ$ 中也可以无冲突替换, 这说明对任何 $d \in M$ 都有 $Ass (t) = let_{d}^{y} Ass (t)$ . 又注意到 $Sub_{t}^{x} (φ) = \forall y (Sub_{t}^{x} (ψ))$ , 可如下做连续等价推导: $(M, ass) ⊨ sub_{t}^{x} (φ)$ 当且仅当对所有的 $d \in M$ , $(M, let_{d}^{y} ass) ⊨ Sub_{t}^{x} (ψ)$ 当且仅当对所有的 $d \in M$ , $(M, let_{let_{d}^{y} Ass (t)}^{x} let_{d}^{y} (ass)) ⊨ ψ$ 当且仅当对所有的 $d \in M$ , $(M, let_{Ass (t)}^{x} let_{d}^{y} (ass)) ⊨ ψ$ 当且仅当对所有的 $d \in M$ , $(M, let_{d}^{y} let_{let_{d}^{y} Ass (t)}^{x} (ass)) ⊨ ψ$ 当且仅当 $(M, let_{Ass (t)}^{x} (ass)) ⊨ ψ$ .
4.	$φ$ 形如 $\neg ψ$ . 此时 $(M, ass) ⊨ Sub_{t}^{x} (φ)$ 当且仅当 $(M, ass) \neq ⊨ Sub_{t}^{x} (ψ)$ 当且仅当 $(M, let_{Ass (t)}^{x} ass) \neq ⊨ ψ$ 当且仅当 $(M, let_{Ass (t)}^{x} ass) ⊨ φ$ .
5.	$φ$ 形如 $(ϕ \to ψ)$ . 类上.

综合五情况证毕.

$□$

定理 2.3.0.7 (可靠性定理). $Γ ⊢ ψ$ 则 $Γ ⊨ ψ$ .

证明. 显然我们会对证明序列归纳, 证明满足 $Γ$ 中每个公式的 $(M, ass)$ 同样满足证明序列中的每一个公式, 从而满足最后一个公式. 换言之, 我们只需证明它总是满足逻辑公理, 且满足 MP 规则. 我们先来验证没有经过全称概括的那些逻辑公理.

1.	前三条逻辑公理: 直接验算真值表即可. 以第一条为例, $(M, ass) ⊨ φ$ 总是不真则假, $(M, ass) ⊨ ψ$ 亦然, 只需列举四种可能情况, 根据定义发现在每种情况下均有 $(M, ass) ⊨ (φ \to (ψ \to φ))$ 即可.
2.	第四条逻辑公理:
3.	第五条逻辑公理:
4.	第六条逻辑公理:
5.	第七条逻辑公理: 根据 $\forall a \in M (a = a)$ 恒成立显然.
6.	第八条逻辑公理: 考察所有满足 $x \approx y$ 的结构与赋值, 不难归纳得出它在每个项上都可以将任意个 $x$ 替换为 $y$ 而不改变赋值, 进而将任意个 $x$ 替换为 $y$ 不改变原子公式的真假, 进而不改变全体公式的真假.

由于以上所有证明均为对 $ass$ 做任何要求, 根据 (元语言的) 概括定理, 我们就证明了以上所有公式的所有全称概括都被任何 $(M, ass)$ 满足, 换言之任何逻辑公理都被任何 $(M, ass)$ 满足.

最后, 只需要证明

(M, ass) ⊨ (φ \to ψ)

且

(M, ass) ⊨ φ

时,

(M, ass) ⊨ ψ

. 这可以直接根据满足的定义得出.

$□$

结构之间的态射

我们现在先来定义什么叫模型.

定义 2.3.0.8. 给定句子集 $Γ$ , 我们令 $fVar (Γ) = ⋃ {fVar (φ) ∣ φ \in Γ}$ 为这个句子集的自由变元集.

如果 $fVar Γ = {x_{i} ∣ i \in I}$ , 这里指标集 $I \subseteq ω$ . 给定结构 $M$ 和, 如果一个 $\overset{a}{ˉ} \in M^{I}$ 满足对任意 $φ (x_{i_{j}}) \in Γ$ 都有 $M ⊨ φ [a_{i_{j}}]$ , 这里 ${i_{j} ∣ x_{i_{j}} \in fVar (φ)} \subseteq I$ , 我们就称 $(M, \overset{a}{ˉ})$ 是 $Γ$ 的模型, 记为 $M ⊨ Γ [\overset{a}{ˉ}]$ .

特别的, 如果 $fVar (Γ) = \emptyset$ , 换言之 $Γ$ 是一个理论, 则简略的记 $M ⊨ Γ [{\emptyset}]$ 为 $M ⊨ Γ$ .

评注. 结构现在可以理解为空理论 (一句话也没有的理论) 的模型.

我们定义一个与一致性并驾齐驱的性质.

定义 2.3.0.9. 如果句子集 $Γ$ 有模型, 则称它可满足.

我们马上得到以下定理.

定理 2.3.0.10. 如果一个句子集是可满足的, 那么这个句子集一致.

证明. 否则, 这个句子集的模型会满足

⊥

, 这显然是不可能的.

$□$

这个定理的逆命题也是正确的, 但是其证明并不简单. 事实上, 它是下一节要证明的东西的推论.

我们先来继续探讨结构之间的态射这个话题. 我们希望定义某种结构之间的函数, 使得一个理论的全体模型构成一个好的范畴.

定义 2.3.0.11. 对语言 $L$ 的理论 $T$ 的两个模型 $M$ 与 $N$ , 我们直接记 $M :: M$ 为 $M$ , 记 $N :: M$ 为 $N$ , 若 $F : M \to N$ 具有如下性质:

1.	$\forall f \in L :: F \forall (a_{0}, ...,, a_{n - 1}) \in M^{(n)} (F (f^{M} (a_{0}, ..., a_{n - 1})) = f^{N} (F (a_{0}), ..., F (a_{n - 1})))$
2.	$\forall P \in L :: P \forall (a_{0}, ..., a_{n - 1}) \in M^{(n)} ((a_{0}, ..., a_{n - 1}) \in P^{M} \to (F (a_{0}), ..., F (a_{n - 1})) \in P^{N})$

则称 $F$ 是一个同态, 记为 $F : M \to N$ .

如果 $F$ 是单射、同态, 且满足 $\forall P \in L :: P \forall (a_{0}, ..., a_{n - 1}) \in M^{(n)} ((F (a_{0}), ..., F (a_{n - 1})) \in P^{N} \to (a_{0}, ..., a_{n - 1}) \in P^{M})$ , 则称 $F$ 是一个嵌入.

如果 $F$ 是满射、嵌入, 则称 $F$ 是同构. 此时我们也称 $M$ 与 $N$ 同构.

如果 $M \subseteq N$ 使得 $i : M \to N, a \mapsto a$ 是嵌入, 则称 $M$ 是 $N$ 的子结构, 记为 $M < N$ .

定理 2.3.0.12. 同态复合同态仍是同态, 嵌入复合嵌入仍是嵌入, 结构之间的同构是一个等价关系.

证明是简单的. 然而我们通常至少考虑嵌入而非同态, 这是因为嵌入有另一种表述方式.

定义 2.3.0.13. 我们考虑同态 $F : M \to N$ 的如下性质:

1.	如果 $\forall φ (x_{m_{0}}, ..., x_{m_{n - 1}}) \in L :: qfFormula \forall (a_{0}, ..., a_{n - 1}) \in M^{n} (M ⊨ φ [a_{0}, ..., a_{n - 1}] \leftrightarrow N ⊨ φ [F (a_{0}), ..., F_{a_{n - 1}}])$ , 则称 $F$ 是嵌入.
2.	如果 $\forall φ (x_{m_{0}}, ..., x_{m_{n - 1}}) \in L :: Formula \forall (a_{0}, ..., a_{n - 1}) \in M^{n} (M ⊨ φ [a_{0}, ..., a_{n - 1}] \leftrightarrow N ⊨ φ [F (a_{0}), ..., F_{a_{n - 1}}])$ , 则称 $F$ 是初等嵌入.

如果 $M \subseteq N$ 使得 $i : M \to N, a \mapsto a$ 是嵌入, 则称 $M$ 是 $N$ 的子结构, 记为 $M < N$ . 如果 $M \subseteq N$ 使得 $i : M \to N, a \mapsto a$ 是初等嵌入, 则称 $M$ 是 $N$ 的初等子结构, 记为 $M ≺ N$ .

定理 2.3.0.14. 以上两种对嵌入的定义等价.

证明.

$□$

子结构是通过限制得到的结构, 这一观察体现为以下定理.

定理 2.3.0.15.

证明.

$□$

进而, 我们可以把嵌入和初等嵌入都分成两个部分.

定理 2.3.0.16. 如果存在 $M$ 到 $N$ 的嵌入, 则存在 $N$ 的子结构与 $M$ 同构. 如果存在 $M$ 到 $N$ 的初等嵌入, 则存在 $N$ 的初等子结构与 $M$ 同构.

证明.

$□$

评注. 由于同构的模型不应加以区分, 我们将宽泛的在存在 $M$ 到 $N$ 的嵌入时就称 $M$ 是 $N$ 的子结构, 在存在 $M$ 到 $N$ 的初等嵌入时就称 $M$ 是 $N$ 的初等子结构.

初等子结构是最妙的子结构, 因为我们如果考察结构的理论, 就会发现以下事实.

定理 2.3.0.17. $M ≺ N$ 时, $Th (M) = Th (N)$ .

证明.

$□$

我们还有一种有趣的方式来考虑 $M$ 到别的结构的嵌入和初等嵌入.

定义 2.3.0.18. 给定语言 $L$ 和集合 $M$ , 我们给定一个新的语言 $L_{M}$ 如下:

1.	$L_{M} :: F = L :: F \cup {\overset{a}{˙} ∣ a \in M}$ , $(L_{M} :: a_{F}) : \overset{a}{˙} \mapsto 0$ . 这些 $\overset{a}{˙}$ 称为 $a$ 的名.
2.	$L_{M} :: P = L :: P$ .

注意到名都是 $0$ 元函数, 我们以后也会令语言 $L$ 中的全体零元函数构成的集合为 $L :: C$ , 零元函数称为常元. 不难意识到, 它们的性质介于变元和函数之间.

自然的想法是把

M :: M

加入原有的语言

L

中, 但我们还想知道

M

作为结构的性质, 因此有必要在新的语言中保留它们.

定义 2.3.0.19. 对语言 $L$ 的结构 $M$ , 我们考虑以下两个 $L_{M}$ 的理论:

1.

$Diag (M) = {Sub_{(\overset{a_{0}}{˙}, ..., \overset{a_{n - 1}}{˙})}^{(x_{m_{0}}, ..., x_{m_{n - 1}})} φ (x_{m_{0}}, ..., x_{m_{n = 1}}) ∣ φ \in L :: qfFormula, L :: fVar (φ) = {x_{m_{0}}, ..., x_{m_{n - 1}}}, (a_{0}, ..., a_{n - 1}) \in M^{(n)}, M ⊨ φ [a_{0}, ..., a_{n - 1}]}$ , 它称作 $M$ 的原子图, 这里 $Sub_{(\overset{a_{0}}{˙}, ..., \overset{a_{n - 1}}{˙})}^{(x_{m_{0}}, ..., x_{m_{n - 1}})}$ 是 $Sub_{\overset{a_{0}}{˙}}^{x_{m_{0}}} ... Sub_{\overset{a_{n - 1}}{˙}}^{x_{m_{n - 1}}}$ 的缩写.

2.

$elDiag (M) = {Sub_{(\overset{a_{0}}{˙}, ..., \overset{a_{n - 1}}{˙})}^{(x_{m_{0}}, ..., x_{m_{n - 1}})} φ (x_{m_{0}}, ..., x_{m_{n = 1}}) ∣ φ \in L :: Formula, L :: fVar (φ) = {x_{m_{0}}, ..., x_{m_{n - 1}}}, (a_{0}, ..., a_{n - 1}) \in M^{(n)}, M ⊨ φ [a_{0}, ..., a_{n - 1}]}$ , 它称作 $M$ 的初等图.

对

L_{M}

的结构

N

, 我们可以通过遗忘所有

\dot{(} a)^{M}

来得到一个

L

结构. 我们将因而不区分作为

L

或是作为

L_{M}

结构的

N

. 现在, 我们再给出嵌入与初等嵌入的另一种等价定义.

定理 2.3.0.20. 给定 $L$ 结构 $M$ 与 $L_{M}$ 结构 $N$ , 这里 $M = M :: M$ .

1.	如果 $N$ 是 $Diag (M)$ 的模型, 则 $M < N$ .
2.	如果 $N$ 是 $elDiag (M)$ 的模型, 则 $M ≺ N$ .

证明.

$□$

下行 Lowenheim-Skolem 定理

结构的扩张

首先, 我们来定义一种比先前的要求稍稍宽泛的结构.

定义 2.3.0.21. 对于某个语言 $L$ , 我们称满足以下条件的 $M = {M, F, P, -^{M}, \approx^{M}}$ 为这个语言的一个预结构:

1.	$M$ 是集合, $F \subseteq {f : M^{(n)} \to M ∣ n \in ω}$ , $P \subseteq ⋃_{n \in ω} M^{(n)}$ , $\approx^{M}$ 是一个 $M$ 上的等价关系.
2.	$-^{M} : L :: F \cup L :: P \to M :: F \cup M :: P$ 是双射.
3.	对函数符号 $f \in L :: F$ , $dom f^{M} = M^{L :: a_{F} (f)}$ .
4.	对谓词符号 $P \in L :: P$ , $P^{M} \subseteq M^{L :: a_{P} (P)}$ .
5.	如果 $a_{0} \approx^{M} b_{0}, ..., a_{n - 1} \approx^{M} b_{n - 1}$ , 则 $f^{M} (a_{0}, ..., a_{n - 1}) = f^{M} (b_{0}, ..., b_{n - 1})$ , $(a_{0}, ..., a_{n - 1}) \in P^{M}$ 当且仅当 $(b_{0}, ..., b_{n - 1}) \in P^{M}$ .

$M / \approx^{M}$ 称作这个预结构诱导的结构.

构造模型的很多时候我们总是先得到一个预结构, 然后才得到它诱导的结构. 它可以视为收缩一个结构的最简单的方法. 我们现在要考虑的问题是如何在语言扩张时同步地把结构也扩张出来.

名字空间

视图

2.3. 一阶逻辑的语义

结构

结构之间的态射

下行 Lowenheim-Skolem 定理

结构的扩张