数理逻辑-期末考点合集

摘要

本文是 2024Fall-数理逻辑的期末考点合集，包括讲义和教材中的知识点、习题和简答题。其中添加了一些笔者对知识的理解，这部分注明不是来自讲义或教材，仅供参考。

讲义 $\S 0.2$ 集合

关于 ZFC 集合论及其构造思路，可参考本人博客：公理的祖先是逻辑或形式二者之一 | EagleBear2002 的博客。

讲义 $\S 0.2.15$ 良序关系

良序：设 $(A, \le)$ 为全序集，如果任意 $A$ 的非空子集都有 $\le$-极小元，则称 $(A, \le)$ 为良序集。

讲义 $\S 0.2.17$ 自然数的定义

设 $A$ 为任意的集合，我们称 $A^+ = A \cup \set{A}$ 为 $A$ 的后继，$A$ 为 $A^+$ 的前趋。

自然数的定义：$0 = \emptyset, 1 = 0^+$。

无穷公理：所有自然数组成的整体是集合，记为 $\omega$。

讲义 $\S 0.2.18$ 数学归纳法

传递集合：设 $A$ 是一个集合，如果 $A$ 的任意元素都是 $A$ 的子集，则称 $A$ 是传递集合。

三歧性：$\forall x, y \in A. x \in y \lor x = y \lor y \in x$。

对任意自然数 $n, m$ 定义：$m < n$ 当且仅当 $m \in n$，$m \le n$ 当且仅当 $m < n$ 或 $m = n$。（这一定义在本书的习题中已经被滥用，不仅限于自然数，在序数上都可以使用）

习题 1：证明设 $A$ 为传递集合，则 $A^+$ 也是传递集合。

证明：由 $A$ 的传递性可知，$\forall a \in A, a \subseteq A$。取任意 $b \in A^+$，只要证明 $b \subseteq A^+$。

$A^+$ 是 $A$ 的后继（此处右上角的 $+$ 并不是传递闭包），即 $A^+ = A \cup \set{A}$。

若 $b \in A$ 则 $b \subseteq A \subseteq A^+$；

若 $b \notin A$ 则 $b = A$，此时 $b \subseteq A^+$ 成立。

$Q.E.D.$

习题 2：证明对任意自然数 $n$，都有 $0 = n$ 或 $0 \in n$。

证明：对 $n$ 使用数学归纳法。

若 $n = 0$，显然命题 $0 = n$ 成立；

若 $n = 1$，即 $n = \set{\emptyset, \set{\emptyset}}$，显然命题 $0 \in n$ 成立；

若 $n = k(k > 1)$ 时命题 $0 \in n$ 成立，则 $n = k + 1$ 时，$n = k \cup \set{k}$，显然命题 $0 \in n$ 成立。

因此，对任意自然数 $n$，都有 $0 = n$ 或 $0 \in n$。

$Q.E.D.$

讲义 $\S 0.2.19$ 有穷集合和无穷集合

\[ \def\ran{\text{ran}} \]

习题 1: 证明 $\omega^{++}$ 与 $\omega$ 等势。

证明：构造 $f: \omega \mapsto \omega^{++}$，其中 $f(0) = \omega, f(1) = \omega^{+}, f(n) = n - 2(n \ge 2)$。显然 $f$ 是双射，因此 $\omega^{++}$ 与 $\omega$ 等势。

$Q.E.D.$

习题 2：假设 $A, B, A_1, B_1$ 为满足如下条件的集合：

$A \cap A_1 = \emptyset, B \cap B_1 = \emptyset$；
$A \sim B, A_1 \sim B_1$；

证明：$A \cup A_1 \sim B \cup B_1$。

证明：由题意得，$\exists f: A \to B, g: A_1 \to B_1$，$f,g$ 为双射。

构造 $h: A \cup A_1 \to B \cup B_1$：

