Exercise 1
设$\varphi = \exists x_1...\exists x_k\psi$，$\psi$是无量词公式，且$\mathfrak{A} \in \mathfrak{B}，\mathfrak{A} \models \varphi$
由 $\mathfrak{A} \models \varphi$ 知：存在$a_1, a_2, ..., a_k \in A$，使得$$\mathfrak{A} \models \psi(a_1,\dots, a_k)$$
我们断言：对任意无量词公式$\chi(x_1, \dots, x_m)$及任意$b_1, \dots,b_m \in A$，有
下面给出证明：
(a) 对$b_{i}$的结构做归纳证明：
- $t = c$。故有 $c^{\mathfrak{A}}=c^{A}=c^{B}=c^{\mathfrak{B}}$
- t=$fx_{1}\dots x_{m}$。故有$$
f^{\mathfrak{A}}(x_{1},\dots,x_{m})=f^{A}(x_{1},\dots,x_{m})=f^{B}(x_{1},\dots,x_{m})=f^{\mathfrak{B}}(x_{1},\dots,x_{m})$$
(b) 对$\chi$的结构做归纳证明：
- $\chi=b_{i} \equiv b_{j}$。其中$b_{i},b_{j}$是项$$\mathfrak{A} \models b_{i}\equiv b_{{j}} \Leftrightarrow b_{i}^{\mathfrak{A}}=b_{j}^{\mathfrak{A}} \Leftrightarrow b_{i}^{\mathfrak{B}}=b_{j}^{\mathfrak{B}} \Leftrightarrow \mathfrak{B} \models b_{i} \equiv b_{j} $$
- $\chi = Rb_{1}\dots b_{m}$。$$\mathfrak{A}\models Rb_{1}\dots b_{m} \iff(b_1,...,b_m) \in R^{\mathfrak{A}}\Leftrightarrow (b_{1},\dots b_{m}) \in R^{\mathfrak{B}}\Leftrightarrow \mathfrak{B}\models Rb_{1}\dots b_{m}$$
- $\chi=\neg\psi$。$$\mathfrak{A} \models \neg\psi \Leftrightarrow \mathfrak{A} \not\models \psi \Leftrightarrow \mathfrak{B} \not\models \psi \Leftrightarrow \mathfrak{B} \models \neg\psi$$
- 若 $\chi = \chi_1 \land \chi_2$，则
\mathfrak{B} \models \exists x_1 \dots \exists x_k \, \psi(x_1, \dots, x_k) = \varphi.
$$ 因此 $\mathfrak{B} \models \varphi$ ## Exercise 2 设 $P$ 为二元关系符号，$f$ 为二元函数符号。记 $x := v_0,\ y := v_1,\ u := v_2,\ v := v_3,\ w := v_4$。对下列各小题，验证替换等式成立。 --- ### (a) $$\exists x \exists y (Px u \land Py v) \frac{u, u, u}{x, y, v} = \exists x \exists y (Px u \land Py u).
$$ **验证**：原公式中自由变量为 $u, v$，约束变量为 $x, y$。替换 $\frac{u, u, u}{x, y, v}$ 表示将自由变量 $v$ 替换为 $u$，而 $x, y$ 不是自由变量，故替换无效。因此左边变为 $\exists x \exists y (Px u \land Py u)$，与右边一致。 --- ### (b) $$\exists x \exists y (Px u \land Py v) \frac{v, fuv}{u, v} = \exists x \exists y (Px v \land Py fuv).
$$ **验证**：原公式中自由变量为 $u, v$。同时将 $u$ 替换为 $v$，$v$ 替换为 $fuv$，得到： $$\exists x \exists y (Px v \land Py fuv),
$$ 即为右边。 --- ### (c) $$\exists x \exists y (Px u \land Py v) \frac{u, x, fuv}{x, u, v} = \exists w \exists y (Pwx \land Py fuv).
$$ **验证**：原公式为 $\exists x \exists y (Px u \land Py v)$。替换 $\frac{u, x, fuv}{x, u, v}$ 表示同时将 $x$ 替换为 $u$，$u$ 替换为 $x$，$v$ 替换为 $fuv$。由于 $x$ 是约束变量，需先重命名以避免捕获。将约束变量 $x$ 重命名为 $w$（新变量），得： $$\exists w \exists y (Pw u \land Py v).
$$ 然后应用替换：$u$ 变为 $x$，$v$ 变为 $fuv$，且 $w$ 不变，得到： $$\exists w \exists y (Pw x \land Py fuv),
$$ 即为右边。 --- ### (d) $$\bigl[ \forall x \exists y (Px y \land Px u) \lor \exists u fuv \equiv x \bigr] \frac{x, fxy}{x, u} = \forall v \exists w (Pvw \land Pv fxy) \lor \exists u fuv \equiv x.
$$ **验证**：原公式为 $\varphi_1 \lor \varphi_2$，其中 $$\varphi_1 = \forall x \exists y (Pxy \land Px u), \qquad \varphi_2 = \exists u fuv \equiv x.
$$ 替换 $\frac{x, fxy}{x, u}$ 表示将自由变量 $x$ 替换为 $x$（不变），自由变量 $u$ 替换为 $fxy$。 - 对 $\varphi_1$：约束变量为 $x, y$，替换项 $fxy$ 中含有自由变量 $x, y$。为避免捕获，先将约束变量重命名：$x$ 改为 $v$，$y$ 改为 $w$（新变量），得： $$\forall v \exists w (Pvw \land Pv u).
$$ 再将 $u$ 替换为 $fxy$，得到： $$\forall v \exists w (Pvw \land Pv fxy).
$$ - 对 $\varphi_2$：自由变量为 $x, v$，约束变量为 $u$。替换只影响自由变量，而 $u$ 是约束的，故 $\varphi_2$ 不变： $$\exists u fuv \equiv x.
$$ 因此左边替换后为： $$\forall v \exists w (Pvw \land Pv fxy) \lor \exists u fuv \equiv x,
$$ 与右边一致。 ## Exercise 3 设 $\mathfrak{A}$ 是任意 $S$-结构，且 $\mathfrak{A} \models \forall x_0 \dots \forall x_r (x_0 \equiv t_0 \land \cdots \land x_r \equiv t_r \to \varphi)$。任取赋值 $s: V \to A$，需证 $\mathfrak{A} \models \varphi\frac{t_0\dots t_r}{x_0\dots x_r}[s]$。 考虑赋值 $s'$，其定义为： $$s'(x_i) = t_i^{\mathfrak{A}}[s] \quad (i=0,\dots,r), \qquad s'(y) = s(y) \ \text{对其他变元 } y.
$$ 由于 $x_i \notin \operatorname{var}(t_j)$，$t_i^{\mathfrak{A}}[s]$ 的计算不依赖于 $s$ 在 $x_j$ 上的值，因此该定义是良定的。 由假设，$\mathfrak{A}$ 满足前提公式，特别地，对赋值 $s'$ 有： $$\mathfrak{A} \models (x_0 \equiv t_0 \land \cdots \land x_r \equiv t_r \to \varphi)[s'].
$$ 而根据 $s'$ 的定义，$s'(x_i) = t_i^{\mathfrak{A}}[s']$（因为 $t_i$ 中不含 $x_j$，所以 $t_i^{\mathfrak{A}}[s'] = t_i^{\mathfrak{A}}[s]$），因此 $\mathfrak{A} \models (x_i \equiv t_i)[s']$ 对所有 $i$ 成立。于是蕴涵式的前件为真，故后件亦真，即 $\mathfrak{A} \models \varphi[s']$。 现在应用替换引理：由于 $x_i \notin \operatorname{var}(t_j)$ 保证了替换时不会发生变量捕获，我们有 $$\mathfrak{A} \models \varphi\frac{t_0\dots t_r}{x_0\dots x_r}[s] \iff \mathfrak{A} \models \varphi[s'],
$$ 其中 $s'$ 正是如上定义的赋值（即 $s' = s[x_0 \mapsto t_0^{\mathfrak{A}}[s], \dots, x_r \mapsto t_r^{\mathfrak{A}}[s]]$）。因此 $\mathfrak{A} \models \varphi\frac{t_0\dots t_r}{x_0\dots x_r}[s]$。 由 $s$ 的任意性，得 $\mathfrak{A} \models \varphi\frac{t_0\dots t_r}{x_0\dots x_r}$。从而前提蕴含结论。