Exercise 1

用反证法。
假设 $\Phi$ 在符号集 $S$ 上不一致，则存在有限子集 $\Psi \subseteq \Phi$ 和公式 $\psi$，使得

由于 $\Psi$ 有限，每个公式只含有限个符号，且 $S = \bigcup_{n \in \mathbb{N}} S_n$ 且 $S_n$ 递增，故存在某个 $n \in \mathbb{N}$ 使得所有出现在 $\Psi$ 中的符号均属于 $S_n$。同时，因为 $\Phi = \bigcup_{n \in \mathbb{N}} \Phi_n$ 且 $\Phi_n$ 递增，存在足够大的 $n$使得 $\Psi \subseteq \Phi_n$。于是推导可限制在 $S_n$ 中，从而

这意味着 $\Phi_n$ 不一致，矛盾。
因此 $\Phi$ 一致，即 $\text{Con}_S(\Phi)$ 成立。

Exercise 2

(a):

由于 $\Phi$ 不一致，所以对任意 $t,s$ ，均有：

故所有项都属于同一个等价类。
即 $\mathfrak{T}^{\Phi}$ 是一个单点集。

(b):

并非啊。
只要 $\Phi$ 不一致那 $\mathfrak{T}^{\Phi}$ 就是一个单点集，和具体的 $\Phi$ 无关。

Exercise 3

(a):

构造一个 $S$-结构 $\mathcal{M} = (M, R^{\mathcal{M}})$ 如下：

• 令 $M = \{0, 1\}$。
• 定义 $R^{\mathcal{M}} = \{0\}$。

再定义赋值 $s : \text{Var} \to M$ 为：对每个变量 $y$，令 $s(y)=1$。

1. $\exists x , Rx$：取 $x$ 为变量，由于 $0 \in R^{\mathcal{M}}$，所以 $\mathcal{M} \models Rx[s[x/0]]$，因此 $\mathcal{M} \models \exists x \, Rx[s]$。
2. $\neg Ry$：对任意变量 $y$，$s(y) = 1 \notin R^{\mathcal{M}}$，故 $\mathcal{M} \models \neg Ry[s]$。

因此 $(\mathcal{M}, s)$ 满足 $\Phi$ 中所有公式，故 $\Phi$ 一致。$\square$

Exercise 4

(a) ⇒ (b)

将 (a) 中的 $\varphi$ 特取为矛盾式 $\bot$，得到

取逆否命题：

其中，$\Phi \not\vdash \bot$ 即 $\operatorname{Con}(\Phi)$；而 $\Phi \not\models \bot$ 表示并非所有满足 $\Phi$ 的模型都满足 $\bot$，由于 $\bot$ 恒假，这等价于存在某个模型满足 $\Phi$，即 $\Phi$ 可满足。
所以有：

这正是 (b)。因此 (a) ⇒ (b)。

(b) ⇒ (a)

假设 (b) 成立，即对任意公式集 $\Psi$，若 $\Psi$ 一致则 $\Psi$ 可满足。
现给定 $\Phi$ 和 $\varphi$，且 $\Phi \models \varphi$。要证 $\Phi \vdash \varphi$。
考虑逆否命题：若 $\Phi \not\vdash \varphi$，则 $\Phi \not\models \varphi$。

首先，有

记 $\Psi = \Phi \cup \{\neg\varphi\}$。若 $\Phi \not\vdash \varphi$，则 $\Psi$ 一致。
由 (b)，$\Psi$ 一致 ⇒ $\Psi$ 可满足，即存在模型 $\mathfrak{M}$ 使得 $\mathfrak{M} \models \Phi$ 且 $\mathfrak{M} \models \neg\varphi$，这意味着 $\mathfrak{M} \not\models \varphi$，故 $\Phi \not\models \varphi$。
于是我们得到：

取逆否命题即得 $\Phi \models \varphi \;\Longrightarrow\; \Phi \vdash \varphi$，也就是 (a)。
因此 (b) ⇒ (a)。