\[ h(x) = \left\{\begin{matrix} f(x) & \text{if } x \in A \\ g(x) & \text{if } x \in A_1\\ \end{matrix}\right. \]

显然，$h$ 为双射。因此 $A \cup A_1 \sim B \cup B_1$。

$Q.E.D.$

习题 3：设 $A, B$ 为两个集合，证明：

$A \preceq B$ 当且仅当 $A$ 与 $B$ 的某个子集等势。

证明：先证充分性。若 $A \preceq B$，则 $\exists f : A \to B$ 是一个单射。令 $C = \ran(f) \subseteq B$，则 $f: A \to C$ 是双射，因此 $A \sim C$。

再证必要性。若 $\exists D \subseteq B. A \sim D$，则 $\exists g: A \to D$ 为双射。因此 $g: A \to B$ 是单射，故 $A \preceq B$。

$Q.E.D.$

讲义 $\S 0.2.21$ 有穷集合

习题：设 $A, B$ 为两个集合，试证明：

（1）如果 $A$ 有穷，$B \preceq A$，则 $B$ 也是有穷集合。

证明：$A$ 是有穷集合

$\Rightarrow \exists n \in \omega. A \preceq n$

$\Rightarrow B \preceq n$

$\Rightarrow B$ 是有穷集合。

$Q.E.D.$

讲义 $\S 0.2.22$ 可数集合

习题 1：设 $A, B$ 为两个可数集合，且 $A, B$ 不相交，即 $A \cap B = \emptyset$。证明：$A \cup B$ 也是可数的。

证明：$A, B$ 可数意味着 $\exists f: \omega \to A, g: \omega \to B$，$f, g$ 为满射。构造

\[ h(n) = \left\{\begin{matrix} f(\frac{n}{2}) & \text{if } n \text{ 为偶数} \\ g(\frac{n-1}{2}) & \text{if } n \text{ 为奇数} \\ \end{matrix}\right. \]

显然 $h: \omega \to A \cup B$ 为满射。因此 $A \cup B$ 可数。

$Q.E.D.$

习题 2：证明：

对任意 $k \in \omega$ 有，$\omega^k$ 都是可数集合（约定 $\omega^0 = \set{\emptyset}, \omega^1 = \omega$）；
集合 $\bigcup \set{\omega^k | k \in \omega}$ 是可数的。

TODO：这道题用到了构造 $A \times B \mapsto \omega$ 的函数，需要记住。

证明：引理：两个可数集合的笛卡尔积是可数集合。对于可数集合 $A, B$，$f: A \mapsto \omega, g: B \mapsto \omega$ 为单射。构造 $h(x, y) = \frac{(f(x)+g(y))\times(f(x)+g(y)+1)}{2} + g(y)$ ，则 $h:A\times B \mapsto \omega$ 为单射。因此 $A \times B$ 可数。

下面进行归纳：

$k = 0$ 时，$\omega^0 = \set{\emptyset}$ 显然是可数集合。

$k = 1$ 时，构造 $f_1: \omega \to \omega$，$f_1(x) = x$ 为双射，可知 $\omega^1$ 为可数集合。

由 $\omega^k$ 为可数集合和引理可知，$\omega^{k+1}=\omega^k \times \omega$ 为可数集合。

因此，对任意 $k \in \omega$ 有，$\omega^k$ 都是可数集合。

$Q.E.D.$

证明：由定理 0.2.7，可数多个可数集合的并仍然是可数集合，因此 $\bigcup \set{\omega^k | k \in \omega}$ 是可数集合。

$Q.E.D.$

讲义 $\S 0.2.24$ 不可数集合（不考）

\[ \def\FUN{\mathsf{FUN}} \]

习题 1：令 $\FUN(\omega, \omega)$ 表示所有从 $\omega$ 到 $\omega$ 的映射组成的集合，即 $\FUN(\omega, \omega) = \set{f|f: \omega \to \omega 为映射}$，用对角线方法证明 $\FUN(\omega, \omega)$ 是不可数的。

证明：使用反证法。假设 $\FUN(\omega, \omega)$ 可数，不妨设 $\FUN(\omega, \omega) = \set{f_0, f_1, f_2, \dots}$。

构造新映射 $f: \omega \to \omega$，$f(n) = f_n(n) + 1$。

若 $f \notin \FUN(\omega, \omega)$，与 $\FUN(\omega, \omega)$ 的定义相矛盾；

若 $f \in \FUN(\omega, \omega)$，但 $\forall n \in \mathbb{N}. f(n) \ne f_n(n)$，矛盾。

假设不成立。原命题成立。

$Q.E.D.$

讲义 $\S 0.2.25$ 序数

具有三歧性的传递集合叫做序数。每个自然数都是序数，$\omega$ 是序数。

习题：设 $S$ 为序数集合，证明：

（1）如果 $\alpha$ 是 $S$ 的最大元，则 $\alpha = \bigcup S$；

（2）如果 $S$ 中无最大元，则对任何的 $\beta$ 属于 $S$，有 $\beta < \bigcup S$。

证明：$\alpha$ 是 $S$ 的最大元，由三歧性得，$\forall \beta \in S. \beta = \alpha \vee \beta \in \alpha$。

由 $S$ 是传递集合，$\forall \beta \in S. \beta \subseteq \alpha$，即 $S$ 中任意元素都是 $\alpha$ 的子集，因此 $\bigcup S \subseteq \alpha$。

由 $\alpha \in S$ 得，$\alpha \subseteq \bigcup S$。

因此 $\alpha= \bigcup S$。

$Q.E.D.$

证明：由传递集合得，$\forall \beta \in S. \beta \subseteq \bigcup S$。

$S$ 中没有最大元，即 $\forall \beta \in S. \exists \gamma \in S. \beta < \gamma$，因此 $\beta \ne \bigcup S$。

因此，$\beta < \bigcup S$。

$Q.E.D.$

讲义 $\S 0.2.26$ 超穷归纳法

如果 $\alpha$ 存在前趋，称 $\alpha$ 为后继序数。不是后继序数的非零序数称为极限序数。

习题：设 $\alpha, \beta$ 为序数，且 $\alpha \ne 0$。

（1）$\alpha$ 是极限序数，当且仅当 $\bigcup \alpha = \alpha$；

（2）如果 $\beta \in \alpha$，且 $\beta$ 是 $\alpha$ 的最大元，则 $\alpha = \beta^+$。

证明：

先证必要性（$\alpha$ 是极限序数 $\Rightarrow \bigcup \alpha = \alpha$）：如果 $\alpha$ 是极限序数，那么 $\forall \beta \in \alpha. \beta < \alpha$，并且 $\alpha$ 中没有最大元。

由 $\alpha$ 的传递性可知，$\alpha$ 中任意元素都是其子集，因此 $\bigcup \alpha \subseteq \alpha$。

$\forall \beta \in \alpha. \forall x \in \beta. x \in \bigcup \alpha$ 因此 $\beta \subseteq \bigcup \alpha$。又由传递性，$\beta \subseteq \alpha$，因此 $\beta \in \bigcup \alpha$。因此 $\alpha \subseteq \bigcup \alpha$。（TODO：这一步有点问题）

因此 $\bigcup \alpha = \alpha$。

再证充分性（$\bigcup \alpha = \alpha \Rightarrow \alpha$ 是极限序数）：假设 $\bigcup \alpha = \alpha$。这意味着 $\alpha$ 是由它自身的所有元素组成的，并且对于每个 $\beta \in \alpha$，都有 $\beta \subset \alpha$。

如果 $\alpha$ 不是极限序数，则 $\alpha$ 中应有一个最大元 $\gamma$，使得 $\alpha = \gamma^+$。由上一题结论，$\bigcup \alpha = \gamma$，但这与假设 $\bigcup \alpha = \alpha$ 矛盾。因此，$\alpha$ 不能有最大元。

因此，$\alpha$ 必须是极限序数。

$Q.E.D.$

证明：由 $\beta$ 是 $\alpha$ 中最大元，$\forall \gamma \in \alpha. \gamma \le \beta$，且 $\alpha$ 为后继序数（TODO：这一步怎么来的？）。设 $\alpha = \beta_0^+ = \beta_0 \cup \set {\beta_0}$，只要证明 $\beta = \beta_0$。

若 $\beta < \beta_0$，与 $\beta$ 是 $\alpha$ 中最大元矛盾；

若 $\beta_0 < \beta$，则 $\alpha = \beta_0 \le \beta$，与 $\beta \in \alpha$ 矛盾。

因此，$\beta = \beta_0$。

$Q.E.D.$

讲义 $\S 0.2.28$ 可数序数

定义 $\omega_1 = \set{\alpha \mid \alpha \text{ 是可数序数}}$。$\omega_1$ 是序数，且不可数。

定义 $\omega_{\alpha+1} = \set{\beta \mid \beta \text{ 是序数且 } \beta \preceq \omega_\alpha}$。

讲义 $\S 0.2.29$ 基数

\[ \def\card{\mathrm{card\ }} \]

设 $\alpha$ 是序数，如果对于任意的 $\beta < \alpha$ 都有 $\beta \prec \alpha$，则称 $\alpha$ 是基数。

讲义中对基数的定义十分诡异，我们在这里补充教材中对基数的定义。集合 $A$ 的基数 $\card A$ 是与 $A$ 大小相等的最小序数，基数的意义是用于比较集合的大小：

\[ \card A = \card B \iff A \sim B \]

习题 1：设 $\alpha$ 为基数，$\kappa$ 为集合 $\set{\beta | \beta 是序数且与 \alpha 等势}$ 的最小元。证明：$\kappa$ 是基数。

TODO：看不明白过程

证明：对每个序数 $\gamma < \kappa$，即 $\gamma \in \kappa$，有 $\gamma \subseteq \kappa$，即 $\gamma \prec \kappa$ 或 $\gamma \sim \kappa$。

又因为 $\kappa$ 为集合中最小元，因此 $\gamma \prec \kappa$。

$Q.E.D.$

习题 2：对任意的 $\alpha$ 都有，$\alpha \le \omega_\alpha$。

TODO

教材 $\S 1$ 命题逻辑

教材 $\S 1.1$ 命题逻辑的语言

\[ \def\len{\mathsf{len}} \]

习题 2：证明不存在长度为 2、3、6 的合式公式，但其他任意正整数长度的合式公式都可能存在。

证明：用 $\len(\alpha)$ 表示公式 $\alpha$ 的长度。定义谓词 $P$，命题 $P(\alpha): \len(\alpha) \notin \set{2, 3, 6}$。

对所有命题符号 $A_n$，$\len(A_n) = 1$，命题 $P(A_n)$ 成立。

对所有非命题符号的合式公式 $\alpha$ 归纳：

下面证明：若组成合式公式 $\alpha$ 的合式公式 $\beta, \gamma$ 均有 $P(\beta), P(\gamma)$ 成立，则 $P(\alpha)$ 成立。

若 $\alpha = (\lnot \beta)$，则 $\len(\alpha) \ge 4$，$\len(\alpha) \notin \set{2, 3}$。若 $\len(\alpha) = 6$，则 $\len(\beta) = 3$，与 $P(\beta)$ 矛盾；

若 $\alpha = (\beta \square \gamma)$（其中 $\square \in \set{\vee, \wedge, \to, \leftrightarrow}$），显然 $\len(\alpha) = \len(\beta) + \len(\gamma) + 3> 5$。若 $\len(\alpha) = 6$ 则 $\len(\beta) + \len(\gamma) = 3$，与 $P(\beta)$ 或 $P(\gamma)$ 矛盾。

因此，$\len(\alpha) \notin \set{2, 3, 6}$。

下面证明 $\len(\alpha)$ 可以为其他任何长度。

$\len$ 函数存在如下递归关系：

\[ \len(A_n) = 1 \\ \len((\lnot \alpha)) = \len(\alpha) + 3 \\ \len((\alpha \square A_n)) = \len(\alpha) + 4 \]

显然，$\len(\alpha)$ 可以为 $\set{1, 4, 5, 7, 8, 9}$ 中的任何值。根据长度为 7、8、9 的公式，可以根据 $\len((\lnot \alpha)) = \len(\alpha) + 3$ 构造长度为大于 9 的任意整数的公式。

$Q.E.D.$

习题 3：设 $\alpha$ 是一个合式公式，$c$ 是二元连接符（$\wedge, \vee, \to, \leftrightarrow$）出现的次数，$s$ 是命题符合出现的次数（例如，若 $\alpha = (A \to (\lnot A))$，则 $c = 1, s = 2$）。使用归纳法证明：$s = c + 1$。

证明：命题 $P(n): 当 c = n 时，s = c + 1$。

当 $c = 0$ 时，$\alpha = A$ 或 $\alpha = (\lnot A)$，其中 $A$ 是命题符号。$P(0)$ 成立。

若当 $c \le n (n \ge 1)$ 时都有 $P(c)$ 成立。则当 $c = n + 1$ 时，$\alpha = (\beta \square \gamma)$，其中 $c_\alpha = c_\beta + c_\gamma + 1, s_\alpha = s_\beta + s_\gamma = c_\beta + c_\gamma + 2 = c_\alpha + 1$。此时 $P(n+1)$ 成立。

因此，对任意 $c \ge 0$，都有 $P(c)$ 成立。

$Q.E.D.$

教材 $\S 1.2$ 真值指派

习题 6：(a) 证明：如果两个真值指派 $v_1, v_2$ 与在合式公式 $\alpha$ 中出现的命题符号的指派是一致的，那么 $\overline{v_1}(\alpha) = \overline{v_2}(\alpha)$。（使用归纳法则）。

证明：设 $\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle$ 是 $\alpha$ 的构造序列。

\[ \forall A \in \alpha. v_1(A) = v_2(A) \\ \Rightarrow v_1(\varepsilon_1) = v_2(\varepsilon_1) \\ \Rightarrow \forall k \le n. \overline{v_1}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_k \rangle) = \overline{v_2}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_k \rangle) \\ \Rightarrow \overline{v_1}(\alpha) = \overline{v_2}(\alpha) \]

$Q.E.D.$

习题 8：（置换）$\alpha_1, \alpha_2, \dots$ 一个合式公式的序列，对每个合式公式 $\varphi$，令 $\varphi^*$ 是用 $\alpha_n$ 置换 $A_n$（对所有 $n$）后得到的结果。

设 $v$ 是所有命题符号的真值指派，定义 $u$ 为满足 $u(A_n) = \overline{v}(\alpha_n)$ 的真值指派，证明 $\overline{u}(\varphi) = v(\varphi^*)$ 使用归纳法。
证明如果 $\varphi$ 是重言式，那么 $\varphi^*$ 也是。（例如，$((A \land B) \leftrightarrow (B \land A))$ 是一个重言式，因此对任意的合式公式 $\alpha, \beta$，通过置换可得 $((\alpha \land \beta) \leftrightarrow (\beta \land \alpha))$ 是重言式。）

