数理逻辑-期末考点合集

$$$$

摘要

本文是 2024Fall-数理逻辑 的期末考点合集，包括讲义第 0 章、教材第 1-3 章内容，并标注了考点。

本文添加了一些笔者对知识的理解，这部分注明不是来自讲义或教材，仅供参考。中文版《数理逻辑（第二版）》教材中存在许多翻译错误和公式排版、印刷错误，本文指出了其中一些错误并注明错处。

考试题型：

简答题：9 个，每个 5 分，共 45 分。3 个写文字的，6 个带构造的。

大题：6 个（5 题 9 分，1 题 10 分）。第 6、7 大题，注意区分本科生/研究生题目。

主要考基本概念。

大佬镇场

讲义 $\mathrm{\S }0.2$ 集合

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

讲义 $\mathrm{\S }0.2.15$ 良序关系

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

讲义 $\mathrm{\S }0.2.17$ 自然数的定义

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

自然数的定义：$0=\mathrm{\varnothing },1=0^{+}$。

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

讲义 $\mathrm{\S }0.2.18$ 数学归纳法

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

三歧性：$\mathrm{\forall }x,y\in A.x\in y\vee x=y\vee y\in x$。

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

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

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

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

1. 若 $b\in A$ 则 $b\subseteq A\subseteq A^{+}$；
2. 若 $b\notin A$ 则 $b=A$，此时 $b\subseteq A^{+}$ 成立。

$Q.E.D.$

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

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

1. 若 $n=0$，显然命题 $0=n$ 成立；
2. 若 $n=1$，即 $n=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$，显然命题 $0\in n$ 成立；
3. 若 $n=k(k>1)$ 时命题 $0\in n$ 成立，则 $n=k+1$ 时，$n=k\cup \{k\}$，显然命题 $0\in n$ 成立。

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

$Q.E.D.$

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

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

