Exercise 1
定义映射 $h: T^{\Phi} \to A$ 为 $h([t]) = t^{\mathcal{T}}$，其中 $t^{\mathcal{T}}$ 是项 $t$ 在解释 $\mathcal{T}=(\mathfrak{A},\beta)$ 下的值。
- 良定性：若 $[t_1] = [t_2]$，则 $\Phi\vdash t_1\approx t_2$。而 $\mathcal{T}\models\Phi$，故 $\mathcal{T}\models t_1\approx t_2$，因此 $t_1^{\mathcal{T}} = t_2^{\mathcal{T}}$。
- 关系符号 $R$：若 $([t_1],\dots,[t_n])\in R^{\mathfrak{T}^{\Phi}}$，则 $\Phi\vdash R(t_1,\dots,t_n)$。从而 $\mathcal{T}\models R(t_1,\dots,t_n)$，即 $(t_1^{\mathcal{T}},\dots,t_n^{\mathcal{T}})\in R^{\mathfrak{A}}$，所以 $(h([t_1]),\dots,h([t_n]))\in R^{\mathfrak{A}}$。
- 函数符号 $f$：
- 常元 $c$：$h(c^{\mathfrak{T}^{\Phi}}) = h([c]) = c^{\mathcal{T}} = c^{\mathfrak{A}}$。
所以 $h$ 是一个同态。
Exercise 2
因为 $\Phi\vdash\varphi$，有 $\Phi\models\varphi$。现在只要说明在更小的语言 $L^{S_0}$ 里仍然有 $\Phi\models\varphi$，然后 $L^{S_0}$ 里的完备性自然给一个只含 $S_0$-公式的证明。
任取一个 $S_0$-结构 $\mathfrak{B}_0$ 满足 $\Phi$。把它随便扩充成 $S$-结构 $\mathfrak{B}$：对每个不在 $S_0$ 里的常元，取论域 of 里某个固定元素当解释；对不在 $S_0$ 里的函数符号，都解释成常函数；对多余的关系符号，全都解释成空集。这样扩充出来的 $\mathfrak{B}$ 跟 $\mathfrak{B}_0$ 在 $S_0$ 符号上完全一样，而 $\Phi$ 里根本没有多余符号，所以 $\mathfrak{B}\models\Phi$。由 $\Phi\models\varphi$ 得 $\mathfrak{B}\models\varphi$，又因为 $\varphi$ 也是只含 $S_0$ 的符号，它的真值只看 $S_0$ 的解释，于是 $\mathfrak{B}_0\models\varphi$。
这样就在 $L^{S_0}$ 里证明了 $\Phi\models\varphi$，根据完备性定理，存在 $L^{S_0}$ 中的证明。这个证明当然只用到 $S_0$ 的符号，而且它在原语言 $L^S$ 里也是合法的证明序列。
Exercise 3.
$\Phi$ 是至多可数的一集公式，而且知道它在一个无穷域上有模型。要找一个可数域上的模型。
先把语言扩充，加入可数个新的常元 $c_1, c_2, \dots$。考虑公式集
$$ \Phi' = \Phi \cup \{\, \exists x_1\dots\exists x_n\bigwedge_{i现在对一致的公式集 $\Phi'$ 做 Henkin 构造 ：先把语言继续扩张加入更多见证常元，把它扩充成一个包含 $\Phi'$ 并且满足见证性质的极大一致集 $\Phi^$。语言总共是可数的，所以 $\Phi^$ 的项模型 $\mathfrak{T}$ 的论域由新常元和原来语言的项生成的等价类组成，必然是可数的。
因为 $\Phi^$ 包含了所有“至少 $n$ 个元素”的句子，$\mathfrak{T}$ 是无限模型。于是 $\mathfrak{T}$ 就是可数无限的，并且 $\mathfrak{T}\models\Phi^$，所以也满足 $\Phi$。这就得到了可数域上的模型。
Exercise 4
$S=\emptyset$，结构就是带等词的纯集合。
(i) 对每个 $n\in\mathbb{N}$，令 $\psi_n$ 是“恰好存在 $n$ 个元素”的句子：
$$ \exists x_1\dots\exists x_n\Big(\bigwedge_{i对任意有限结构 $\mathfrak{A}$：
- 若 $|A|$ 是偶数，则 $|A|$ 不等于任何奇数，于是对每个奇数 $n$ 都有 $\mathfrak{A}\models\neg\psi_n$，故 $\mathfrak{A}\models\Phi$。
- 若 $|A|$ 是奇数，设 $|A| = m$（$m$ 为奇数），则 $\mathfrak{A}\models\psi_m$，从而 $\mathfrak{A}\not\models\neg\psi_m$，因此 $\mathfrak{A}\not\models\Phi$。
因此对有限结构满足要求。
(ii) 假设存在句子集 $\Psi$ 使对所有结构 $\mathfrak{A}$ 都有 $\mathfrak{A}\models\Psi \iff |A|$ 是偶数。考虑
$$ \Gamma = \Psi \cup \{\,\exists x_1\dots\exists x_k\bigwedge_{iExercise 5
设 $\mathfrak{A}$ 是有限 $S$-结构，论域 $A=\{a_1,\dots,a_n\}$。构造句子 $\Phi$ 如下：
$$ \begin{aligned} \Phi := \exists x_1\dots\exists x_n\Big( &\bigwedge_{1\le i如果 $\mathfrak{B}\models\Phi$，则存在 $b_1,\dots,b_n\in B$ 两两不同且穷尽了 $B$。关系、函数和常元的限制条件恰好使它们的解释与 $\mathfrak{A}$ 在同构 $a_i\mapsto b_i$ 下完全一致，因此这个映射给出 $\mathfrak{A}\cong\mathfrak{B}$。
反过来，如果 $\mathfrak{B}\cong\mathfrak{A}$，那么在同构下取 $a_i$ 的像作为 $b_i$ 就会满足存在量词和所有合取支，所以 $\mathfrak{B}\models\Phi$。
于是 $\mathfrak{B}\models\Phi$ 当且仅当 $\mathfrak{B}\cong\mathfrak{A}$。