证明：命题 $P(k): \varphi 构造序列长度为 k 时，\overline{u}(\varphi) = v(\varphi^*)$。设 $\varphi$ 的构造序列为 $\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_k \rangle$。对 $k$ 进行归纳：

当 $k = 1$ 时，$\varepsilon_1$ 为命题符号，命题 $P(1)$ 成立。

若当 $k < n(n > 1)$ 时，命题 $P(k)$ 都成立。

则当 $k = n$ 时，$u(\varepsilon_{n}) = v(\varepsilon_{n})$，因此 $\overline{u}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle) = \overline{v}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle)$。

因此，对所有 $k \ge 1$，命题 $P(k)$ 都成立。

$Q.E.D.$

证明：若 $\varphi$ 是重言式。对任意真值指派 $v$，$\overline{v}(\varphi^*) = \overline{u}(\varphi) = T$。因此 $\varphi^*$ 为重言式。

$Q.E.D.$

教材 $\S 1.3$ 解析算法

习题 3（不考）：证明引理 13B 中关于运算 $\varepsilon_\lnot$ 的情形。

证明：对具有该性质的合适公式的集合 $S$，使用归纳法。

只包括一个命题的合适公式，没有符合条件的真初始段，原命题显然成立。

下面验证 $S$ 在 $\varepsilon_\lnot$ 下是封闭的。考虑 $S$ 中的 $\alpha$，$(\lnot \alpha)$ 的真初始段如下：

