\[ \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \]
教材 2.2 真值与模型
习题 13：证明同态定理的 (a)。
设 \(h\) 是从 \(\A\) 到 \(\B\) 中的同态，\(s\) 将变量的集合映射到 \(|\A|\) 中。
- 对每个项 \(t\)，我们有 \(h(\overline{s}(t)) = \overline{h \circ s}(t)\)，其中 \(\overline{s}(t)\) 是在 \(\A\) 中计算的，而 \(\overline{h \circ s}(t)\) 是在 \(\B\) 中计算的；
影印版教材中同态定理的横线印刷不清晰，本题中的表述是正确的。
证明：对于常量 \(c\)，\(h(\overline{s}(c)) = h(c^\A) = c^\B = \overline{h \circ s}(c)\)；
对于变量 \(x\)，\(h(\overline{s}(t)) = h(s(x)) = h \circ s(x) = \overline{h \circ s}(x)\)；
对于 \(n\) 元函数函数 \(f\)，按照归纳，
\[ h(\overline{s}(f t_1 \dots t_n)) = h(f^\A(\overline s(t_1), \dots, \overline s(t_n))) \\ = f^\B(h(\overline{s}(t_1)), \dots, h(\overline{s}(t_n))) \\ = f^\B(\overline{h \circ s}(t_1), \dots, \overline{h \circ s}(t_n)) \\ = \overline{h \circ s}(ft_1 \dots t_n) \]
\(Q.E.D.\)
习题 18：全称公式 (\(\forall_1\)) 是形式为 \(\forall x_1 \cdots x_n \theta\) 的公式，存在公式 (\(\exists_1\)) 是形式为 $ x_1 x_n $ 的公式，其中 $ $ 是无量词。设 $ $ 是 \(\B\) 的子结构，$ s: V || $。
- 证明：如果 $$ 且 $ $ 是存在公式，那么 $$。如果 $$ 且 $ $ 是全称公式，那么 $$。
说明：(a) 的意思是（当 $ $ 是句子时）任何全称句子 $ $ 在子结构中都可以保持。由于全称是语法性质，其必定与符号串相关。反过来，在子结构中保持则是语义性质，其必定与结构相关。但是这一语义性质保持了逻辑等价的语法性质（这正是我们所需要的）。即，如果句子 $ $ 在子结构中总是成立，那么 $ $ 逻辑等价于全称句子（这一点要归功于洛斯和塔斯基）。
证明：我们假设 $_x_1 x_n $，于是对于每个 \(d_1, \dots, d_n \in |\B|\)，\(\vDash_\B \theta[s(x_i|d_i)_{i=1}^n]\)。
这意味着，对于每个 \(d_1, \dots, d_n \in |\A|\)，\(\vDash_\B \theta[s(x_i|d_i)_{i=1}^n]\)。因此，对每个 \(d_1, \dots, d_n \in |\A|\)，\(\vDash_\A \theta[s(x_i|d_i)_{i=1}^n]\)。等价地，\(\vDash_\A \forall x_1 \dots \forall x_n \theta [s]\)。
用同样的证明方法，我们假设 \(\vDash_\A \exists x_1 \dots \exists x_n \theta [s]\)，则存在 \(d_1, \dots, d_n \in |\A|\)，\(\vDash_\A \theta[s(x_i|d_i)_{i=1}^n]\)。进而存在 \(d_1, \dots, d_n \in |\B|\)，\(\vDash_\B \theta[s(x_i|d_i)_{i=1}^n]\)。可推出 \(\vDash_\B \exists x_1 \dots \exists x_n \theta [s]\)。
\(Q.E.D.\)
习题 20：设语言有等号和二元谓词符号 \(P\)。考虑两个结构 \((\mathbb{N}, <), (\mathbb{R}, <)\)。试找出一个句子，它在一个结构中是真的，在另外一个中是假的。
直观来说，\((\mathbb{N}, <)\) 中存在“相邻”的两个数而 \((\mathbb{R},<)\) 中不存在。“相邻”可以被形式化描述为“这两个数之间没有其他的数”。我们使用公式来表达这一性质：
\[ \forall x \exists y \forall z \lnot(x < z \land z < y) \]
习题 22：设 \(\A\) 是结构且 \(h\) 是函数，\(\mathrm{ran} h = |\A|\)。证明存在结构 \(\B\) 使得 \(h\) 是一个从 \(\B\) 到 \(\A\) 上的同态。提示：取 \(|\B| = \mathrm{dom} h\)。一般地，需要使用选择公理在 \(\B\) 中定义函数，除非 \(h\) 是一对一的。
证明：取 \(|\B| = \mathrm{ran} h\)，则 \(h:|\B| \to |\A|\) 是满射。对每个 \(a \in \A\)，使用选择公理定义 \(G(a) = \set{b \in |\B| | h(b) = a}\)，定义 \(g(a)\) 为 \(G(a)\) 中的任意一个元素（例如，某个全序下的最小元素）。接下来，我们可以根据对同态的定义构造 \(\B\) 中的谓词参数、常数符号函数符号对应的元素：
\[ \langle b_1, \dots, b_n\rangle \in P^\B \iff \langle h(b_1), \dots, h(b_n)\rangle \in P^\A \\ c^\B = g(c^\A) \\ f^\B(b_1, \dots, b_n) = g(f^\A(h(b_1), \dots, h(b_n))) \]
以上定义的 \(\B\) 显然使得 \(h\) 为同态。
\(Q.E.D.\)
教材 2.3 解析算法
习题 1：对于合式公式 \(\alpha\) 的任意真的初始段 \(\alpha'\)，\(K(\alpha) < 1\)。
证明：对波兰记法下的 \(\alpha\) 使用归纳法。
- 若 \(\alpha = (\lnot \beta)\)，有以下几种情况：
- \(\alpha' = (\)，\(K(\alpha') = -1\)
- \(\alpha' = (\lnot\)，\(K(\alpha') = 0\)
- \(\alpha' = (\lnot \beta'\)，\(K(\alpha') \le -1\)
- \(\alpha' = (\lnot \beta\)，\(K(\alpha') = -1\)
- 若 \(\alpha = (\beta \land \gamma)\)，有以下几种情况：
- \(\alpha' = (\)，\(K(\alpha') = -1\)
- \(\alpha' = (\beta'\)，\(K(\alpha') \le -1\)
- \(\alpha' = (\beta\)，\(K(\alpha') = 0\)
- \(\alpha' = (\beta \land\)，\(K(\alpha') = -1\)
- \(\alpha' = (\beta \land \gamma'\)，\(K(\alpha') \le -1\)
- \(\alpha' = (\beta \land \gamma\)，\(K(\alpha') \le 0\)
因此，总有 \(K(\alpha') \le 0\)。
\(Q.E.D.\)
习题 2：设 \(\varepsilon\) 是包含变量、常数符号和函数符号的表达式。证明：\(\varepsilon\) 是项当且仅当 \(K(\varepsilon) = 1\) 且对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)，我们有 \(K(\varepsilon') > 0\)。提示：证明更强一些的结果：如果对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)，\(K(\varepsilon') > 0\)，那么 \(\varepsilon\) 是 \(K(\varepsilon)\) 个项的连接。
证明：先证充分性。由引理 23A，\(K(\varepsilon) = 1\)。由引理 23B，对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)，我们有 \(K(\varepsilon') > 0\)。
再证必要性。
对 \(\varepsilon\) 归纳。若 \(\varepsilon\) 长度为 1，则为变量或常数符号，命题显然成立。
若 \(\varepsilon\) 长度超过 1，由 \(K(\varepsilon) = 1\) 且对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)，\(K(\varepsilon') > 0\)，可知必然存在至少一个 \(n\) 元函数符号 \(f\)。
若只存在一个 \(n\) 元函数符号 \(f\)，则由 \(K(\varepsilon) = 1\) 知 \(\varepsilon\) 中必然存在 \(n\) 个变量或常数符号，由 \(K(\varepsilon') \ge 1\) 知这些变量符号必然都出现在 \(\varepsilon\) 右端。命题成立。
对 \(\varepsilon\) 中函数符号的个数归纳，由 \(K(\varepsilon) = 1\) 且对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)，\(K(\varepsilon') > 0\)，可知 \(\varepsilon\) 必然以 \(n\) 元函数符号开始，且函数符号后恰好有 \(n\) 项。
\(Q.E.D.\)