证明：构造 $f:\omega \to {\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$ 为满足如下条件的集合：

1. $A\cap A_1=\mathrm{\varnothing },B\cap B_1=\mathrm{\varnothing }$；
2. $A\sim B,A_1\sim B_1$；

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

证明：由题意得，$\mathrm{\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)=\{\begin{array}{cc}f(x)& \text{if }x\in A\\ g(x)& \text{if }x\in A_1\end{array}$$

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

$Q.E.D.$

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

(1)$A⪯B$ 当且仅当 $A$ 与 $B$ 的某个子集等势。

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

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

$Q.E.D.$

讲义 $\mathrm{\S }0.2.21$ 有穷集合

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

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

证明：$A$ 是有穷集合

$\Rightarrow \mathrm{\exists }n\in \omega .A⪯n$

$\Rightarrow B⪯n$

$\Rightarrow B$ 是有穷集合。

$Q.E.D.$

讲义 $\mathrm{\S }0.2.22$ 可数集合

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

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

$$h(n)=\{\begin{array}{cc}f(\frac{n}{2})& \text{if }n\text{ 为偶数}\\ g(\frac{n-1}{2})& \text{if }n\text{ 为奇数}\end{array}$$

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

$Q.E.D.$

习题 2：证明：

（1）对任意 $k\in \omega$ 有，${\omega }^k$ 都是可数集合（约定 ${\omega }^0=\{\mathrm{\varnothing }\},{\omega }^1=\omega$）；

（2）集合 $\bigcup \{{\omega }^k|k\in \omega \}$ 是可数的。

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

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

下面进行归纳：

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

$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.$

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

$Q.E.D.$

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

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

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

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

1. 若 $f\notin \mathsf{FUN}(\omega ,\omega )$，与 $\mathsf{FUN}(\omega ,\omega )$ 的定义相矛盾；
2. 若 $f\in \mathsf{FUN}(\omega ,\omega )$，但 $\mathrm{\forall }n\in \mathbb{N}.f(n)\ne f_n(n)$，矛盾。

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

$Q.E.D.$

讲义 $\mathrm{\S }0.2.25$ 序数

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

本书中对序数的定义并不直观，也没有说明序数的用途。此处补充序数的描述：

在数理逻辑中，序数（ordinal numbers） 是一种用于表示集合的“大小”和“顺序类型”的概念，尤其在集合论、公理集合论和模型论中起着重要作用。序数扩展了自然数的概念，可以用来描述无穷集合的大小和结构，起到了将有限和无限统一到同一框架下的作用。

序数是良序集的等价类。直观地，序数可以理解为一种表示“位置”的标签，且这些标签本身是有序的。

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

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

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

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

由 $S$ 是传递集合，$\mathrm{\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.$

（2）证明：由传递集合得，$\mathrm{\forall }\beta \in S.\beta \subseteq \bigcup S$。

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

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

$Q.E.D.$

讲义 $\mathrm{\S }0.2.26$ 超穷归纳法

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

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

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

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

（1）证明：

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

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

$\mathrm{\forall }\beta \in \alpha .\mathrm{\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.$

（2）证明：由 $\beta$ 是 $\alpha$ 中最大元，$\mathrm{\forall }\gamma \in \alpha .\gamma \le \beta$，且 $\alpha$ 为后继序数（TODO：这一步怎么来的？）。设 $\alpha ={\beta }_0^{+}={\beta }_0\cup \{{\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.$

讲义 $\mathrm{\S }0.2.28$ 可数序数

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

定义 ${\omega }_{\alpha +1}=\{\beta \mid \beta \text{ 是序数且 }\beta ⪯{\omega }_{\alpha }\}$。

讲义 $\mathrm{\S }0.2.29$ 基数

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

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

$$\mathrm{card}A=\mathrm{card}B⟺A\sim B$$

习题 1：设 $\alpha$ 为基数，$\kappa$ 为集合 $\{\beta |\beta \mathrm{是}\mathrm{序}\mathrm{数}\mathrm{且}\mathrm{与}\alpha \mathrm{等}\mathrm{势}\}$ 的最小元。证明：$\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

教材 $\mathrm{\S }1$ 命题逻辑

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

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

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

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

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

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

1. 若 $\alpha =(\mathrm{\neg }\beta )$，则 $\mathsf{len}(\alpha )\ge 4$，$\mathsf{len}(\alpha )\notin \{2,3\}$。若 $\mathsf{len}(\alpha )=6$，则 $\mathsf{len}(\beta )=3$，与 $P(\beta )$ 矛盾；
2. 若 $\alpha =(\beta ◻\gamma )$（其中 $◻\in \{\vee ,\wedge ,\to ,\leftrightarrow \}$），显然 $\mathsf{len}(\alpha )=\mathsf{len}(\beta )+\mathsf{len}(\gamma )+3>5$。若 $\mathsf{len}(\alpha )=6$ 则 $\mathsf{len}(\beta )+\mathsf{len}(\gamma )=3$，与 $P(\beta )$ 或 $P(\gamma )$ 矛盾。

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

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

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

$$\begin{gathered} \mathsf{len}(A_n)=1\text{ \\ len((¬α))=len(α)+3 \\ len((α◻An))=len(α)+4} \end{gathered}$$

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

$Q.E.D.$

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

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

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

若当 $c\le n(n\ge 1)$ 时都有 $P(c)$ 成立。则当 $c=n+1$ 时，$\alpha =(\beta ◻\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.$

教材 $\mathrm{\S }1.2$ 真值指派

对于命题符号集合 $S$，真值指派 $v$ 是函数：

$$v:S\to \{T,F\}$$

设 $\overline{S}$ 是由 $S$ 通过 5 种公式构造运算得到的合式公式的集合，我们将 $v$ 扩展到 $\overline{v}$：

$$\overline{v}:\overline{S}\to \{T,F\}$$

我们称真值指派 $v$ 满足 $\phi$，当且仅当 $\overline{v}(\phi )=T$。

重言蕴含：$\mathrm{\Sigma }\models \tau$ 当且仅当满足 $\mathrm{\Sigma }$ 中每个合式公式的真值指派也满足 $\tau$。$\{\sigma \}\models \tau$ 也记为 $\sigma \models \tau$。

重言式： $\mathrm{\varnothing }\models \tau$ 也记为 $\models \tau$。

重言等价：$\sigma \models \tau$ 并且 $\tau \models \sigma$，记为 $\sigma \models =|\tau$。

紧致性定理：设 $\mathrm{\Sigma }$ 是合式公式的无限集合，如果对于 $\mathrm{\Sigma }$ 中的任意有限子集 ${\mathrm{\Sigma }}_0$，都存在一个真值指派满足 ${\mathrm{\Sigma }}_0$ 中的每个合式公式，那么，就存在一个真值指派满足 $\mathrm{\Sigma }$ 的所有合式公式（即，如果 $\mathrm{\Sigma }$ 的任意有限子集可满足，则 $\mathrm{\Sigma }$ 可满足）。

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

证明：设 $⟨{\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_n⟩$ 是 $\alpha$ 的构造序列。

$$\begin{gathered} \mathrm{\forall }A\in \alpha .v_1(A)=v_2(A)\text{ \\ ⇒v1(ε1)=v2(ε1) \\ ⇒∀k≤n.v1―(⟨ε1,ε2,…,εk⟩)=v2―(⟨ε1,ε2,…,εk⟩) \\ ⇒v1―(α)=v2―(α)} \end{gathered}$$

$Q.E.D.$

习题 8：（置换）${\alpha }_1,{\alpha }_2,\dots$ 一个合式公式的序列，对每个合式公式 $\phi$，令 ${\phi }^{\ast }$ 是用 ${\alpha }_n$ 置换 $A_n$（对所有 $n$）后得到的结果。

（a）设 $v$ 是所有命题符号的真值指派，定义 $u$ 为满足 $u(A_n)=\bar{v}({\alpha }_n)$ 的真值指派，证明 $\bar{u}(\phi )=v({\phi }^{\ast })$ 使用归纳法。

（b）证明如果 $\phi$ 是重言式，那么 ${\phi }^{\ast }$ 也是。（例如，$((A\wedge B)\leftrightarrow (B\wedge A))$ 是一个重言式，因此对任意的合式公式 $\alpha ,\beta$，通过置换可得 $((\alpha \wedge \beta )\leftrightarrow (\beta \wedge \alpha ))$ 是重言式）

（a）证明：命题 $P(k):\phi \mathrm{构}\mathrm{造}\mathrm{序}\mathrm{列}\mathrm{长}\mathrm{度}\mathrm{为}k\mathrm{时}，\bar{u}(\phi )=v({\phi }^{\ast })$。设 $\phi$ 的构造序列为 $⟨{\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_k⟩$。对 $k$ 进行归纳：

当 $k=1$ 时，${\epsilon }_1$ 为命题符号，命题 $P(1)$ 成立。

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

则当 $k=n$ 时，$u({\epsilon }_n)=v({\epsilon }_n)$，因此 $\bar{u}(⟨{\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_n⟩)=\bar{v}(⟨{\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_n⟩)$。

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

$Q.E.D.$

（b）证明：若 $\phi$ 是重言式。对任意真值指派 $v$，$\bar{v}({\phi }^{\ast })=\bar{u}(\phi )=T$。因此 ${\phi }^{\ast }$ 为重言式。

$Q.E.D.$

教材 $\mathrm{\S }1.3$ 解析算法

习题 3（不考）：证明引理 13B 中关于运算 ${\epsilon }_{\mathrm{\neg }}$ 的情形。

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

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

下面验证 $S$ 在 ${\epsilon }_{\mathrm{\neg }}$ 下是封闭的。考虑 $S$ 中的 $\alpha$，$(\mathrm{\neg }\alpha )$ 的真初始段如下：

1. $($
2. $(\mathrm{\neg }$
3. $(\mathrm{\neg }{\alpha }_0$，其中 ${\alpha }_0$ 是 $\alpha$ 的真初始段
4. $(\mathrm{\neg }\alpha$

显然，${\alpha }_0\in S$。原命题显然正确。

$Q.E.D.$

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

$$((A\wedge (\mathrm{\neg }B))\to (C\vee D))$$

我们写成：

$$((A\wedge (\mathrm{\neg }B\to (C\vee D$$

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

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

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

1. 对 $e$ 中出现的每个串 $\alpha ，\beta$，若 $\alpha ,\beta \in S$，执行替换：$$\begin{gathered} (\mathrm{\neg }\alpha \to (\mathrm{\neg }\alpha )\text{ \\ (α∧β→(α∧β) \\ (α∨β→(α∨β) \\ } \end{gathered}$$
2. 重复步骤 1，直到无法执行替换。

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

$Q.E.D.$

直观上，上述算法每次迭代时把一个或两个短的合式公式变成一个更长的合式公式，直到包含所有的命题符号，整个公式称为一个合式公式。

教材 $\mathrm{\S }1.4$ 归纳与递归

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

$C_n$ 是长度为 $n$ 的构造序列的最后一个元素 $x$ 的集合，$C_1=B$。

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

$\mathsf{size}(C_1)=2,\mathsf{size}(C_2)=6$

枚举 $C_3$ 中的元素：

$$\begin{gathered} C_3=\{a,b,g(a),g(b),f(a,a),f(b,b),\text{ \\ g(g(a)),g(f(a,a)),g(g(b)),g(f(b,b)), \\ f(a,b),f(b,a),f(a,g(a)),f(g(a),a),f(g(a),g(a)), \\ f(a,f(a,a)),f(f(a,a),a),f(f(a,a),f(a,a)) \\ f(b,g(b)),f(g(b),b),f(g(b),g(b)), \\ f(b,f(b,b)),f(f(b,b),b),f(f(b,b),f(b,b)) \\ }} \end{gathered}$$

因此，$\mathsf{size}(C_3)=24$ 。同理，$\mathsf{size}(C_4)=144$。

陆老师原话：“数字不重要，你把前两个写出来就行了，后面的太难了”。

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

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

“自顶向下”的 $C^{\ast }$ 的扩展定义：

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

证明 $C^{\ast }=C_{\ast }$：

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

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

$$\bigcup _n{C}_n=C_{\ast }=C^{\ast }=\bigcap \{S|S\mathrm{是}\mathrm{归}\mathrm{纳}\mathrm{的}\}$$

$Q.E.D.$

这种题考场会出吗？根本不认得符号 😭

教材 $\mathrm{\S }1.5$ 命题连接词

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

$$\begin{gathered} G(F,F,F)=F,G(T,F,F)=T,\text{ \\ 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.} \end{gathered}$$

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

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

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

构造析取范式：

$$G(A,B,C)=(A\wedge \mathrm{\neg }B\wedge \mathrm{\neg }C)\vee (\mathrm{\neg }A\wedge B\wedge \mathrm{\neg }C)\vee (\mathrm{\neg }A\wedge \mathrm{\neg }B\wedge C)$$

（b）将上述函数简化：

$$\begin{gathered} G(A,B,C)=(A\wedge \mathrm{\neg }(B\vee C))\vee (\mathrm{\neg }A\wedge (B+C))\text{ \\ =((B∨C)<A)∨(A<(B+C))} \end{gathered}$$

思路：应用 $A\wedge \mathrm{\neg }B=B<A$ 来减少连接个数。

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

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

令 $\alpha$ 是任意只包含 $A,B$ 的公式，只要证明在 $\overline{v}(\alpha )$ 下的四种可能取值中有偶数个为 $T$。

合式公式 $A$ 和 $B$ 显然只有偶数个 $T$。若合式公式 $\alpha ,\beta$ 有偶数个 $T$，则合式公式 $\mathrm{\neg }\alpha$ 和 $\alpha \leftrightarrow \beta$ 也有偶数个 $T$​。

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

$Q.E.D.$

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

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

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

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

$Q.E.D.$

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

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

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

$$v(A)=\{\begin{array}{ll}T& \text{iff }A\in \mathrm{\Delta },\\ F& \text{iff }A\notin \mathrm{\Delta }\end{array}$$

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

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

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

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

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

则对于构造序列长度为 $n$ 的合式公式 $\phi$，设其构造序列为 $⟨{\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_n⟩$。

1. 若 $\phi =(\mathrm{\neg }\alpha )$，$\overline{v}(\mathrm{\neg }\alpha )=T⟺\overline{v}(\alpha )=F⟺\alpha \notin \mathrm{\Delta }⟺(\mathrm{\neg }\alpha )\in \mathrm{\Delta }$，原命题对 $\phi$ 显然成立；
2. 若 $\phi =(\alpha \wedge \beta )$，$\overline{v}(\alpha \wedge \beta )=T⟺\overline{v}(\alpha )=T\wedge \overline{v}(\beta )=T⟺\alpha \in \mathrm{\Delta }\wedge \beta \in \mathrm{\Delta }$。由条件 2 可知，$\mathrm{\Delta }$ 对 $\wedge$ 封闭。因此 $\alpha \in \mathrm{\Delta }\wedge \beta \in \mathrm{\Delta }⟺\alpha \wedge \beta \in \mathrm{\Delta }$。原命题对 $\phi$ 成立。
3. 若 $\phi =(\alpha \vee \beta )$，可转化为 $\phi =\mathrm{\neg }(\mathrm{\neg }\alpha \wedge \mathrm{\neg }\beta )$。根据 1 和 2 归纳即可。

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

$Q.E.D.$

教材 $\mathrm{\S }2$ 一阶逻辑

教材 $\mathrm{\S }2.1$ 一阶语言

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

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

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

$$P{t}_1{t}_2\dots t_n$$

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

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

句子是没有自由变量的合式公式。

概念辨析

特点	公式（Formula）	句子（Sentence）
是否含自由变量	可能含有自由变量	不含自由变量
可判定性	不能直接判定，需要赋值	可以直接判定真值
作用	描述性质或关系，通常作为表达式的一部分	完整断言，可以作为公理或定理
示例	$P(x)\to Q(y)$	$\mathrm{\forall }x(P(x)\to Q(x))$

我们会尽量使用如下字母表：

• 谓词符号：大写斜体的字母和 $\in ,<$；
• 变量：$v_i,u,v,x,y,z$；
• 函数符号：$f,g,h,S,+$ 等；
• 常数符号：$a,b,\dots ,0$；
• 项：$u,t$；
• 公式：小写希腊字母；
• 句子：$\sigma ,\tau$；
• 公式集：大写希腊字母和特定的斜体字母（看作是希腊字母）即 $A(\alpha ),T(\tau )$；
• 结构 $\mathrm{\S }2.2$，大写德文字母。

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

教材 $\mathrm{\S }2.2$ 真值与模型

一阶语言的结构 $\mathfrak{A}$ 是一个函数，把一些语法上的符号映射到有实际意义的元素。

形式上，一阶语言的一个结构是一个函数，其定义域为参数的集合，且满足以下条件：

1. 全称量词 $\mathrm{\forall }$：指派一个非空集合 $|\mathfrak{A}|$，称为 $\mathfrak{A}$ 的论域（universe）（或者定义域（domain））。
2. n 元谓词符号 $P$：指派一个 n 元关系，$ P^\A \subseteq |\A|^n $，即 $P^{\mathfrak{A}}$ 是 P 上一个 n 元组的集合。
3. 常数符号 $c$：指派一个论域 $|\mathfrak{A}|$ 中的元素 $c^{\mathfrak{A}}$。
4. n 元函数符号 $f$：指派一个 $|\mathfrak{A}|$ 上的 n 元运算 $f^{\mathfrak{A}}$，即 $f^{\mathfrak{A}}:|\mathfrak{A}{|}^n\to |\mathfrak{A}|$。

例如，数论结构（$\mathrm{\S }3$） $\mathfrak{A}=(\mathbb{N};\mathbf{0},\mathbf{S},<,+,\cdot ,E)$。其中 $|\mathfrak{A}|=\mathbb{N}$。

若句子 $\sigma$ 在 $\mathfrak{A}$ 中为真，则称 $\mathfrak{A}$ 是 $\sigma$ 的一个模型，记为 ${\models }_{\mathfrak{A}}\sigma$。注意，中文版教材中将该公式写成了 $\models \mathfrak{A}\sigma$，这是错误的。

对于结构 $\mathfrak{A}$，函数 $s:V\to |\mathfrak{A}|$ 满足合式公式 $\phi$ 记为 ${\models }_{\mathfrak{A}}\phi [s]$。这一定义可以扩充到项：$s:T\to |\mathfrak{A}|$，含义相似，下图是一个一元函数的交换图（commutative graph）。

$$\begin{array}{ccc}T& \stackrel{\overline{s}}{\to }& |\mathfrak{A}|\\ {\mathcal{F}}_f\downarrow & \downarrow f^{\mathfrak{A}}\\ T& \stackrel{\overline{s}}{\to }& |\mathfrak{A}|\end{array}$$

一阶逻辑中全程量词的语义解释：对于合式公式 $\phi$，${\models }_{\mathfrak{A}}\mathrm{\forall }x\phi [s]$ 当且仅当对每个 $\mathrm{\forall }d\in |\mathfrak{A}|.{\models }_{\mathfrak{A}}\phi [s(x|d)]$。其中 $s(x|d)$ 是一个函数，其取值在变量 $x$ 处为 $d$，其他曲直与 $s$ 相同。这一定义相当于把全称量词 $\mathrm{\forall }$ 从 ${\models }_{\mathfrak{A}}$ 右侧转移到了左侧，常用于证明带全称量词的命题。

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

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

$$\begin{gathered} {\models }_{\mathfrak{A}}\mathrm{\forall }x((\alpha \to \beta )\wedge \alpha )[s]\text{ \\ ⟺∀d∈A.⊨A((α→β)∧α)[s(x|d)] \\ ⟺∀d∈A.⊨A(β∧α)[s(x|d)] \\ ⟺⊨A∀x(β∧α)[s] \\ ⟺⊨A∀x(β)[s]∧⊨A∀x(α)[s] \\ } \end{gathered}$$

$Q.E.D.$

教材 $\mathrm{\S }2.2.1$ 逻辑蕴涵

合式公式集合 $\mathrm{\Gamma }$ 逻辑蕴含合式公式 $\phi$ 记作 $\mathrm{\Gamma }\models \phi$，当且仅当对语言中的每个结构 $\mathfrak{A}$ 和每个函数 $s:V\to |\mathfrak{A}|$，使得 $\mathfrak{A}$ 以 $s$ 满足 $\mathrm{\Gamma }$ 的每个元素时，也满足 $\phi$。

$\models$ 在命题逻辑中（$\mathrm{\S }1.2$）表示重言蕴含，在一阶语言中表示逻辑蕴含。逻辑蕴涵的其他记法与重言蕴含相似，不再赘述。

下面这段话来自教材，对我们理解定义非常重要：

逻辑蕴涵的定义与第 1 章中的重言蕴涵非常相似，但是其复杂性却大大不同。在命题逻辑中想要判定一个合式公式是否是重言式，只需要考虑有限个真值指派，其中每一个都是有限函数。对每个真值指派，只要计算 $\overline{v}(\alpha )$，这可以在有限长的时间内完成。（如前所述，重言式的集合是可以判定的）

与之相反，如果要判定一阶语言中的合式公式是否恒真，则需要考虑每一个结构 $\mathfrak{A}$。（特别地，这需要使用每个非空集合，而每个集合都有很多元素）对于每个结构，还要考虑每个从变量集合 $V$ 到 $|\mathfrak{A}|$ 的函数 $s$。并且对每一个给定的结构 $\mathfrak{A}$ 和 $s$，还需要判定 $\mathfrak{A}$ 是否以 $s$ 满足 $\phi$。如果 $|\mathfrak{A}|$ 是无限的，其本身就是一个非常复杂的概念。

考虑到这些复杂性，恒真公式集的无法判定性就不足为怪了（$\mathrm{\S }3.5$）。奇怪的是，可以证明恒真性的概念与另外一个概念（可推导性）是等价的，这个概念更接近有限性（$\mathrm{\S }2.4$）。利用这个等价，在某些推理假设下，可以证明恒真集（恒真合式公式的集合）事实上是可数的。由这个可数的性质可以得到恒真公式集的一个更具体的特性。

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

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

$$\begin{gathered} {\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]⟺\mathrm{\forall }d\in |\mathfrak{A}|.{\models }_{\mathfrak{A}}\alpha [s(x|d)]\text{ \\ ⟺⊨Aα[s] \\ } \end{gathered}$$

$Q.E.D.$

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

（a）$|\mathfrak{A}|$ 中恰好有两个元素

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

$$\mathrm{\exists }x\mathrm{\exists }yx\ne y\wedge (\mathrm{\forall }zy=z\vee x=z)$$

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

教材 $\mathrm{\S }2.2.2$ 可定义性

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

（a）$\{0\}$

（b）$\{1\}$

（c）$\{⟨m,n⟩|n\mathrm{是}\mathbb{N}\mathrm{中}m\mathrm{的}\mathrm{后}\mathrm{继}\}$

（d）$\{⟨m,n⟩|\mathrm{在}\mathbb{N}\mathrm{中}m<n\}$

（a）$\mathrm{\forall }xy\cdot x=y$

（b）$\mathrm{\forall }xy\cdot x=x$

（c）$\mathrm{\exists }x(n=m+x\wedge \mathrm{\forall }yx\cdot y=y)$ 即 $n=m+1$

（d）$\mathrm{\exists }x(n=m+x\wedge \mathrm{\exists }yx\cdot y\ne x)$ 即 $n=m+x\wedge x\ne 0$

习题 13（不考）：证明同态定理的（a）。

设 $h$ 是从 $\mathfrak{A}$ 到 $\mathfrak{B}$ 中的同态，$s$ 将变量的集合映射到 $|\mathfrak{A}|$ 中。

（a）对每个项 $t$，我们有 $h(\bar{s}(t))=\overline{h\circ s}(t)$，其中 $\bar{s}(t)$ 是在 $\mathfrak{A}$ 中计算的，而 $\overline{h\circ s}(t)$ 是在 $\mathfrak{B}$ 中计算的；

影印版教材中同态定理的横线印刷不清晰，本题中的表述是正确的。

证明：对于常量 $c$，$h(\bar{s}(c))=h(c^{\mathfrak{A}})=c^{\mathfrak{B}}=\overline{h\circ s}(c)$；

对于变量 $x$，$h(\bar{s}(t))=h(s(x))=h\circ s(x)=\overline{h\circ s}(x)$；

对于 $n$ 元函数函数 $f$，按照归纳，

$$\begin{gathered} h(\bar{s}(f{t}_1\dots t_n))=h(f^{\mathfrak{A}}(\bar{s}(t_1),\dots ,\bar{s}(t_n)))\text{ \\ =fB(h(s―(t1)),…,h(s―(tn))) \\ =fB(h∘s―(t1),…,h∘s―(tn)) \\ =h∘s―(ft1…tn)} \end{gathered}$$

$Q.E.D.$

习题 18：全称公式 (${\mathrm{\forall }}_1$) 是形式为 $\mathrm{\forall }{x}_1\cdots x_n\theta$ 的公式，存在公式 (${\mathrm{\exists }}_1$) 是形式为 $\mathrm{\exists }{x}_1\cdots x_n\theta$ 的公式，其中 $\theta$ 是无量词。设 $\mathfrak{A}$ 是 $\mathfrak{B}$ 的子结构，$ s: V \rightarrow |\A|$。

（a）证明：如果 ${\models }_{\mathfrak{A}}\psi [s]$ 且 $\psi$ 是存在公式，那么 ${\models }_{\mathfrak{B}}\psi [s]$。如果 ${\models }_{\mathfrak{B}}\phi [s]$ 且 $\phi$ 是全称公式，那么 ${\models }_{\mathfrak{A}}\phi [s]$。

说明：（a）的意思是（当 $\phi$ 是句子时）任何全称句子 $\phi$ 在子结构中都可以保持。由于全称是语法性质，其必定与符号串相关。反过来，在子结构中保持则是语义性质，其必定与结构相关。但是这一语义性质保持了逻辑等价的语法性质（这正是我们所需要的）。即，如果句子 $\sigma$ 在子结构中总是成立，那么 $\sigma$ 逻辑等价于全称句子（这一点要归功于洛斯和塔斯基）。

证明：本题的证明过程要用到一阶逻辑的全称量词语义解释，以及与之相似的一阶逻辑的存在量词语义解释。后者并没有在教材中提到。

我们假设 $\vDash_{\B} \forall x_{1} \dots \forall x_{n} \theta [s] $，于是对于每个 $d_1,\dots ,d_n\in |\mathfrak{B}|$，${\models }_{\mathfrak{B}}\theta [s(x_i|d_i{)}_{i=1}^n]$。

这意味着，对于每个 $d_1,\dots ,d_n\in |\mathfrak{A}|$，${\models }_{\mathfrak{B}}\theta [s(x_i|d_i{)}_{i=1}^n]$。因此，对每个 $d_1,\dots ,d_n\in |\mathfrak{A}|$，${\models }_{\mathfrak{A}}\theta [s(x_i|d_i{)}_{i=1}^n]$。等价地，${\models }_{\mathfrak{A}}\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_n\theta [s]$。

用同样的证明方法，我们假设 ${\models }_{\mathfrak{A}}\mathrm{\exists }{x}_1\dots \mathrm{\exists }{x}_n\theta [s]$，则存在 $d_1,\dots ,d_n\in |\mathfrak{A}|$，${\models }_{\mathfrak{A}}\theta [s(x_i|d_i{)}_{i=1}^n]$。进而存在 $d_1,\dots ,d_n\in |\mathfrak{B}|$，${\models }_{\mathfrak{B}}\theta [s(x_i|d_i{)}_{i=1}^n]$。可推出 ${\models }_{\mathfrak{B}}\mathrm{\exists }{x}_1\dots \mathrm{\exists }{x}_n\theta [s]$。

$Q.E.D.$

习题 20：设语言有等号和二元谓词符号 $P$。考虑两个结构 $(\mathbb{N},<),(\mathbb{R},<)$。

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

直观来说，$(\mathbb{N},<)$ 中存在“相邻”的两个数而 $(\mathbb{R},<)$ 中不存在。“相邻”可以被形式化描述为“这两个数之间没有其他的数”。我们使用公式来表达这一性质：

$$\mathrm{\forall }x\mathrm{\exists }y(x<y\wedge \mathrm{\forall }z(\mathrm{\neg }(x<z\wedge z<y)))$$

习题 22：设 $\mathfrak{A}$ 是结构且 $h$ 是函数，$\text{ran}h=|\mathfrak{A}|$。证明存在结构 $\mathfrak{B}$ 使得 $h$ 是一个从 $\mathfrak{B}$ 到 $\mathfrak{A}$ 上的同态。提示：取 $|\mathfrak{B}|=\text{dom}h$。一般地，需要使用选择公理在 $\mathfrak{B}$ 中定义函数，除非 $h$ 是一对一的。

证明：取 $|\mathfrak{B}|=\text{ran}h$，则 $h:|\mathfrak{B}|\to |\mathfrak{A}|$ 是满射。对每个 $a\in \mathfrak{A}$，使用选择公理定义 $G(a)=\{b\in |\mathfrak{B}|\mid h(b)=a\}$，定义 $g(a)$ 为 $G(a)$ 中的任意一个元素（例如，某个全序下的最小元素）。接下来，我们可以根据对同态的定义构造 $\mathfrak{B}$ 中的谓词参数、常数符号函数符号对应的元素：

$$\begin{gathered} ⟨b_1,\dots ,b_n⟩\in P^{\mathfrak{B}}⟺⟨h(b_1),\dots ,h(b_n)⟩\in P^{\mathfrak{A}}\text{ \\ cB=g(cA) \\ fB(b1,…,bn)=g(fA(h(b1),…,h(bn)))} \end{gathered}$$

以上定义的 $\mathfrak{B}$ 显然使得 $h$ 为同态。

$Q.E.D.$

教材 $\mathrm{\S }2.3$ 解析算法

项是通过符号函数对变量和常数的运算得到的。定义符号函数 $K$，使得对符号 $s$，$K(s)=1-n$，其中 $n$ 是项的个数。

$$\begin{gathered} K(x)=1-0=1,\text{ 对变量 }x;\text{ \\ K(c)=1−0=1, 对常数符号 c; \\ K(f)=1−n, 对 n 元函数符号 f} \end{gathered}$$

通过如下方式将 $K$ 扩充到表达式的集合

$$K(s_1{s}_2\cdots s_n)=K(s_1)+K(s_2)+\cdots +K(s_n).$$

习题 1：对于合式公式 $\alpha$ 的任意真的初始段 ${\alpha }^{\prime }$，$K(\alpha )<1$。

证明：对波兰记法下的 $\alpha$ 使用归纳法。

1. 若 $\alpha =(\mathrm{\neg }\beta )$，有以下几种情况：
   • ${\alpha }^{\prime }=($，$K({\alpha }^{\prime })=-1$
   • ${\alpha }^{\prime }=(\mathrm{\neg }$，$K({\alpha }^{\prime })=0$
   • ${\alpha }^{\prime }=(\mathrm{\neg }{\beta }^{\prime }$，$K({\alpha }^{\prime })\le -1$
   • ${\alpha }^{\prime }=(\mathrm{\neg }\beta$，$K({\alpha }^{\prime })=-1$
2. 若 $\alpha =(\beta \wedge \gamma )$，有以下几种情况：
   • ${\alpha }^{\prime }=($，$K({\alpha }^{\prime })=-1$
   • ${\alpha }^{\prime }=({\beta }^{\prime }$，$K({\alpha }^{\prime })\le -1$
   • ${\alpha }^{\prime }=(\beta$，$K({\alpha }^{\prime })=0$
   • ${\alpha }^{\prime }=(\beta \wedge$，$K({\alpha }^{\prime })=-1$
   • ${\alpha }^{\prime }=(\beta \wedge {\gamma }^{\prime }$，$K({\alpha }^{\prime })\le -1$
   • ${\alpha }^{\prime }=(\beta \wedge \gamma$，$K({\alpha }^{\prime })\le 0$

因此，总有 $K({\alpha }^{\prime })\le 0$。

$Q.E.D.$

习题 2：设 $\epsilon$ 是包含变量、常数符号和函数符号的表达式。证明：$\epsilon$ 是项当且仅当 $K(\epsilon )=1$ 且对 $\epsilon$ 的任意终段 ${\epsilon }^{\prime }$，我们有 $K({\epsilon }^{\prime })>0$。提示：证明更强一些的结果：如果对 $\epsilon$ 的任意终段 ${\epsilon }^{\prime }$，$K({\epsilon }^{\prime })>0$，那么 $\epsilon$ 是 $K(\epsilon )$ 个项的连接。

证明：先证充分性。由引理 23A，$K(\epsilon )=1$。由引理 23B，对 $\epsilon$ 的任意终段 ${\epsilon }^{\prime }$，我们有 $K({\epsilon }^{\prime })>0$。

再证必要性。

对 $\epsilon$ 归纳。若 $\epsilon$ 长度为 1，则为变量或常数符号，命题显然成立。

若 $\epsilon$ 长度超过 1，由 $K(\epsilon )=1$ 且对 $\epsilon$ 的任意终段 ${\epsilon }^{\prime }$，$K({\epsilon }^{\prime })>0$，可知必然存在至少一个 $n$ 元函数符号 $f$。

若只存在一个 $n$ 元函数符号 $f$，则由 $K(\epsilon )=1$ 知 $\epsilon$ 中必然存在 $n$ 个变量或常数符号，由 $K({\epsilon }^{\prime })\ge 1$ 知这些变量符号必然都出现在 $\epsilon$ 右端。命题成立。

对 $\epsilon$ 中函数符号的个数归纳，由 $K(\epsilon )=1$ 且对 $\epsilon$ 的任意终段 ${\epsilon }^{\prime }$，$K({\epsilon }^{\prime })>0$，可知 $\epsilon$ 必然以 $n$ 元函数符号开始，且函数符号后恰好有 $n$ 项。

$Q.E.D.$

教材 $\mathrm{\S }2.4$ 演绎计算

教材 $\mathrm{\S }2.4.1$ 形式演绎

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

$$\frac{\alpha ,\alpha \to \beta }{\beta }$$

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

1. 重言式；
2. 去掉全称量词：$\mathrm{\forall }x\alpha \to {\alpha }_t^x$，其中 $t$ 是 $x$ 在 $\alpha$ 中的替换，即把 $\alpha$ 中出现的 $x$ 换成 $t$；
3. 全称量词右移：$\mathrm{\forall }x(\alpha \to \beta )\to (\mathrm{\forall }x\alpha \to \mathrm{\forall }x\beta )$；
4. 添加全称量词：$\alpha \to \mathrm{\forall }x\alpha$，其中 $x$ 在 $\alpha$ 中不是自由出现的（自由出现的意思是无量词限定，例如 $\mathrm{\forall }yx+y=2$ 中 $x$ 是自由出现的，$y$ 不是）；
5. $x=x$；
6. $x=y\to (\alpha \to {\alpha }^{\prime })$，其中 $\alpha$ 是原子的，${\alpha }^{\prime }$ 是有限次的将 $\alpha$ 中的 $x$ 替换为 $y$ 得到的。

教材 $\mathrm{\S }2.4.2$ 替换

对原子公式 $\alpha$，${\alpha }_t^x$ 是将 $\alpha$ 中自由出现的变量 $x$ 都替换为 $t$ 所得到的表达式。

$$(\mathrm{\forall }y\alpha {)}_t^x=\{\begin{array}{c}\mathrm{\forall }y\alpha \text{ if }x=y\\ \mathrm{\forall }y({\alpha }_t^x)\text{ if }x\ne y\end{array}$$

上述定义的含义为，如果待替换的变量不是自由出现的，例如被全称量词限定的 $y$，则不执行替换。

教材 $\mathrm{\S }2.4.4$ 演绎与元定理

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

概化定理（添加全称量词）：如果 $\mathrm{\Gamma }⊢\phi$ 且 $x$ 不在 $\mathrm{\Gamma }$ 的任何公式中自由出现，则 $\mathrm{\Gamma }⊢\mathrm{\forall }x\phi$。

规则 T：如果 $\mathrm{\Gamma }⊢{\alpha }_1,\dots ,\mathrm{\Gamma }⊢{\alpha }_n$，且 $\{{\alpha }_1,\dots ,{\alpha }_n\}$ 重言蕴含 $\beta$ ，那么 $\mathrm{\Gamma }⊢\beta$。

演绎定理：如果 $\mathrm{\Gamma };\gamma ⊢\phi$，那么 $\mathrm{\Gamma }⊢(\gamma \to \phi )$。从右到左叫做演绎，从左到右叫演绎定理。

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

$$v(\alpha )=T⟺{\models }_{\mathfrak{A}}\alpha [s]$$

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

$$\bar{v}(\alpha )=T⟺{\models }_{\mathfrak{A}}\alpha [s]$$

（b）证明：如果 $\mathrm{\Gamma }$ 重言蕴含 $\phi$，则 $\mathrm{\Gamma }$ 逻辑蕴涵 $\phi$。

（a）证明：使用归纳法证明。对于基本公式 $\alpha$，$\bar{v}(\alpha )=v(\alpha )=T⟺{\models }_{\mathfrak{A}}\alpha [s]$。

对于公式 $\mathrm{\neg }\alpha$，$\bar{v}(\alpha )=T⟺\bar{v}(\alpha )=F⟺\mathrm{not}{\models }_{\mathfrak{A}}\alpha [s]⟺{\models }_{\mathfrak{A}}\mathrm{\neg }\alpha [s]$。

对于公式 $\beta \to \alpha$，$\bar{v}(\beta \to \alpha )=T⟺\bar{v}(\beta )=F\vee \bar{v}(\alpha )=T⟺{\models }_{\mathfrak{A}}\mathrm{\neg }\beta [s]\vee {\models }_{\mathfrak{A}}\alpha [s]⟺\models \beta \to \alpha [s]$。

$Q.E.D.$

（b）证明：$\mathrm{\Gamma }$ 重言蕴含 $\phi$，意味着对每个结构 $\mathfrak{A}$，若对于每个 $\alpha \in \mathrm{\Gamma }$，$\bar{v}(\alpha )=T$，有 $\bar{v}(\phi )=T$。

因此，对每个结构 $\mathfrak{A}$ 和 $s:V\to |\mathfrak{A}|$，若对每个 $\alpha \in \mathrm{\Gamma }$，都有 ${\models }_{\mathfrak{A}}\alpha [s]$，则 ${\models }_{\mathfrak{A}}\phi [s]$。因此，$\mathrm{\Gamma }\models \phi$。

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

$Q.E.D.$

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

$$⊢(\alpha \to \mathrm{\exists }x\beta )\leftrightarrow \mathrm{\exists }x(\alpha \to \beta )$$

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

$$⊢(\mathrm{\forall }x\beta \to \alpha )\leftrightarrow \mathrm{\exists }x(\beta \to \alpha )$$

TODO：回头再看。

证明 Q2b：由规则 T，需要证明 $⊢(\alpha \to \mathrm{\exists }x\beta )\to \mathrm{\exists }x(\alpha \to \beta )$ 和 $⊢(\alpha \to \mathrm{\exists }x\beta )\leftarrow \mathrm{\exists }x(\alpha \to \beta )$。

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

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

通过将 $\mathrm{\neg }\alpha$ 替换为 $\alpha$ ，将 $\mathrm{\neg }\beta$ 替换为 $\beta $，并使用反证法的重言式等价性，我们得到 $⊢(\mathrm{\forall }x\beta \to \alpha )\leftrightarrow \mathrm{\exists }x(\beta \to \alpha )$。

$Q.E.D.$

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

（b）证明：如果 $y$ 不在 $\phi$ 中出现，那么在 ${\phi }_y^x$ 和 $({\phi }_y^x{)}_x^y=\phi$ 中 $x$ 可替换 $y$。提示：对 $y$ 使用归纳法。

本题中证明会使用替换的定义（4）

（a）证明：如果 $\phi =\mathrm{\forall }yx$，则 $({\phi }_y^x{)}_x^y=\mathrm{\forall }yy$，此时 $x$ 在 $({\phi }_y^x{)}_x^y$ 中同样的位置上不出现。

如果 $\phi =\mathrm{\forall }xy$，则 $({\phi }_y^x{)}_x^y=\mathrm{\forall }xx$，此时 $x$ 在 $\phi$ 中同样的位置上不出现。

$Q.E.D.$

TODO：再看看（b）

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

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

$Q.E.D.$

习题 11：证明 Eq3：

$$⊢\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(x=y\to y=z\to x=z)$$

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

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

$Q.E.D.$

另一种基于命题逻辑（而不是一阶逻辑）的证明：

$$\begin{gathered} ⊢\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(x=y\to y=z\to x=z)\text{ \\ ⟺⊢∀x∀y∀z(x≠y∨(y≠z∨x=z)) \\ ⟺⊢∀x∀y∀z(x≠y∨¬(y=z∧x≠z)) \\ ⟺⊢∀x∀y∀z¬(x=y∧y=z∧x≠z)} \end{gathered}$$

其中 $\ne$ 就是 $=$ 的否定。由于相等关系（或者逻辑上的相等）的传递性，$\mathrm{\neg }(x=y\wedge y=z\wedge x\ne z)$ 为重言式。

$Q.E.D.$

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

可靠性定理：如果 $\mathrm{\Gamma }⊢\phi$，那么 $\mathrm{\Gamma }\models \phi$。

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

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

1. 如果 $\mathrm{\Gamma }\models \phi$，那么 $\mathrm{\Gamma }⊢\phi$。
2. 任意和谐的公式集都是可满足的。

紧致性定理：

1. 如果 $\mathrm{\Gamma }⊢\phi$，那么存在某个有限的 ${\mathrm{\Gamma }}_0\subseteq \mathrm{\Gamma }$，有 ${\mathrm{\Gamma }}_0⊢\phi$。
2. 如果 $\mathrm{\Gamma }$ 的每个有限子集 ${\mathrm{\Gamma }}_0$ 都是可满足的，那么 $\mathrm{\Gamma }$ 是可满足的。特别地，句子集 $\mathrm{\Sigma }$ 有模型当且仅当其每个有限子集有模型。

可枚举定理：

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

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

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

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

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

证明：$\mathrm{\Gamma };{\phi }_c^x\models \psi ⟺$ 对任意 $\mathfrak{A}$ 和 $s$，如果 ${\models }_{\mathfrak{A}}\mathrm{\Gamma }[s]$ 且 ${\models }_{\mathfrak{A}}{\phi }_c^x[s]$，则 ${\models }_{\mathfrak{A}}\psi [s]$；

$⟺$ 对任意 $\mathfrak{A}$ 和 $s$，如果 ${\models }_{\mathfrak{A}}\mathrm{\Gamma }[s]$ 且 ${\models }_{\mathfrak{A}}\phi [s(x\mid c^{\mathfrak{A}})]$，则 ${\models }_{\mathfrak{A}}\psi [s]$；

$⟺$ 对任意 $\mathfrak{A}$ 和 $s$，如果 ${\models }_{\mathfrak{A}}\mathrm{\Gamma }[s]$ 且 ${\models }_{\mathfrak{A}}\mathrm{\exists }x\phi$，则 ${\models }_{\mathfrak{A}}\psi [s]$；

$⟺\mathrm{\Gamma };\mathrm{\exists }x\phi \models \psi$；

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

$Q.E.D.$

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

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

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

先证充分性。若（a）成立。若 $\mathrm{\Gamma }$ 不可满足，则 $\mathrm{\Gamma }\models \{\varphi ,\mathrm{\neg }\varphi \}$，因此 $\mathrm{\Gamma }⊢\{\varphi ,\mathrm{\neg }\varphi \}$，即 $\mathrm{\Gamma }$ 不和谐。推出（b）的逆否命题。

再证必要性。若（b）成立。若 $\mathrm{\Gamma }\models \varphi$，则对任意 $\mathfrak{A},s$，${\models }_{\mathfrak{A}}\mathrm{\Gamma }[s]⟹{\models }_{\mathfrak{A}}\varphi [s]$ 即 $\mathrm{not}{\models }_{\mathfrak{A}}\mathrm{\neg }\varphi [s]$。即 $\mathrm{\Gamma };\mathrm{\neg }\varphi$ 是不可满足的，也因此是不和谐的。导出矛盾，因此 $\mathrm{\Gamma }⊢\varphi$。

$Q.E.D.$

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

必然存在不出现 $P$ 的从 $\mathrm{\Gamma }$ 到 $\phi$ 的演绎。

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

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

$Q.E.D.$

习题 4：设 $\mathrm{\Gamma }=\{\mathrm{\neg }\mathrm{\forall }{v}_{1}P{v}_1,P{v}_2,P{v}_3,\dots \}$，$\mathrm{\Gamma }$ 是否和谐？是否可满足？

证明：假设 $\mathfrak{A}=(\{0,1\};P)$，其中 $P^{\mathfrak{A}}=\{⟨1⟩\}$，且构造 $s:V\to |\mathfrak{A}|$ 使得 $\mathrm{\forall }i>0.s(v_i)=1$。于是 ${\models }_{\mathfrak{A}}P{v}_i[s],{\models }_{\mathfrak{A}}P{v}_1[s(v_1|1)]$ 并且 $\mathrm{not}{\models }_{\mathfrak{A}}P{v}_1[s(v_1|0)]$。

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

$Q.E.D.$

教材 $\mathrm{\S }2.6$ 理论的模型

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

$$T\models \sigma \Rightarrow \sigma \in T$$

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

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

$$\mathrm{Th}\mathcal{K}=\{\sigma |\sigma \mathrm{在}\mathcal{K}\mathrm{的}\mathrm{每}\mathrm{个}\mathrm{元}\mathrm{素}\mathrm{中}\mathrm{都}\mathrm{是}\mathrm{真}\mathrm{的}\}$$

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

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

$$\begin{gathered} \mathrm{Cn}\mathrm{\Sigma }=\{\sigma |\mathrm{\Sigma }\models \sigma \}\text{ \\ =ThModΣ} \end{gathered}$$

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

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

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

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

$$(a)\mathrm{\exists }x\mathrm{\exists }y\mathrm{\exists }z[(Pxfx\to Pxx)\vee (Pxy\wedge Pyz\wedge \mathrm{\neg }Pxz)]$$

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

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

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

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

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

$$\begin{gathered} \mathrm{\neg }\mathrm{\exists }x\mathrm{\exists }y\mathrm{\exists }z((Pxfx\to Pxx)\vee (Pxy\wedge Pyz\wedge \mathrm{\neg }Pxz))\text{ \\ ⟺¬∃x∃y∃z[¬(Pxfx→Pxx)→(Pxy∧Pyz∧¬Pxz)] \\ ⟺¬∃x[¬(Pxfx→Pxx)→∃y∃z(Pxy∧Pyz∧¬Pxz] \\ ⟺∀x¬[¬(Pxfx→Pxx)→∃y∃z(Pxy∧Pyz∧¬Pxz)] \\ ⟺∀x[¬(Pxfx→Pxx)∧¬∃y∃z(Pxy∧Pyz∧¬Pxz)] \\ ⟺∀x[Pxfx∧¬Pxx∧∀y∀z(¬Pxy∨¬Pyz∨Pxz)] \\ ⟺∀x[Pxfx∧¬Pxx∧∀y∀z(Pxy→(Pyz→Pxz))]} \end{gathered}$$

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

$$\mathrm{Th}\mathfrak{A}⊢\{Pxfx;\mathrm{\neg }Pxx;\mathrm{\forall }y\mathrm{\forall }z(Pxy\to Pyz\to Pxz)\}$$

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

由子集 $\{Pxfx,\mathrm{\neg }Pxx\}$ 可知，$\mathrm{Th}\mathfrak{A}⊢\{x\ne fx\}$。由 $Pxfx⊢\{Pfxffx,Pffxfffx,\dots \}$。由传递性 $\mathrm{\forall }y\mathrm{\forall }z(Pxy\to Pyz\to Pxz)$ 可知，$\mathrm{Th}\mathfrak{A}⊢\{P{f}^{n}x{f}^{m}x\}$ 对任意 $0\le n<m$ 都成立。因此，$\mathfrak{A}$ 是无限的。

$Q.E.D.$

特别地，$\mathfrak{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 \mathrm{\neg }\sigma \notin T_2\Rightarrow \mathrm{\neg }\sigma \notin T_1\Rightarrow \sigma \in T_1$，又 $T_1\subseteq T_2$，由外延公理，有 $T_1=T_2$。

$Q.E.D.$

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

$$(a)(\mathrm{\exists }xAx\wedge \mathrm{\exists }xBx)\to Cx$$

其前束公式为：

$$\mathrm{\exists }y\mathrm{\exists }z((Ay\wedge Bz)\to Cx)$$

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

提示：应用紧致性定理。

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

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

$Q.E.D.$

“初等等价”的含义是，两个语言或结构满足完全相同的一阶逻辑公式集，在一阶逻辑的层面上“无法区分”。这道题的论证过程还有些问题，Section 2.6: Problem 7 Solution | dbFin 提供了本题的一种证明方式，但笔者认为这种证明方式也并不正确，因为其并没有定义 $\mathfrak{A}$ 与 ${\mathfrak{A}}_n$ 的关系。

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

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

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

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

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

（b）证明：$\sigma$ 是一个可行的 ${\mathrm{\forall }}_2$ 句子，当且仅当 $\mathrm{\neg }\sigma$ 是不可满足的。通过 (a)，我们知道它是可判定的。

教材 $\mathrm{\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$ 的忠实解释来实现。

构造过程：

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$ 关系成立。
2. 定义公式转换：接下来，我们需要定义如何将 $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)$。对于复合公式，按照标准的逻辑运算符的转换规则进行转换。
3. 验证忠实性：最后，我们需要验证这个解释是忠实的，即它保持了 $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$ 公式 $\varphi$ 在 ${\mathfrak{N}}_0$ 中定义（对于空关系结论显而易见）。

考虑 $\pi$ 从 $L_0$ 参数集到 $L_1$ 公式集中的映射，使得 ${\pi }_{\vee }=v_1=v_1$ ，${\pi }_{+}=+v_1{v}_2{v}_3$ 和 ${\pi }_{\cdot }=\cdot v_1{v}_2{v}_3$ 。因为 $\mathrm{\exists }{v}_{1}v=v_1$ ，$\mathrm{\forall }{v}_1\mathrm{\forall }{v}_2\mathrm{\exists }x\mathrm{\forall }{v}_3+v_1{v}_2{v}_3\leftrightarrow v_3=x$ ，以及 $\mathrm{\forall }{v}_1\mathrm{\forall }{v}_2\mathrm{\exists }x\mathrm{\forall }{v}_3\cdot v_1{v}_2{v}_3\leftrightarrow v_3=x$ 在 ${\mathfrak{N}}_1$ 中为真，所以 $\pi$ 是 $\mathfrak{N}$ 的 $L_0$ 到 $\mathrm{Th}{\mathfrak{N}}_1$ 的解释，并且 ${\mathfrak{N}}_1$ 是 $\mathrm{Th}{\mathfrak{N}}_1$ 的模型。

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

$Q.E.D.$

教材 $\mathrm{\S }3$ 不可判定性

本章主要学习三种方法：自代入法、对角线法和可计算法。

教材 $\mathrm{\S }3.0$ 数论

本章涉及到的模型：

$$\begin{gathered} \mathfrak{N}=(\mathbb{N};\mathbf{0},\mathbf{S},<,+,\cdot ,E)\text{ \\ NS=(N;0,S) \\ NL=(N;0,S,<) \\ NA=(N;0,S,<,+) \\ NM=(N;0,S,<,+,⋅)} \end{gathered}$$

定理 30A：设 $A\subseteq \mathrm{Th}\mathfrak{N}$ 是 $\mathfrak{N}$ 中取值为真的句子集，且 $A$ 的哥德尔数集合 $\{\mathrm{♯}\alpha \mid \alpha \in A\}$ 是一个在 $\mathfrak{N}$ 中可定义的集合。则我们可以找到一个在 $\mathfrak{N}$ 中为真的句子 $\sigma$，但 $\sigma$ 不能由 $A$ 推出。

该命题的证明方式是证明哥德尔第一不完备性定理的雏形。本视频推导了证明两个哥德尔不完备定理的过程：【毕导】这个视频里说的都是真的，但你却永远无法证明_哔哩哔哩_bilibili。中文版教材的证明过程中有一些翻译错误，请以本文为准。

证明：命题的证明思路如下：

1. 利用哥德尔数（$\mathrm{\S }3.4$）构造自指句子 $\sigma$；
2. 使用反证法，通过假设推出矛盾以证明假设的反面；
3. 得出结论。

下面是命题证明的详细过程。

我们来构造一个句子 $\sigma$ 来表示 $\sigma$ 本身不是 $A$ 的定理。概括地说，接下去的讨论是这样的：如果 $A⊢\sigma$，那么 $\sigma$ 是假的，这与 $A$ 是取值为真的句子集相矛盾。因此，$\sigma$ 是取值为真的句子，但 $A\mathrm{not}⊢\sigma$。

为了构造 $\sigma$，我们首先考虑这样的一个三元关系 $R$：TODO：从这个定义开始看不懂的。推理在 $\mathrm{\S }3.4$ P168 定义。

$$(a,b,c)\in R\text{iff}a\text{ 是某个公式 }\alpha \text{ 的哥德尔数，}c\text{ 是 }\alpha ({\mathbf{S}}^b\mathbf{0})\text{ 的从 }A\text{ 出发的某个推理上的 }\mathcal{G}\text{ 值}$$

简言之，$(a,b,c)$ 的含义是，哥德尔数为 $a$ 的公式中的 $v_1$ 替换为 $b$，得到的推理的哥德尔数为 $c$。

因为 $\{\mathrm{♯}\alpha \mid \alpha \in A\}$ 在 $\mathfrak{N}$ 中可定义，因此 $R$ 也是可定义的。（这里面的细节要等几节后才能证明）令 $\rho$ 是 $\mathfrak{N}$ 中定义 $R$ 的一个公式，$q$ 为

$$q=\mathrm{♯}(\mathrm{\forall }{v}_3\mathrm{\neg }\rho (v_1,v_1,v_3))$$

（在此，用下列记号：$\phi (t)={\phi }_t^{v_1},\phi (t_1,t_2)=({\phi }_{t_1}^{v_1}{)}_{t_2}^{v_2}$，等等）

下面开始正式构造自指句子 $\sigma$，令

$$\sigma =\mathrm{\forall }{v}_3\mathrm{\neg }\rho ({\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^q\mathbf{0},v_3)$$

则 $\sigma$ 表示任何一个数都不是 $q$ 的从 $A$ 出发的某个推理上的 $\mathcal{G}$ 值，这个推理是将哥德尔数为 $q$ 的公式中的变元 $v_1$ 换成数字 $q$ 后所得到的公式的推理；即任何一个数都不是 $\sigma$ 的推理 $\mathcal{G}$ 的值。这个句子就是毕导视频中提到的 $\mathrm{sub}(n,n,17)$。

下面使用反证法，通过假设推出矛盾以证明假设的反面。

假设和我们期望的结果相反，存在一个从 $A$ 出发的 $\sigma$ 的推论。我们设 $k$ 是这个推理 $\mathcal{G}$ 的值，则 $⟨q,q,k⟩\in R$ 并且

$${\models }_{\mathfrak{N}}\rho ({\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^k\mathbf{0})$$

显然

$$\sigma ⊢\mathrm{\neg }\rho ({\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^k\mathbf{0})$$

并且这两个公式说明 $\sigma$ 在 $\mathfrak{N}$ 中是假的。但 $A⊢\sigma$ 和 $A$ 中的句子在 $\mathfrak{N}$ 中都是真的，这就得到了矛盾。

因此，不存在 $\sigma$ 的从 $A$ 出发的推论。这样对于每个 $k$，我们有 $⟨q,q,k⟩\notin R$。即对于每个 $k$，

$${\models }_{\mathfrak{N}}\mathrm{\neg }\rho ({\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^k\mathbf{0}),$$

由此我们有（使用替换引理）

$${\models }_{\mathfrak{N}}\mathrm{\forall }{v}_3\mathrm{\neg }\rho ({\mathbf{S}}^q\mathbf{0},{\mathbf{S}}^q\mathbf{0},v_3);$$

即，$\sigma$ 在 $\mathfrak{N}$ 中是真的。

大题考点：TODO

1. 定理 30A 的证明思路。要点：自指、反证法
2. 定理 30A 中三元关系 $R$ 是怎么定义的？其中的符号 $a,b,c,\alpha$ 分别代表什么？其中的推理是如何编码的？

教材 $\mathrm{\S }3.3$ 数论的子理论

教材 $\mathrm{\S }3.3.1$ 公理集 $A_E$

其中，$S1,S2$ 构成对后继运算的定义，$L1,L2,L3$ 构成对小于运算的定义，$A1,A2,M1,M2,E1,E2$ 分别构成对加法、乘法、幂乘运算的递归定义。

大题考点：

1. AE 公理集有哪些？分别是什么？

教材 $\mathrm{\S }3.3.2$ 可表示关系

可定义关系：设 $R$ 是 $\mathbb{N}$ 上的 $m$ 元关系，即 $R\subseteq {\mathbb{N}}^m$。我们已经知道，公式 $\rho$（其中只有 $v_1,\cdots ,v_m$ 是自由变元）在 $\mathfrak{N}$ 中定义 $R$ 当且仅当对于 $\mathbb{N}$ 中任意的 $a_1,\cdots ,a_m$，

$$\begin{gathered} ⟨a_1,\cdots ,a_m⟩\in R⟺{\models }_{\mathfrak{N}}\rho [a_1,\cdots ,a_m]\text{ \\ ⟺⊨Nρ(Sa10,⋯,Sam0).} \end{gathered}$$

（后两个条件等价是根据替换引理）我们可以把上述结果写成两个蕴涵式：

$$\begin{gathered} ⟨a_1,\cdots ,a_m⟩\in R\Rightarrow {\models }_{\mathfrak{N}}\rho ({\mathbf{S}}^{a_1}\mathbf{0},\cdots ,{\mathbf{S}}^{a_m}\mathbf{0})\text{ \\ ⟨a1,⋯,am⟩∉R⇒⊨N¬ρ(Sa10,⋯,Sam0)} \end{gathered}$$

可表示关系：如果在上述两个蕴涵式中，“在 $\mathfrak{N}$ 中为真”的概念可以被更强的概念“从 $A_E$ 中推出”取代，我们称 $\rho$ 在理论 $\mathrm{Cn}{A}_E$ 中可以表示 $R$。

$$\begin{gathered} ⟨a_1,\cdots ,a_m⟩\in R\Rightarrow \rho ({\mathbf{S}}^{a_1}\mathbf{0},\cdots ,{\mathbf{S}}^{a_m}\mathbf{0})\in T\text{ \\ ⟨a1,⋯,am⟩∉R⇒¬ρ(Sa10,⋯,Sam0)∉T} \end{gathered}$$

$\rho$ 在理论 $\mathrm{Th}\mathfrak{N}$ 中表示 $R$ 当且仅当 $\rho$ 在 $\mathfrak{N}$ 中定义 $R$。

一个关系在 $T$ 中是可表示的，当且仅当存在一个公式，在 $T$ 中表示该关系。

定理 33E 公式 $\rho$ 在 $\mathrm{Cn}{A}_E$ 中表示关系 $R$ 当且仅当

1. $\rho$ 由 $A_E$ 数字确定，且
2. $\rho$ 在 $\mathfrak{N}$ 中定义 $R$。

我们有必要比较一下可表示和可定义这两个概念。在这两个概念中，我们都是用公式来描述自然数之间的关系。对于可定义性，我们关心的是句子的解释是否是真的；而对于在 $\mathrm{Cn}{A}_E$ 中可表示，我们关心的是句子是否能从公理推出。

大题考点：

1. 可表示、可定义是怎么定义的？他们有什么区别？

笔者认为，“定义”意味着创造了新的概念，而“表示”并不创造新的概念。$\mathrm{Cn}{A}_E$ 作为一个封闭的理论，无法在其中创造更多的概念，因此使用“表示”这一术语。结构 $\mathfrak{N}$ 本身并不包含句子，因此用“定义”这一术语。

教材 $\mathrm{\S }3.3.5$ 可表示函数

在很多情况下，使用函数要比用关系来得方便。设 $f:{\mathbb{N}}^m\to \mathbb{N}$ 是自然数上的 $m$ 元函数，公式 $\phi$ 中只有 $v_1,\cdots ,v_{m+1}$ 是自由变元。我们称 $\phi$（在 $\mathrm{Cn}{A}_E$ 中）函数表示 $f$，当且仅当对于 $\mathbb{N}$ 中的每一 $m$ 元组 $a_1,\cdots ,a_m$，

$$A_E⊢\mathrm{\forall }{v}_{m+1}[\phi ({\mathbf{S}}^{a_1}\mathbf{0},\cdots ,{\mathbf{S}}^{a_m}\mathbf{0},v_{m+1})\leftrightarrow v_{m+1}={\mathbf{S}}^{f(a_1,\cdots ,a_m)}\mathbf{0}]$$

大题考点：

1. 可表示函数的定义

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

本题的第二小问在中文版教材前置条件被翻译为“在结构 $\{\mathbf{0}\}$ 中”，这是完全错误的翻译！请以本题的翻译为准！

证明：在算数关系中，很容易使用对数将乘法转化为加法。例如 $\log (nm)=\log (n)+\log (m)$。利用这一思路，定义加法关系为 $\{⟨n,m,p⟩|2En\cdot 2Em=2Ep\}$，其中 $2={\mathbf{S}}^2\mathbf{0}$。至此我们完成了对加法的定义，在后续我们会使用加法。

在此结构中，定义 $\{\mathbf{0}\}$ 为：$\mathrm{\forall }xx+\mathbf{0}=x$。

定义序关系为 $\{⟨n,m⟩|\mathrm{\exists }x(x+x\ne x\wedge n+x=m)\}$；

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

定义后继关系为 $\{⟨n,m⟩|\mathrm{\exists }x(x+x\ne x\wedge \mathrm{\forall }y\mathrm{\forall }z(y+y\ne y\to z+z\ne z\to y+z\ne x)\wedge n+x=m)\}$。

$Q.E.D.$

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

证明：

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

其次，令 $\tau$ 是一个形式为 $\mathrm{\neg }{\tau }_1$ 或 ${\tau }_2\to {\tau }_3$ 的句子，并且在 $\mathfrak{A}$ 中为真，其中 ${\tau }_i$ 是使得 $A_E⊢{\tau }_i$ 当且仅当 ${\tau }_i$ 在 $\mathfrak{A}$ 中为真，而 $A_E⊢\mathrm{\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⊢\mathrm{\neg }{\tau }_1$，并且 $A_E⊢\mathrm{\neg }{\tau }_2\vee {\tau }_3$，即 $A_E⊢\tau$；否则，${\tau }_1$ 在 $\mathfrak{A}$ 中为真，而 ${\tau }_2$ 在 $\mathfrak{A}$ 中为真，${\tau }_3$ 在 $\mathfrak{A}$ 中为假，这意味着 $A_E⊢\mathrm{\neg }\mathrm{\neg }{\tau }_1$，并且 $A_E⊢\mathrm{\neg }(\mathrm{\neg }{\tau }_2\vee {\tau }_3)$，即 $A_E⊢\mathrm{\neg }\tau$。

$Q.E.D.$

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

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

$Q.E.D.$

习题 6（不考）：3 是序列数字吗？$\mathrm{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。然而，形式上，我们仍然可以计算问题中的公式。

首先，形式上，$\mathrm{lh}b$ 定义为最小的 $n\in \mathbb{N}$，使得要么 $b = 0 $，要么 $⟨p_n,b⟩\notin \mathcal{D}$，其中 $\mathcal{D}$ 是可整除关系。在我们的例子中，$ \langle p_0, 3 \rangle \notin \mathcal{D}$，因此 $\mathrm{lh}3=0$。

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

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

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

$$f(\overline{a})=\{\begin{array}{ll}g(\overline{a})& \text{若 }\overline{a}\in R,\\ h(\overline{a})& \text{若 }\overline{a}\notin R.\end{array}$$

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

$Q.E.D.$

教材 $\mathrm{\S }3.4$ 语法的算数化

本节完成了对哥德尔数的具体定义，这意味着所有的公式都可以用自然数来表示。

如表 3-1，函数 $h$ 把每个左边的整数指派给右边的符号。例如 $h(\mathrm{\forall })=0,h(\mathbf{0})=2,h(v_i)=9+2i$。

对于一个语言的表达式 $\epsilon =(s_0\dots s_m)$，定义其哥德尔数为 $\mathrm{♯}(\epsilon )$

$$\mathrm{♯}(s_0\dots s_m)=⟨h(s_0),\dots ,h(s_n)⟩$$

比如，对 $\mathfrak{N}$ 的语言使用上述的函数 $h$，我们可以得到

对于一个推理（序列），$⟨{\alpha }_1,\dots ,{\alpha }_n⟩$，做如下指派：

$$\mathcal{G}(⟨{\alpha }_1,\dots ,{\alpha }_n⟩)=⟨\mathrm{♯}{\alpha }_1,\dots ,\mathrm{♯}{\alpha }_n⟩$$

存在可表示函数 $\mathrm{Sb}$，使得对于一个项或公式 $\alpha$，变元 $x$，及项 $t$，

$$\mathrm{Sb}(\mathrm{♯}\alpha ,\mathrm{♯}x,\mathrm{♯}t)=\mathrm{♯}{\alpha }_t^x$$

存在一个可表示关系 $\mathrm{Fr}$，使得对于一个项或公式 $\alpha$，及变元 $x$，

$$⟨\mathrm{♯}\alpha ,\mathrm{♯}x⟩\in \mathrm{Fr}⟺x\text{ 在 }\alpha \text{ 中自由出现}$$

性质：

$$⟨a,b⟩\in \mathrm{Fr}⟺\mathrm{Sb}(a,b,\mathrm{♯}\mathbf{0})\ne a$$

教材 $\mathrm{\S }3.5$ 不完全性和不可判定性

不动点引理：对于只含有自由变元 $v_1$ 的公式 $\beta$ ，我们可以找到句子 $\sigma$ 使得

$$A_E⊢[\sigma \leftrightarrow \beta ({\mathbf{S}}^{\mathrm{♯}\sigma }\mathbf{0})].$$

我们可以认为 $\sigma$ 间接地表达 “$\beta$ 是真的我。” 当然，实际上 $\sigma$ 什么也没说，它只是一些符号串而已。甚至当我们在 $\mathfrak{N}$ 中把它翻译成自然语言时，它也仅仅是关于一些数字和它们的后继及运算结果的句子。正是因为我们把数字和表达式联系起来，我们才能把 $\sigma$ 看作一个公式。

大题考点：

1. TODO：不动点定理的证明思路？

教材 $\mathrm{\S }3.5.2$ 弱可表示性

我们考虑递归可枚举集 $Q$，其中对于递归 $R$

$$a\in Q\iff \mathrm{\exists }b⟨a,b⟩\in R$$

我们知道存在公式 $\rho$ 在 $\mathrm{Cn}{A}_E$ 中表示 $R$ 。因此，公式 $\mathrm{\exists }{v}_2\rho$ 在 $\mathfrak{N}$ 中定义了 $Q$。这个公式在 $\mathrm{Cn}{A}_E$ 中不能表示 $Q$，除非 $Q$ 是递归的。但我们说这个公式几乎可以表示 $Q$。

大题考点：

1. TODO：弱可表示性的定义

教材 $\mathrm{\S }3.6$ 递归函数

另有：习题 3.6 1；2（a);3;4;8

习题 1：如下定义函数 $f$ 和 $g$，

$$\begin{gathered} f(n)=\{\begin{array}{ll}0& \text{如果哥德巴赫猜想是对的}\\ 1& \text{其他情况}\end{array}\text{ \\ g(n)={0如果在 π 的十进制小数展开式中至少连续出现 n 个 71其他情况} \end{gathered}$$

那么，$f$ 是递归的吗？$g$ 是递归的吗？（哥德巴赫猜想是指任意一个比 2 大的偶数都可以写成两个素数的和。在这本书的第一版使用的是 Fermat 最终定理。）

函数 $f$ 不是递归的，因为 $f$ 是常函数。

函数 $g$ 是递归可枚举函数，不是递归函数。

习题 2：定义对角线函数 $d(a)=[a{]}_1(a)+1$。

（a）证明：$d$ 是部分递归函数

这题不会，跳过。

习题 3：（a）证明：任意部分递归函数的值域都是递归可枚举的。

（b）证明：严格递增的全递归函数 $f$（即, $f(n)<f(n+1)$）的值域是递归的。

（c）证明：递增全递归函数 $f$（即, $f(n)\le f(n+1)$）的值域是递归的。

这道题考前重点讲解。

证明：听了，但没听懂。真不会了，考到就认命吧。

教材 $\mathrm{\S }3.6.2$ 部分递归函数

范式定理（Kleene，1943）

（a）在 $⟨e,a_1,\cdots ,a_m⟩$ 的值是 $[e{]}_m(a_1,\cdots ,a_m)$ 的 $(m+1)$ 元部分函数是部分递归函数）

（b）对于每个 $e⩾0$，$[e{]}_m$ 是 $m$ 元部分递归函数

（c）对于任意 $m$ 元部分递归函数, 都存在某个 $e$, 使得这个部分递归函数等于 $[e{]}_m$

在范式定理中，符号 $e,a,k,T_m$, 和 $k^{\prime }$ 的含义如下：

1. $e$: 这是递归函数的索引或编码，通常对应于一个程序或计算过程的标识符。它表示一个递归函数或其对应的程序。
2. $a$: 这是输入向量，通常表示为 $a_1,a_2,\dots ,a_m$，是递归函数的输入参数。
3. $k$: 这是一个编码，表示从公式 $\phi$ 推导出结果的推理过程的哥德尔数。它包含了推理过程和结果的信息。
4. $T_m$: 这是一个 $(m+2)$ 元关系，包含 $e,a_1,\dots ,a_m,k$。它定义了计算步骤，表示 $e$、输入 $a$ 和编码 $k$ 之间的关系，其中 $k$ 编码了从公式 $\phi$ 推导出结果的推理过程。
5. $k^{\prime }$: 这是在 $k$ 之前的某个值，用于确保 $k$ 是满足条件的最小值。在最小化操作 $\mu k$ 中，$k^{\prime }$ 代表比 $k$ 更小的值，用于检查是否有更小的 $k$ 满足条件。

范式定理的核心思想是，对于任意递归函数 $f$，存在一个索引 $e$，使得 $f(a_1,\dots ,a_m)$ 可以表示为 $U(\mu k(e,a_1,\dots ,a_m,k)\in T_m)$，其中 $U(k)$ 提取编码 $k$ 中的结果部分。通过这些符号和关系，定理描述了递归函数的计算过程和其通用性。

大题考点：

1. 解释范式定理中符号 $e,a,k,T_m$, 和 $k^{\prime }$的意思

教材 $\mathrm{\S }3.7$ 第二不完全性定理

哥德尔第二不完全性定理（1931） 设 $T$ 是一个足够强的递归可公理化理论，则 $T⊢\mathrm{Cons}T$ 当且仅当 $T$ 是不和谐的。

证明思路：

哥德尔第二不完备定理表明，如果一个足够强大的公理系统是相容的，那么它不能证明它自身的相容性。以下是该定理的证明思路，分为几个关键步骤：

可证明性公式：首先，我们定义一个公式 ${\text{Prb}}_T(x)$，它表示“ $x$ 在系统 $T$ 中是可证明的”。这个公式通过哥德尔编码来表示公式和证明的过程。

相容性公式：接下来，我们定义系统的相容性公式 $\text{ConsT}$，它表示“系统 $T$ 是相容的”，即不存在可证明的矛盾。具体来说，$\text{ConsT}$ 可以表示为 $\mathrm{\neg }{\text{Prb}}_T(0=1)$，即系统 $T$ 不能证明 $0=1$。

不动点引理：利用不动点引理，我们可以构造一个自指命题 $\sigma$，使得 $\sigma$ 等价于 $ \neg \text{Prb}_T(\sigma)$。这个命题 $\sigma$ 可以被理解为“我不可证明”。

假设系统证明相容性：假设系统 $T$ 能够证明其相容性，即 $T⊢\text{ConsT}$。根据 $\sigma$ 的定义，我们有：

$$T⊢(\sigma \leftrightarrow \mathrm{\neg }{\text{Prb}}_T(\sigma ))$$

利用反射性质：通过反射性质，我们可以证明如果 $T⊢\sigma$，那么 $T⊢{\text{Prb}}_T(\sigma )$。然而，根据 $\sigma$ 的定义，这会导致矛盾，因为 $T$ 不能同时证明 $\sigma$ 和 $\mathrm{\neg }{\text{Prb}}_T(\sigma )$。

Löb 定理的应用：Löb 定理指出，如果 $T$ 证明“${\text{Prb}}_T(\tau )\to \tau$”，那么 $T$ 证明 $\tau$。在这个情境下，如果 $T$ 证明 $\text{ConsT}$，那么根据 Löb 定理，$T$ 会证明 $\mathrm{\neg }{\text{Prb}}_T(0=1)$，即 $\text{ConsT}$ 本身。

结论：如果 $T$ 是相容的，它不能证明 $\text{ConsT}$，因为如果 $T$ 能证明 $\text{ConsT}$，那么根据上述推理，$T$ 会变得不相容。因此，哥德尔第二不完备定理成立：如果 $T$ 是相容的，它不能证明自身的相容性。

总结：哥德尔第二不完备定理的证明思路是通过构造自指命题 $\sigma$，利用可证明性和相容性的表达，结合反射性质和 Löb 定理，最终得出系统无法证明自身相容性的结论。

一个基于哥德尔第一不完备定理的更简单的证明思路：

哥德尔第一不完备定理可以简化为对“若公理体系具有一致性，则构造的自指命题 $\sigma$ 为真”这一命题的否定。

哥德尔第二不完备定理可以简化为对“从公理可推出公理体系具有一致性”这一命题的否定。

若“从公理可推出公理体系具有一致性”这一命题成立，则有从公理出发可推出自指命题 $\sigma$ 为真，这本身就是一个推导出（证明出）$\sigma$ 的过程，与第一不完备定理相悖。因此“从公理可推出公理体系具有一致性”这一命题为假。

大题考点：

1. TODO：简叙哥德尔第二不完全性定理（P200）的证明思路