$($

$(\lnot$

$(\lnot \alpha_0$，其中 $\alpha_0$ 是 $\alpha$ 的真初始段

$(\lnot \alpha$

显然，$\alpha_0 \in S$。原命题显然正确。

$Q.E.D.$

习题 4：假定将合式公式的定义修改为去掉其中所有的右括号。对于

\[ ((A \wedge (\lnot B)) \to (C \vee D)) \]

我们写成：

\[ ((A \wedge (\lnot B \to (C \vee D \]

证明这种记法具有唯一可读性（即每个合式公式只有一个可能的分解方法）。提示：这种表达式具有的括号数和联结符号数相同。

证明：只需给出算法，可以根据每个该记法下的公式 $e$ 和合式公式一一对应。

一种“自底向上”的构造算法：令 $S$ 表示所有合式公式（包括命题符号）的集合。

对 $e$ 中出现的每个串 $\alpha， \beta$，若 $\alpha, \beta \in S$，执行替换：

\[ ( \lnot \alpha \to (\lnot \alpha) \\ ( \alpha \wedge \beta \to ( \alpha \wedge \beta ) \\ ( \alpha \vee \beta \to ( \alpha \vee \beta ) \\ \]

重复步骤 1，直到无法执行替换。

在上述算法中，每次执行替换时在 $e$ 中增加了一个右括号 $)$，上述算法会在有限步骤内结束。替换后的子串都是合式公式，因此每个算法结束后 $e$ 成为合式公式。又因为该记法下每个公式都是由某个合式公式转化而来，因此该记法下每个公式和合式公式一一对应。

$Q.E.D.$

教材 $\S 1.4$ 归纳与递归

\[ \def\size{\mathsf{size}} \def\F{\mathcal{F}} \]

习题 1：设 $C$ 是由集合 $B=\set{a, b}$ 在二元运算 $f$ 和一元运算 $g$ 的作用下生成的。试列出 $C_2$ 中的所有元素。$C_3$ 和 $C_4$ 中各有多少元素？

$C_1 = \set{a, b}, C_2 = \set{a, b, g(a), g(b), f(a, a), f(a, b), f(b, a), f(b, b)}$

若不考虑元素相等的情况，$\size(C_{n+1}) = \size(C_n)(\size(C_n) + 2)$。

$\size(C_1) = 2, \size(C_2) = 8, \size(C_3) = 80, \size(C_4) = 6560$。

习题 3：本节中关于要求 $\F$ 仅是 $U$ 上的关系类的讨论可以进行推广。$C_*$ 如前定义，但是如果对于每个 $í \le n$，我们有 $x_i \in B$ 或者对某个 $R \in \F$ 以及某些小于 $i$ 的数 $j_1, \dots, j_k$ 有 $\langle x_{j_1}, \dots , x_{j_k}, x_i \rangle \in R$，那么我们说 $\langle x_0, , x_1 \dots , x_n \rangle$ 是一个构造序列。请给出 $C^*$ 的正确定义，并证明 $C^* = C_*$。

TODO：如何定义集合对多元关系（而非多元函数）封闭？

“自顶向下”的 $C^*$ 的扩展定义：

我们称 $U$ 的子集 $S$ 在 $R \in \F$ 的作用下是封闭的，当且仅当只要 $x_0 , x_1 \dots , x_n \in S$，那么 $\forall x_m. \langle x_0, , x_1 \dots , x_n , x_m \rangle \in R \Rightarrow x_m \in S$。称 $S$ 是归纳的，当且仅当 $B \subseteq S$ 并且 $S$ 在 $R$ 的作用下是封闭的。令 $C^*$ 是 $U$ 的所有归纳子集的交集，则 $x \in C^*$ 当且仅当 $x$ 属于 $U$ 的每个归纳子集。

证明 $C^* = C_*$：

首先验证 $C^* \subseteq C_*$。我们只需要证明 $C_*$ 是归纳的，即 $B \subseteq C_*$ 并且 $C_*$ 在 $R \in \F$ 的作用下是封闭的。显然 $B = C_1 \subseteq C_*$。如果 $x_0 , x_1 \dots , x_n \in C_*$，则将其构造序列进行连接，并添加每个新的元素 $x_m$，其中 $\langle x_0, , x_1 \dots , x_n , x_m \rangle \in R, R \in \F$，我们就得到了一个新的构造序列，并将 $x_m$ 加入了 $C_*$ 中。因此，$C_*$ 在 $R \in \F$ 的作用下是封闭的。

其次证明 $C_* \subseteq C^*$。考察构造序列 $\langle x_0, , x_1 \dots , x_n, x_m \rangle$，对 $i \le n$ 进行归纳，可得到 $x_i \in C^*$。首先 $x_0 \in B \subseteq C^*$。在归纳步骤使用 $C_*$ 的封闭特性即可。因此得到：

\[ \bigcup_n C_n = C_* = C^* = \bigcap\set{S | S 是归纳的} \]

$Q.E.D.$

教材 $\S 1.5$ 命题连接词

习题 1：设 $G$ 是三元布尔函数，定义如下：

\[ G(F, F,F)= F, G(T, F, F) =T, \\ G(F, F,T) = T, G(T, F,T) = F, \\ G(F,T, F) =T, G(T,T, F) = F, \\ G(F,T,T)=F, G(T,T,T) = F. \]

（a）给出一个仅使用 $\wedge, \vee, \lnot$ 的能够实现的合式公式；

（b）给出一个合式公式，其联结词最多出现 5 个。

（a）观察可知，当且仅当三个参数中只有一个 $T$ 时，函数值为 $T$。

构造析取范式：

\[ G(A, B, C) = (A \wedge \lnot B \wedge \lnot C) \vee (\lnot A \wedge B \wedge \lnot C) \vee (\lnot A \wedge \lnot B \wedge C) \]

（b）将上述函数简化：

\[ G(A, B, C) = (A \wedge (B \downarrow C)) \vee (\lnot A \wedge (B + C)) \\ = (A \wedge (B \downarrow C)) \vee (A < (B + C)) \]

习题 5：证明 $\set{\top, \bot, \lnot, \leftrightarrow , +}$ 是不完备的。提示：证明任意使用这些联结词和命题符号 $A, B$ 的合式公式在 $\bar{v}(\alpha)$ 的 4 种可能的取值下有偶数个取值为 $T$。说明：另一种方法是使用域 $\set{0，1}$ 上的代数，任意使用这些联结词的可实现的布尔函数具有线性的特性。

证明：由于 $\top \equiv A \vee \lnot A, \bot \equiv A \wedge \lnot A$，其中 $\equiv$ 表示重言等价（LaTeX 中没有重言等价符号）。即 $\set{\top, \bot}$ 可以用其他连结词表示，因此只需要证明 $\set{\lnot, \leftrightarrow, +}$ 是不完备的。

令 $\alpha$ 是任意只包含 $A, B$ 的公式，只要证明在 $\bar v(\alpha)$ 下的四种可能取值中有偶数个为 $T$。显然，$\leftrightarrow$ 和 $+$ 都会在 $A, B$ 的四种真值组合中产生偶数个 $T$。现在考虑使用 $\lnot, \leftrightarrow, +$ 构造的任意合式公式 $\alpha$，我们可以对其进行递归分析：

如果公式是一个单一的命题符号或由 $\leftrightarrow$ 和 $+$ 构造，则它的真值表中 $T$ 的个数一定是偶数。

如果公式是 $\lnot \alpha$，则 $\lnot$ 仅会翻转公式 $\alpha$ 的真值。因此，如果 $\alpha$ 的真值表中 $T$ 的个数是偶数，$\lnot \alpha$ 的真值表中 $T$ 的个数仍然是偶数。

因此，该联结词集合和命题符号无法构造与 $A \vee B$ 等价的公式，该连结词集合不完备。

$Q.E.D.$

教材 $\S 1.7$ 紧致性和能行性（不考）

\[ \def\v{\overline{v}} \]

习题 1：设 $\Sigma$ 的每个有限子集都是可满足的，证明 $\Sigma ; \alpha$ 和 $\Sigma ; \neg \alpha$ 中至少有一个也是如此。(这是紧致性定理证明的一部分)

提示：如果不是这样，那么对于有限子集 $\Sigma_1 \subseteq \Sigma$ 和 $\Sigma_2 \subseteq \Sigma$，$\Sigma_1 ; \alpha$ 和 $\Sigma_2 ; \neg \alpha$ 都是不可满足的。再考虑 $\Sigma_1 \cup \Sigma_2$。

不使用紧致性定理的证明：使用反证法。如果不是这样，则对于有限子集 $\Sigma_1 \subseteq \Sigma$ 和 $\Sigma_2 \subseteq \Sigma$，$\Sigma_1 ; \alpha$ 和 $\Sigma_2 ; \neg \alpha$ 都是不可满足的。因此 $\Sigma_1 \cup \Sigma_2$ 也是不可满足的。这与“$\Sigma$ 的每个有限子集都是可满足的”相矛盾。

$Q.E.D.$

习题 2：设 $\Delta$ 是满足以下条件的合式公式集合：

$\Delta$ 的每个有限子集是可满足的，
对每个合式公式 $\alpha$，要么 $\alpha \in \Delta$ 要么 $(\neg \alpha) \in \Delta$。

对每个命题符号 $A$，定义真值指派 $v$：

\[ v(A) = \begin{cases} T & \text{iff } A \in \Delta, \\ F & \text{iff } A \notin \Delta \end{cases} \]

证明对每个合式公式 $\varphi$，$\v(\varphi) = T$ 当且仅当 $\varphi \in \Delta$。（这也是紧致性定理证明的一部分）

提示：对 $\varphi$ 使用归纳法。

证明：对 $\varphi$ 使用归纳法。

若 $\varphi$ 为命题符号，则根据 $v$ 的定义，$\v(\varphi) = T$ 当且仅当 $\varphi \in \Delta$，原命题对 $\varphi$ 成立。

若对于构造序列长度小于 $n$ 的所有合式公式，原命题都成立。

则对于构造序列长度为 $n$ 的合式公式 $\varphi$，设其构造序列为 $\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle$。

若 $\varphi = (\lnot \alpha)$，$\v(\lnot \alpha) = T \iff \v(\alpha) = F \iff \alpha \notin \Delta \iff (\lnot \alpha) \in \Delta$，原命题对 $\varphi$ 显然成立；

若 $\varphi = (\alpha \wedge \beta)$，$\v(\alpha \wedge \beta) = T \iff \v(\alpha) = T \wedge \v(\beta) = T \iff \alpha \in \Delta \wedge \beta \in \Delta$。由条件 2 可知，$\Delta$ 对 $\wedge$ 封闭。因此 $\alpha \in \Delta \wedge \beta \in \Delta \iff \alpha \wedge \beta \in \Delta$。原命题对 $\varphi$ 成立。

若 $\varphi = (\alpha \vee \beta)$，可转化为 $\varphi = \lnot(\lnot \alpha \wedge \lnot \beta)$。根据 1 和 2 归纳即可。

因此，原命题对所有合式公式 $\varphi$ 成立。

$Q.E.D.$

教材 $\S 2$ 一阶逻辑

\[ \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \]

本节知识点

表达式是符号的任意有限序列。大多数表达式没有意义，项和合式公式是具有特定意义的表达式。

项定义为在常数符号和变量之前加上函数符号构成的表达式。

原子公式的做工相当于命题逻辑中的命题符号，原子公式是具有如下形式的表达式：

\[ Pt_1t_2\dots t_n \]

合式公式（或公式）是指由原子公式通过使用 0 次或多次连接符号和量词符号构成的表达式。

自由变量是“没有量词约束”的变量。

以上都是语法概念，与语义无关。

教材 $\S 2.2$ 真值与模型

习题 3：证明：$\set{\forall x(\alpha \to \beta), \forall x\alpha} \models \forall x \beta$

证明：对每个结构 $\mathfrak{A}$ 和每个函数 $s: V \to | \A |$，有 $\models_\A \forall x(\alpha \to \beta)[s]$ 和 $\models_\A \forall x \alpha[s]$，即 $\models_\A \forall x((\alpha \to \beta) \land \alpha)[s]$。因此

\[ \models_\A \forall x((\alpha \to \beta) \land \alpha)[s] \\ \iff \forall d \in \A. \models_\A((\alpha \to \beta) \land \alpha)[s(x|d)] \\ \iff \forall d \in \A. \models_\A(\beta \land \alpha)[s(x|d)] \\ \iff \models_\A \forall x(\beta \land \alpha)[s] \\ \iff \models_\A \forall x(\beta)[s] \land \models_\A \forall x(\alpha)[s] \\ \]

$Q.E.D.$

习题 4：证明：如果 $x$ 在 $\alpha$ 中不是自由出现的，那么 $\alpha \models \forall x \alpha$。

证明：对每个结构 $\mathfrak{A}$ 和每个函数 $s: V \to | \A |$，由定理 22A，有：

\[ \models_\A\forall x \alpha[s] \iff \forall d \in |\A|. \models_\A \alpha[s(x|d)] \\ \iff \models_\A \alpha[s] \\ \]

习题 9：设语言具有相等和二元谓词符号 $P$。对下面的条件中的每一个，找出一个句子 $\sigma$ 使得结构 $\A$ 是 $\sigma$ 的模型，当且仅当条件被满足。

中恰好有两个元素

下面的句子 $\sigma$ 满足要求

\[ \exists x \exists y x \neq y \land \forall x \forall y \forall z (x = y \lor y = z \lor z = x) \]

该句子用自然语言描述，即集合中存在至少两个不相等的元素，且任意三个元素中都至少有两个相等，因此集合中只存在两个不相等的元素。

习题 11：给出能够在 $(\mathbb{N}; +, \cdot )$ 中定义如下每个关系的公式，假设语言具有相等符号和参数 $\forall, +, \cdot$。

$\set{0}$
$\set{1}$
$\set{\langle m, n\rangle | n 是 \mathbb{N} 中 m 的后继}$
$\set{\langle m, n\rangle | 在 \mathbb{N} 中 m < n}$

$\forall x y \cdot x = y$

$\forall x y \cdot x = y$

$\exists x (n = m + x \land \forall y x \cdot y = y)$ 即 $n = m + 1$

$\exists x (n = m + x \land \exists y x \cdot y \ne x)$ 即 $n=m+x \land x \neq 0$

习题 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}, <)$。

（a）试找出一个句子，它在一个结构中是真的，在另外一个中是假的。

直观来说，$(\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.$

教材 $\S 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.$

本节知识点

本节使用到教材当中的一些公理、定理和规则总结如下：

假言推理（Modus Ponen，又称 MP 规则或直言三段论）：

\[ \frac{\alpha, \alpha \to \beta}{\beta} \]

$\Lambda$ 是 6 组逻辑公理的集合：

重言式；
$\forall x \alpha \to \alpha^x_t$，其中 $t$ 是 $x$ 在 $\alpha$ 中的替换，即把 $\alpha$ 中出现的 $x$ 换成 $t$；
$\forall x (\alpha \to \beta) \to (\forall x \alpha \to \forall x \beta)$；
$\alpha \to \forall x \alpha$，其中 $x$ 在 $\alpha$ 中不是自由出现的（自由出现的意思是无量词限定，例如 $\forall y x + y = 2$ 中 $x$ 是自由出现的，$y$ 不是）；
$x=x$；
$x = y \to (\alpha \to \alpha')$，其中 $\alpha$ 是原子的，$\alpha'$ 是有限次的将 $\alpha$ 中的 $x$ 替换为 $y$ 得到的。

由 $\Gamma \cup \Lambda$ 和假言推理可以获得的公式集叫做 $\Gamma$ 的定理集合。

概化定理：如果 $\Gamma \vdash \varphi$ 且 $x$ 不在 $\Gamma$ 的任何公式中自由出现，则 $\Gamma \vdash \forall x \varphi$。

规则 T：如果 $\Gamma \vdash \alpha_1, \dots, \Gamma \vdash \alpha_n$，且 $\set{\alpha_1, \dots, \alpha_n}$ 重言蕴含 $\beta$ ，那么 $\Gamma \vdash \beta$。

演绎定理：如果 $\Gamma;\gamma \vdash \varphi$，那么 $\Gamma \vdash (\gamma \to \varphi)$。从右到左叫做演绎，从左到右叫演绎定理。

教材 $\S 2.4$ 演绎计算

习题 3：(a) 设 $\A$ 是结构，且令 $s:V \to |\A|$，在基本公式集上定义真值指派 $v$ 如下：

\[ v(\alpha) = T \iff \models_\A \alpha[s] \]

证明：对于任意公式（基本与否均可），有：

\[ \overline{v}(\alpha) = T \iff \models_\A \alpha[s] \]

证明：如果 $\Gamma$ 重言蕴含 $\varphi$，则 $\Gamma$ 逻辑蕴涵 $\varphi$。

证明：使用归纳法证明。对于基本公式 $\alpha$，$\overline{v}(\alpha) = v(\alpha) = T \iff \models_\A \alpha[s]$。

对于公式 $\lnot \alpha$，$\overline{v}(\alpha) = T \iff \overline{v}(\alpha) = F \iff \not \models_\A \alpha[s] \iff \models_\A \lnot \alpha[s]$。

对于公式 $\beta \to \alpha$，$\overline{v}(\beta \to \alpha) = T \iff \overline{v}(\beta) = F \lor \overline{v}(\alpha) = T \iff \models_\A \lnot \beta[s] \lor \models_\A \alpha[s] \iff \models \beta \to \alpha [s]$。

$Q.E.D.$

证明：$\Gamma$ 重言蕴含 $\varphi$，意味着对每个结构 $\A$，若对于每个 $\alpha \in \Gamma$，$\overline{v}(\alpha) = T$，有 $\overline{v}(\varphi) = T$。

因此，对每个结构 $\A$ 和 $s:V \to |\A|$，若对每个 $\alpha \in \Gamma$，都有 $\models_\A \alpha[s]$，则 $\models_\A \varphi[s]$。因此，$\Gamma \models \varphi$。

上述证明实际上展示了“重言蕴含为什么在逻辑上是对的”。

$Q.E.D.$

习题 8：设 $x$ 不在 $\alpha$ 中自由出现，证明 Q2b

\[ \vdash (\alpha \to \exists x \beta) \leftrightarrow \exists x (\alpha \to \beta) \]

在同样的假设下，证明 Q3a：

\[ \vdash (\forall x \beta \to \alpha) \leftrightarrow \exists x (\alpha \to \beta) \]

证明 Q2b：由规则 T，需要证明 $\vdash (\alpha \to \exists x \beta) \rightarrow \exists x (\alpha \to \beta)$ 和 $\vdash (\alpha \to \exists x \beta) \leftarrow \exists x (\alpha \to \beta)$。

通过推导、反证法和假言推理，我们可以得到第一个公式等价于 $ x () (x ) $。现在，根据第 2 组公理和假言推理，我们有 $ x () () $。此外，$ () $ 和 $ () $ 都是重言式。通过假言推理，我们得到 $ x () $ 和 $ x () $。根据推广定理，$ x () $ 重言蕴含 $ (x ) $，根据规则 T，我们得到了需要的结果。

通过推导、反证法和假言推理，我们可以得到第二个公式等价于 $ (x ) x () $。对于这个公式，基于推广定理并假设 $ x $ 没有自由出现在 $ $ 中，我们只需证明 $ (x ) () $，而通过反证法、推导和假言推理，它等价于 $ { , } x $。通过假言推理，我们只需证明 $ x $，或者通过推导 $ x $，或者通过反证法和假言推理，得到 $ x $，这是第 2 组公理的一项。

通过将 $ $ 替换为 $ $ ，将 $ $ 替换为 $ $，并使用反证法的重言式等价性，我们得到 $ (x ) x () $。

$Q.E.D.$

习题 9：（再替换引理）(a) 试证： $(\varphi_y^x)^y_x$ 一般不相等，而且以下两种情况均有可能发生：$x$ 在 $(\varphi_y^x)_x^y$ 中的某个位置上出现，而在 $\varphi$ 中同样的位置上不出现；或者反过来，$x$ 在 $\varphi$ 中的某个位置上出现，而在 $(\varphi_y^x)_x^y$ 中同样的位置上不出现。

证明：如果 $y$ 不在 $\varphi$ 中出现，那么在 $\varphi_y^x$ 和 $(\varphi_y^x)_x^y = \varphi$ 中 $x$ 可替换 $y$。提示：对 $y$ 使用归纳法。

证明：让我们暂时称变量 $ x $ （或 $ y $）的一个实例被 $ x $ 所限定当且仅当该实例位于公式 $ x $ 的某个子公式中。然后，公式 $ $ 中的每一个 $ x $ 或 $ y $ 的实例将会变成 $ x $ 或 $ y $，这取决于它是否被 $ x $ 和/或 $ y $ 限定（对于不同情况）。在其中的两种情况中，如果一个变量没有被 $ y $ 限定（无论是否被 $ x $ 限定），它最终会在 $ (^y_x)y_x $ 中变成 $ x $。如果变量被 $ y $ 限定，那么根据它是否被 $ x $ 限定，它会分别保持与 $ $ 中相同或变成 $ y $ 在 $ (^y_x)y_x $ 中。因此，当 $ y $ 可能变成 $ x $ 且 $ x $ 可能变成 $ y $ 时，我们会有若干潜在情况。基于此，设 $ = Py y Px $。那么 $ (^y_x)y_x = Px y Py $，其中一个自由 $ x $ 最终变成 $ y $，一个自由 $ y $ 最终变成 $ x $。

基于此观察，显然如果 $ $ 中没有 $ y $，那么 a) 没有 $ y $ 可以变成 $ x $（没有额外的 $ x' $），并且 b) 没有 $ x $ 被 $ y $ 所限定，因此没有 $ x $ 可以变成 $ y $（没有缺失的 $ x' $）。(b) 部分给出了一个更正式的证明。

$Q.E.D.$

证明：如建议的那样，我们通过归纳法证明该陈述。对于变量或常量符号 $ z y $，如果 $ z x $，则 $ ^z_y = (^y_x)y_x = z $，否则 $ ^z_y = y $ 且 $ (^y_x)y_x = x = z $。对于不包含 $ y $ 的项 $ t = f_i t_1 t_n $，通过归纳，$(t^y_x)y_x = f_i ((t_1)^y_x)y_x ((t_n)^y_x)y_x = f_i t_1 t_n = t$。同样，对于不包含 $ y $ 的原子公式 $\varphi = Pt_1 \ldots t_n$，通过归纳，$(\varphi^y_x)^y_x = P((t_1)^y_x)^y_x \ldots ((t_n)^y_x)^y_x = \varphi$（并且 $ x $ 可以替代 $ y $ 因为后者也是一个原子公式）。

此外，根据定义和归纳，如果不包含 $ y $ 的 $\alpha$ 和 $\beta$ 使得 $ x $ 可替代 $ y $ 在 $ ^y_x $ 和 $ ^y_x $ 中，那么 a) $ ()^y_x = ^y_x $，$ x $ 可替代 $ y $ 在其中，且 b) $ (()^y_x = ^y_x ^y_x $。此外，$ (x )^y_x = x $ 不包含任何 $ y $，因此 $ x $ 不在 $\{x, y\}$ 中，$ x $ 不自由出现在其中，$ x $ 可替代 $ y $ 在其中，且 $ ((x )^y_x)y_x = x(^y_x)y_x = x $。

$Q.E.D.$

习题 11：证明 Eq3：

\[ \vdash \forall x \forall y \forall z (x = y \to y = z \to x = z) \]

证明：在数理逻辑中，$\to$ 运算符具有右结合性，即 $\alpha \to \beta \to \gamma$ 的含义是 $\alpha \to (\beta \to \gamma)$。本题的表达中不适用括号。

根据泛化定理，我们只需证明 $ x = y y = z x = z $。根据公理组 5，我们有 $ x = x $。根据公理组 6，我们有 $ x = y x = x y = x $ 和 $ y = x y = z x = z $。前两个式子根据规则 T 可以推出 $ x = y y = x $，再结合第三个式子并再次应用规则 T，可以推出 $ x = y y = z x = z $。

$Q.E.D.$

本节知识点

可靠性定理：如果 $\Gamma \vdash \varphi$，那么 $\Gamma \models \varphi$。

引理 25A：逻辑公理都是恒真的。

完备性定理（哥德尔 1930）：

如果 $\Gamma \models \varphi$，那么 $\Gamma \vdash \varphi$。
任意和谐的公式集都是可满足的。

紧致性定理：

如果 $\Gamma \vdash \varphi$，那么存在某个有限的 $\Gamma_0 \subseteq \Gamma$，有 $\Gamma_0 \vdash \varphi$。
如果 $\Gamma$ 的每个有限子集 $\Gamma_0$ 都是可满足的，那么 $\Gamma$ 是可满足的。特别地，句子集 $\Sigma$ 有模型当且仅当其每个有限子集有模型。

可枚举定理：

对合理的语言，恒真（valid）合式公式的集合是能行可枚举的。

定理 26A：如果句子集合 $\Sigma$ 有任意大的计数的有限模型，那么就有一个无限模型。

定理 26C：对有限语言中的有限结构 $\A$，$\Th \ \A$ 是可判定的。

教材 $\S 2.5$ 可靠性与完备性理论

\[ \def\Th{\mathrm{Th}} \]

习题 1：（语义规则 EI）假设常数符号 $c$ 不在 $\varphi$、$\psi$ 和 $\Gamma$ 中出现，$\Gamma; \varphi_c^x \models \psi$，证明：$\Gamma; \exists x \varphi \models \psi$。（不使用可靠性定理和完备性定理。）

证明：该规则将推论 24H 中的 $\vdash$ 换成了 $\models$，该题应该从语义方面证明而不是从语法方面。

$\Gamma ; \varphi^{x}_c \models \psi \iff$ 对任意 $\A$ 和 $s$，如果 $\models_{\A} \Gamma[s]$ 且 $\models_{\A} \varphi^{x}_{c}[s]$，则 $\models_{\A} \psi[s]$；

$\iff$ 对任意 $\A$ 和 $s$，如果 $\models_{\A} \Gamma[s]$ 且 $\nvDash_{\A} \psi[s]$，则 $\models_{\A} \neg \varphi[s(x|c^{\A})]$

$\iff$ 对任意 $\A$ 和 $s$，如果 $\models_{\A} \Gamma[s]$ 且 $\nvDash_{\A} \psi[s]$，则对所有 $d \in |\A|$ 有 $\models_{\A} \neg \varphi[s(x|d)]$

$\iff$ 对任意 $\A$ 和 $s$，如果 $\models_{\A} \Gamma[s]$ 且 $\nvDash_{\A} \psi[s]$，则 $\models_{\A} \forall x \neg \varphi[s]$

$\iff$ $\Gamma ; \neg \forall x \neg \varphi \models \psi$

$\iff \Gamma; \exists x \varphi \models \psi$；

上述证明完成了“在 $\A$ 中把 $x$ 替换成 $c^\A$” 这件事。

$Q.E.D.$

习题 2（不考）：证明完备性定理 (a) 与 (b) 等价。提示：$\Gamma \vdash \varphi$ 当且仅当 $\Gamma \cup \{\neg \varphi\}$ 是不可满足的，且 $\Delta$ 是可满足的当且仅当 $\Delta \nvDash \bot$，其中 $\Delta$ 是某个不可满足的、可批驳的公式集，如 $\neg \forall x x = x$。

说明：类似地，可靠性定理也适用于每个可满足的公式集是和谐的。

证明：在计算机学科中，consistent 被翻译为“一致的”。

先证充分性。若 (a) 成立。若 $\Gamma$ 不可满足，则 $\Gamma \models \set{\phi, \lnot \phi}$，因此 $\Gamma \vdash \set{\phi, \lnot \phi}$，即 $\Gamma$ 不和谐。推出 (b) 的逆否命题。

再证必要性。若 (b) 成立。若 $\Gamma \models \phi$，则对任意 $\A, s$，$\models_\A \Gamma[s] \implies \models_\A \phi[s]$ 即 $\not\models_\A \lnot\phi[s]$。即 $\Gamma ; \lnot \phi$ 是不可满足的，也因此是不和谐的。导出矛盾，因此 $\Gamma \vdash \phi$。

$Q.E.D.$

习题 3：设 $\Gamma \vdash \varphi$，且 $P$ 是不在 $\Gamma$ 和 $\varphi$ 中出现的谓词符号。是否存在不出现 $P$ 的从 $\Gamma$ 到 $\varphi$ 的演绎？提示：这个问题有两种不同的方法。“软”方法使用两个不同的语言，一个含有 $P$，另一个不含 $P$；“硬”方法则考虑是否能够可以从 $\Gamma$ 到 $\varphi$ 的演绎中消去 $P$。

必然存在不出现 $P$ 的从 $\Gamma$ 到 $\varphi$ 的演绎。

证明：使用“软”方法完成证明。

对于一个不含 $P$ 的语言，在该语言中 $\Gamma \vdash \varphi$，存在不出现 $P$ 的从 $\Gamma$ 到 $\varphi$ 的演绎，设该演绎为 $q$。对于包含 $P$ 的语言，$q$ 同样是该语言中一个从 $\Gamma$ 到 $\varphi$ 的演绎。

$Q.E.D.$

习题 4：设 $\Gamma = \{ \neg \forall v_1 Pv_1, Pv_2, Pv_3, \dots \}$，$\Gamma$ 是否和谐？是否可满足？

证明：假设 $\A = (\set{0,1};P)$，其中 $P^\A = \set{\langle 1 \rangle}$，且 $s :V \to |\A|$ 使得 $\forall i>0s(v_i) = 1$。于是 $\models_\A Pv_i[s], \models_\A P v_1[s(v_1|1)]$ 并且 $\not\models_\A P v_1[s(v_1|0)]$。

因此 $\Gamma$ 可满足。由可靠性和完备性定理得，$\Gamma$ 是和谐的。

$Q.E.D.$

教材 $\S 2.6$ 理论的模型

习题 1（不考）：证明下述句子是有限恒真的（即在每个有限结构中是真的）：

\[ (a) \exists x \exists y \exists z [(Pxf x \rightarrow Pxx) \lor (Pxy \land Pyz \land \lnot Pxz)] \]

提示：这些句子的逆的任意模型都是无限的。

证明：题中的 negation 在计算机科学中一般被翻译为“否定”而不是“逆”。

题中公式的含义是，在论域中存在一个 $x$，使得 $Pxfx \rightarrow Pxx$ 或者“$P$ 在 $x$ 处不传递”。

本题的证明中反复使用了 6 条公理和概化公理。

我们按照一阶逻辑的规则对句子的逆进行恒等变形：

\[ \neg \exists x \exists y \exists z \big((Pxf x \to Pxx) \lor (Pxy \land Pyz \land \neg Pxz)\big)\\ \iff \neg \exists x \exists y \exists z \big[\lnot (Pxf x \to Pxx) \rightarrow (Pxy \land Pyz \land \neg Pxz) \big]\\ \iff \neg \exists x \big[\neg (Pxf x \to Pxx) \rightarrow \exists y \exists z (Pxy \land Pyz \land \neg Pxz \big]\\ \iff \forall x \neg \big[\lnot (Pxf x \to Pxx) \rightarrow \exists y \exists z (Pxy \land Pyz \land \neg Pxz) \big]\\ \iff \forall x \big[\neg (Pxf x \to Pxx) \land \neg \exists y \exists z (Pxy \land Pyz \land \neg Pxz)\big]\\ \iff \forall x \big[Pxf x \land \neg Pxx \land \forall y \forall z (\neg Pxy \lor \neg Pyz \lor Pxz)\big]\\ \iff \forall x \big[Pxf x \land \neg Pxx \land \forall y \forall z (Pxy \to (Pyz \to Pxz))\big] \]

如果 $\A$ 是该句子的模型，我们有：

\[ \Th \ \A \vdash \{Pxf x; \neg Pxx; \forall y \forall z (Pxy \to Pyz \to Pxz)\} \]

只要证符合上述条件的 $\A$ 必是无限的。

由子集 $\set{Pxfx, \lnot Pxx}$ 可知，$\Th \ \A \vdash \set{x \neq fx}$。由 $Pxfx \vdash \set{Pfxffx, Pffxfffx , \dots}$。由传递性 $\forall y \forall z (Pxy \to Pyz \to Pxz)$ 可知，$\Th \ \A \vdash \set{Pf^nxf^mx}$ 对任意 $0 \le n \lt m$ 都成立。因此，$\A$ 是无限的。

$Q.E.D.$

特别地，$\A = (\mathbb{N};P=<,f=S)$ 即自然数上的后继函数和小于关系是该 (a) 的逆的一个模型。

习题 2：设 $T_1$ 和 $T_2$ 是（同一语言的）理论，使得：(i) $T_1 \subseteq T_2$ (ii) $T_1$ 是完备的 (iii) $T_2$ 是可满足的。证明：$T_1 = T_2$。

证明：对任意句子 $\sigma$，$\sigma \in T_2 \Rightarrow \lnot \sigma \notin T_2 \Rightarrow \lnot \sigma \notin T_1 \Rightarrow \sigma \in T_1$，又 $T_1 \subseteq T_2$，由外延公理，有 $T_1 = T_2$。

$Q.E.D.$

\[ \def\Th{\mathrm{Th}} \def\Cn{\mathrm{Cn}} \def\Mod{\mathrm{Mod}} \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \def\N{\mathfrak{N}} \def\K{\mathcal{K}} \]

本节知识点

理论是逻辑蕴涵意义下封闭的句子集合，$T$ 是一个理论当且仅当 $T$ 是一些句子的集合，该集合使得语言中的任意句子 $\sigma$，

\[ T \models \sigma \Rightarrow \sigma \in T \]

注意：我们仅指句子，而不是带有自由变量的公式。

对语言的结构类 $\K$，定义其理论为（记作 $\Th \ \K$）

\[ \Th \ \K = \set{ \sigma | \sigma \ 在 \ \K \ 的每个元素中都是真的} \]

这一概念由先前的特殊情况 $\K = \set{\A}$ 而来。

对于句子集合 $\Sigma$，定义 $\Mod \ \Sigma$ 为 $\Sigma$ 所有模型的类。$\Th \ \Mod \ \Sigma$ 则是在 $\Sigma$ 的所有模型中都是真的的所有句子的集合。称此集合为 $\Sigma$ 的推论集，记作 $\Cn \ \Sigma$，这样

\[ \Cn \Sigma = \set{\sigma | \Sigma \models \sigma} \\ = \Th \ \Mod \ \Sigma \]

一个句子集合是一个理论当且仅当 $T = \Cn \ T$。

一个理论 $T$ 称为完备的，当且仅当对每个句子 $\sigma$，或者 $\sigma \in T$，或者 $(\lnot \sigma) \in T$，

理论 $T$ 是有限可公理化的当且仅当对于某个有限句子集合 $\Sigma$，$T = \Cn\ \Sigma$。

定义 $L_0$ 在 $T_1$ 中的解释 $\pi$ 是 $L_0$ 的参数集上的一个函数，满足

$\pi$ 把 $L_1$ 中的一个公式 $\pi_\forall$ 指派给 $\forall$，$\pi_\forall$ 中至多只有 $v_1$ 是自由出现的，使得

\[ T_1 \models \exists v_1 \pi_\forall \]

其中的思想是，

$ T*1 v_1 v_n (_v(v_1) _v(v_n) $ $ x (_v(x) v{n+1} (f(v_1,,v{n+1}) v{n+1}=x))) . $ (2) $\pi$ 为每个 $n$ 元谓词参量 $P$ 指派了 $L_1$ 中的一个公式 $\pi_P$, 公式中至多只有 $v_1,\cdots,v_n$ 是自由出现的. (3) $\pi$ 为每个 $n$ 元函数符号 $f$ 指派了 $L_1$ 中的一个公式 $\pi_f$, 公式中至多只有 $v_1,\cdots,$ $v_n,v*{n+1}$ 是自由出现的，使得 $ T1 v_1 v_n (_v(v_1) _v(v_n) $ $ x (_v(x) v{n+1} (f(v_1,,v{n+1}) v_{n+1}=x))) . $ 换句话说，$\pi_c$ 定义了一个单点，它也在 $\pi_v$ 定义的集合中。

紧致性定理：

如果 $\Gamma \vdash \varphi$，那么存在某个有限的 $\Gamma_0 \subseteq \Gamma$，有 $\Gamma_0 \vdash \varphi$；
如果 $\Gamma$ 的每个有限子集 $\Gamma_0$ 都是可满足的，那么 $\Gamma$ 是可满足的。特别地，句子集 $\Sigma$ 有模型当且仅当其每个有限子集有模型。

习题 5（不考）：给出与如下公式等价的前束公式

\[ (a) (\exists x A x \land \exists x B x) \to Cx \]

其前束公式为：

\[ \exists y \exists z ((Ay \land Bz) \to Cx) \]

习题 7：考虑带有二元谓词符号 $<$ 的语言，设 $\N = (\mathbb{N}; <)$ 是包含（通常序的）自然数的结构。证明：存在某个初等等价于 $\N$ 的 $\A$，使得 $<^\A$ 具有降序链。（即在 $|\A|$ 中存在 $a_0, a_1, \cdots$，使得对所有 $i$ 有 $\langle a_{i+1}, a_i \rangle \in <^\A$。）

提示：应用紧致性定理。

说明：该习题的目的在于说明在这个语言中无法表达“不存在降序链。”

证明：构造 $<^\A$：$\langle a^\A, b^\A \rangle \in <^\A$ 当且仅当 $\langle b^\N, a^\N \rangle \in <^\N$。显然 $\A \equiv \N$，且在 $\A$ 中存在 $<^\A$ 的降序链，该降序链 $a_0, a_1, \cdots$ 对应的正是 $\N$ 中的升序链。

$Q.E.D.$

习题 10：设有一个不带函数符号的有限语言，

（a）（不考）证明：可满足的 $\exists_2$ 句子集是可判定的（术语及相关背景见 2.2 节的习题 19）；

（b）证明：恒真的 $\forall_2$ 句子集是可判定的。（$\forall_2$ 公式是指具有形式 \[\forall x_1 \dots \forall x_m \exists y_1 \dots \exists y_n \theta\] 的公式，其中 $\theta$ 是无量词的公式。）

说明：在一阶逻辑中，“判定问题”（Entscheidungs 问题）就是在给定一个公式后判定其是否恒真。由于丘奇定理（3.5 节），这一问题通常是无解的。这个习题给出的是判定问题中的一个可解的情形。

证明：我们知道 $\exists_2$ 句子是可满足的，当且仅当其在一个有限模型内是可满足的。在先前的习题中，我们可以判定它是否有任意模型，即其是否可满足。

证明：$\sigma$ 是一个可行的 $\forall_2$ 句子，当且仅当 $\lnot \sigma$ 是不可满足的。通过 (a)，我们知道它是可判定的。

教材 $\S 2.7$ 理论之间的解释（不考）

习题 1：假设 $L_0$ 和 $L_1$ 含有相同参量的语言，但 $L_0$ 中有一个 $n$ 元函数符号 $f$ 不在 $L_1$ 中，同时 $L_1$ 中有一个 $(n + 1)$ 元谓词符号 $P$ 不在 $L_0$ 中。证明对于 $L_0$ 的任意理论 $T$，存在一个忠实解释将 $T$ 解释到 $L_1$ 上。

证明：简单来说，忠实解释是指能够保持理论 $T$ 中所有公式的真假值不变的解释。

要证明对于 $L_0$ 的任意理论 $T$，存在一个忠实解释将 $T$ 解释到 $L_1$ 上，我们可以通过构造一个从 $L_0$ 到 $L_1$ 的忠实解释来实现。

构造过程

定义解释映射：首先，我们需要定义一个映射，将 $L_0$ 中的项和公式转换为 $L_1$ 中对应的项和公式。对于 $L_0$ 中的项，如果它们不涉及函数符号 $f$，则直接对应到 $L_1$ 中相同的项。对于涉及 $f$ 的项，如 $f(t_1, t_2, ..., t_n)$，我们定义其在 $L_1$ 中的对应项为 $t$，其中 $P(t_1, t_2, ..., t_n, t)$ 成立。这实际上是在说，对于 $L_0$ 中的每一组输入 $t_1, t_2, ..., t_n$，在 $L_1$ 中存在一个输出 $t$，使得 $P$ 关系成立。

定义公式转换：接下来，我们需要定义如何将 $L_0$ 中的公式转换为 $L_1$ 中的公式。对于不涉及 $f$ 的原子公式，可以直接对应到 $L_1$ 中相同的原子公式。对于形如 $f(t_1, t_2, ..., t_n) = s$ 的原子公式，我们将其转换为 $L_1$ 中的公式 $P(t_1, t_2, ..., t_n, s)$。对于复合公式，按照标准的逻辑运算符的转换规则进行转换。

验证忠实性：最后，我们需要验证这个解释是忠实的，即它保持了 $L_0$ 中的所有公式的真假值。这意味着，如果一个公式在 $L_0$ 下是真（或假）的，那么经过解释后，在 $L_1$ 下它也应该保持同样的真假值。这可以通过结构归纳法来证明，首先证明对于原子公式这一点成立，然后逐步扩展到所有复杂的公式。

忠实性的证明

对于原子公式，如 $f(t_1, t_2, ..., t_n) = s$，在 $L_0$ 下它为真意味着 $f$ 在输入 $t_1, t_2, ..., t_n$ 时确实产生输出 $s$。在 $L_1$ 下，这意味着存在一个元素 $s$ 使得 $P(t_1, t_2, ..., t_n, s)$ 为真，这与原始的原子公式在 $L_0$ 下的意义是一致的。

对于复合公式，忠实性可以通过逻辑运算符的性质和原子公式的忠实性来保证。例如，如果一个合取式在 $L_0$ 下为真，那么它的每个组成部分在 $L_0$ 下也为真，根据忠实性，这些组成部分在 $L_1$ 下也应为真，因此整个合取式在 $L_1$ 下也为真。

综上所述，通过这种方式构造的解释是一个忠实的解释，它可以将 $L_0$ 的任意理论 $T$ 解释到 $L_1$ 上，而不会改变公式的真假值。

$Q.E.D.$

习题 2：设 $L_0$ 是含有等号及二元函数符号 $+$ 和 $\cdot$ 的语言，$L_1$ 也一样，只不过用三元谓词符号表示加法和乘法。令 $\mathfrak{M}_i = (\mathbb{N};+, \cdot)(i = 0, 1)$ 分别是包含自然数和加法、乘法的语言 $L_i$ 的结构。证明在 $\mathfrak{M}_0$ 中由 $L_0$ 公式定义的任何关系都能在 $\mathfrak{M}_1$ 中由 $L_1$ 公式定义。

证明：假设非空的 $n$ 元关系 $R$ 可以由 $L_0$ 公式 $\phi$ 在 $\N_0$ 中定义（对于空关系结论显而易见）。

考虑 $\pi$ 从 $L_0$ 参数集到 $L_1$ 公式集中的映射，使得 $\pi_\vee = v_1 = v_1$ ，$\pi_+ = +v_1v_2v_3$ 和 $\pi_\cdot = \cdot v_1v_2v_3$ 。因为 $\exists v_1v = v_1$ ，$\forall v_1\forall v_2\exists x\forall v_3 +v_1v_2v_3 \leftrightarrow v_3 = x$ ，以及 $\forall v_1\forall v_2\exists x\forall v_3 \cdot v_1v_2v_3 \leftrightarrow v_3 = x$ 在 $\N_1$ 中为真，所以 $\pi$ 是 $\N$ 的 $L_0$ 到 $\Th \N_1$ 的解释，并且 $\N_1$ 是 $\Th\N_1$ 的模型。

于是，$|^\pi\N_1| = \mathbb{N}$ ，$a + ^{^\pi\N_1} b = c$ 当且仅当 $+^{\N_1}abc$ 当且仅当 $a + b = c$ ，以及 $a \cdot^{^\pi\N_1} b = c$ 当且仅当 $\cdot^{\N_1}abc$ 当且仅当 $a \cdot b = c$ ，表明 $^\pi\N_1 = \N_0$ 。但是，对于每一个 $s:V \to \mathbb{N}$ ，$\models_{\N_0} \phi[s]$ 当且仅当 $\models_{^\pi\N_1}[s]$ 当且仅当 $\models_{\N_1} \phi^n[s]$ （引理 27B）。这意味着 $R$ 可以在 $\N_1$ 中由 $\phi^n$ 定义。

$Q.E.D.$

教材 $\S 3$ 不可判定性

教材 $\S 3.3$ 数论的子理论

\[ \def\N{\mathfrak{N}} \def\K{\mathcal{K}} \def\lh{\mathrm{lh}} \]

习题 1：证明：在结构 $( \mathbb{N}; \cdot, E)$ 中，我们能够定义加法关系 $\set{\langle m, n, m+n\rangle | m, n \in \mathbb{N}}$。进一步证明在结构 $\set{0}$ 中，序关系 $<$，后继关系 $\set{\langle n, S(n) \rangle | n \in \mathbb{N}}$ 都是可定义的。(说明：如果把结构 $( \mathbb{N}; \cdot, E)$ 简化为 $( \mathbb{N}; E)$, 这个结果还能加强。在此处，乘法关系可以通过指数运算的一个法则: $(d^a)^b = d^{ab}$ 来定义。）

证明：在算数关系中，很容易使用对数将乘法转化为加法。例如 $\log(nm) = \log(n) + \log(m)$。利用这一思路，定义加法关系为 $\set{\langle n, m, p\rangle | 2En \cdot 2Em = 2Ep}$，其中 $2 = S^20$。

在结构 $\set{0}$ 中，定义序关系为 $\set{\langle n, m\rangle | \exists x (x + x \neq x \land n + x = m)}$；

在算数关系中，后继可以用 $m = n+1$ 表示，只要构造 $x=1$ 即可。

定义后继关系为 $\set{\langle n, m\rangle | \exists x (x + x \neq x \land \forall y \forall z (y+y\neq y \to z+z \neq z \to y+z\neq x) \land n + x = m)}$。

$Q.E.D.$

习题 2（不考）：证明定理 33C, 即（在 $\N$ 中）真的无量词句子都是 $A_E$ 的定理。

证明：

首先，令 $\tau$ 是一个原子句子。那么，$\tau = t < u$ 或 $\tau = t = u$，其中 $t$ 和 $u$ 是不含变量的项。根据引理 33B，存在 $m$ 和 $n$ 使得 $A_E \vdash t = S^m 0$ 和 $A_E \vdash u = S^n 0$。进一步地，$A_E \vdash S^m 0 = S^n 0$ 当且仅当 $m = n$，而 $A_E \vdash S^m 0 \neq S^n 0$ 当且仅当 $m \neq n$（根据 S1 和 S2），并且，利用这一点，根据引理 33A，$A_E \vdash S^m 0 < S^n 0$ 当且仅当 $m < n$，而 $A_E \vdash S^m 0 \not< S^n 0$ 当且仅当 $m \geq n$。利用这些事实，我们可以证明 $A_E \vdash t < u$ 当且仅当 $m < n$，而 $A_E \vdash \neg t < u$ 当且仅当 $m \geq n$，并且 $A_E \vdash t = u$ 当且仅当 $m = n$，而 $A_E \vdash \neg t = u$ 当且仅当 $m \neq n$。例如，对于 $m < n$，$A_E \vdash \forall x \forall y \forall z (x = y \rightarrow x < z \rightarrow y < z)$ 和 $A_E \vdash \forall x \forall y \forall z (x = y \rightarrow z < x \rightarrow z < y)$（演绎公理组 6，DA6），并且利用 DA2，我们可以推导出 $A_E \vdash S^m 0 = t \rightarrow S^m 0 < S^n 0 \rightarrow t < S^n 0$ 和 $A_E \vdash S^n 0 = u \rightarrow t < S^n 0 \rightarrow t < u$，并且类似地对于 $A_E \vdash \neg u = t$ 和 $A_E \vdash \neg u < t$。

其次，令 $\tau$ 是一个形式为 $\neg \tau_1$ 或 $\tau_2 \rightarrow \tau_3$ 的句子，并且在 $\mathfrak{A}$ 中为真，其中 $\tau_i$ 是使得 $A_E \vdash \tau_i$ 当且仅当 $\tau_i$ 在 $\mathfrak{A}$ 中为真，而 $A_E \vdash \neg \tau_i$ 当且仅当 $\tau_i$ 在 $\mathfrak{A}$ 中为假。我们证明同样的结论也适用于 $\tau$。确实，如果 $\tau$ 在 $\mathfrak{A}$ 中为真，那么分别地，$\tau_1$ 在 $\mathfrak{A}$ 中为假，而 $\tau_2$ 在 $\mathfrak{A}$ 中为假或 $\tau_3$ 在 $\mathfrak{A}$ 中为真，这意味着 $A_E \vdash \neg \tau_1$，并且 $A_E \vdash \neg \tau_2 \lor \tau_3$，即 $A_E \vdash \tau$；否则，$\tau_1$ 在 $\mathfrak{A}$ 中为真，而 $\tau_2$ 在 $\mathfrak{A}$ 中为真，$\tau_3$ 在 $\mathfrak{A}$ 中为假，这意味着 $A_E \vdash \neg \neg \tau_1$，并且 $A_E \vdash \neg (\neg \tau_2 \lor \tau_3)$，即 $A_E \vdash \neg \tau$。

$Q.E.D.$

习题 5（不考）：证明：序列数字的集合是可表示的（编目 10）。

证明：序列数的集合定义为 $ = { b x (x b x y (y < x y ) } $，其中 $ $ 是素数的集合，而 $ $ 是可整除关系。换句话说，如果某个素数 $ x $ 能整除 $ b $，那么所有小于 $ x $ 的素数 $ y $ 也能整除 $ b $。特别地，这在 $ b = 1 = $ 和 $ b = 2 = $ 时是显然成立的。通过目录项 0、3、4 和 5，我们得出结论 $ $ 是可表示的。

$Q.E.D.$

习题 6（不考）：3 是序列数字吗？$\lh 3$ 等于多少？求出 $(1 \ast 3) \ast 6$ 和 $1 \ast (3 \ast 6)$。

$3 = 2^0 \cdot 3^1$ 是不是一个序列数，因为 $ p_1 = 3 $ 能整除 3，但 $ p_0 = 2 $ 不能整除 3。然而，形式上，我们仍然可以计算问题中的公式。

首先，形式上，$\text{lh} b$ 定义为最小的 $ n $，使得要么 $ b = 0 $，要么 $ < p_n, b > $，其中 $\mathcal{D}$ 是可整除关系。在我们的例子中，$ < p_0, 3 > $，因此 $\text{lh} 3 = 0$。

其次，形式上，$(b)_c$ 定义为最小的 $ n $，使得要么 $ b = 0 $，要么 $ < p_c^{n+2}, b > $。在我们的例子中，$(3)_c = 0$ 对所有 $ c $（包括 $ c = 1 $ 时 $ p_1 = 3 $）。

最后，$ a _ b = a _{i < b} p_i^{(b)_i + 1} $ 对所有自然数也定义。特别地，由于 $\text{lh} 1 = 0$，$ 1 _ b = p_i^{(b)_i + 1} $，这仅仅是能整除 $ b $ 的最大序列数。因此，$ 1 * 3 = 1 $ 和 $ (1 * 3) * 6 = 6 $（$ 6 = , 0 $ 是一个序列数）。进一步，$ 3 * 6 = 3 p_i^{(6)_i + 1} = 3 = 18 = 2^1 ^2 = < 0, 1 > $。因此，$ 1 _ (3 _ 6) = 18 $。

习题 10：设 $ R $ 是可表示的关系，$ g $ 和 $ h $ 是可表示的函数。证明：$ f $ 是可表示的，其中

\[ f(\bar{a}) = \begin{cases} g(\bar{a}) & \text{若 } \bar{a} \in R, \\ h(\bar{a}) & \text{若 } \bar{a} \notin R. \end{cases} \]

证明：函数 $ f $ 可以表示为组合（定理 33L）$ d(g(), h(), K_R()) $，其中 $ g $, $ h $, $ K_R $（目录项 1），且 $ d(x, y, z) = x z + y (1 - z) $ 是可表示的。

$Q.E.D.$

EagleBear2002 的博客

数理逻辑-期末考点合集

讲义 \(\S 0.2\) 集合

讲义 \(\S 0.2.15\) 良序关系

讲义 \(\S 0.2.17\) 自然数的定义

讲义 \(\S 0.2.18\) 数学归纳法

讲义 \(\S 0.2.19\) 有穷集合和无穷集合

讲义 \(\S 0.2.21\) 有穷集合

讲义 \(\S 0.2.22\) 可数集合

讲义 \(\S 0.2.24\) 不可数集合（不考）

讲义 \(\S 0.2.25\) 序数

讲义 \(\S 0.2.26\) 超穷归纳法

讲义 \(\S 0.2.28\) 可数序数

讲义 \(\S 0.2.29\) 基数

教材 \(\S 1\) 命题逻辑

教材 \(\S 1.1\) 命题逻辑的语言

教材 \(\S 1.2\) 真值指派

教材 \(\S 1.3\) 解析算法

教材 \(\S 1.4\) 归纳与递归

教材 \(\S 1.5\) 命题连接词

教材 \(\S 1.7\) 紧致性和能行性（不考）

教材 \(\S 2\) 一阶逻辑

教材 \(\S 2.2\) 真值与模型

教材 \(\S 2.3\) 解析算法

教材 \(\S 2.4\) 演绎计算

教材 \(\S 2.5\) 可靠性与完备性理论

教材 \(\S 2.6\) 理论的模型

教材 \(\S 2.7\) 理论之间的解释（不考）

教材 \(\S 3\) 不可判定性

教材 \(\S 3.3\) 数论的子理论