\[ \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 || $。
- 证明:如果 \(\vDash_\A \psi[s]\) 且 \(\psi\) 是存在公式,那么 \(\vDash_\B \psi[s]\)。如果 \(\vDash_\B \varphi[s]\) 且 \(\varphi\) 是全称公式,那么 \(\vDash_\A \varphi[s]\)。
说明:(a) 的意思是(当 \(\varphi\) 是句子时)任何全称句子 \(\varphi\) 在子结构中都可以保持。由于全称是语法性质,其必定与符号串相关。反过来,在子结构中保持则是语义性质,其必定与结构相关。但是这一语义性质保持了逻辑等价的语法性质(这正是我们所需要的)。即,如果句子 \(\sigma\) 在子结构中总是成立,那么 \(\sigma\) 逻辑等价于全称句子(这一点要归功于洛斯和塔斯基)。
证明:我们假设 $_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.\)