2025数理逻辑期末复习

关于逻辑学

若前提100%正确，结论是否保证 100%正确？论证过程是否严密，与“前提是否正确”无关

“前提”来自各个领域，其正确性和“逻辑”本身无关
逻辑学家关心的是：“从某些（假定为真的）论据出发，究竟能不能得到最终的结论”

演绎有效性（非正式定义）：我们称一个推演步骤是有效的当且仅当不存在任何一种可能，令该推演的前提为真且结论为假。同样地，在这种情况下我们称这些前提蕴涵（entails）其结论。即在最弱最弱最弱……（省略无穷次）的情况下，推演的前提为真时，其结论也不可能为假。甚至可以说，前提为真且结论为假的情况是在根本上不自洽的。换句话说，一个有效的推演，其结论一定是前提的必要条件。

一个或多个命题是一致的（consistent），当且仅当在任意可能的情况下，它们都同时为真。

两个命题是等价的（equivalent），当且仅当它们在完全相同的可能情况下才同时为真。

逻辑的目的是系统性地检验论证的有效性：我们称一个推演步骤是逻辑有效的，当且仅当它的有效性仅由其前提与结论中的话题无关词汇决定。对于一个逻辑有效的演绎，我们称其前提逻辑上蕴涵（logically entails）其结论。

培根（Francis Bacon）：亚里士多德《工具论》中的那些纯演绎的方法（三段论）不足以发现科学真理,因此需要《新工具》（Novum Organum Scientiarum）

康德（Immanuel Kant）：分析命题（主项包含谓项）不提供新知识，后天综合命题讲述经验世界的知识，而哲学、数学知识应该是先天综合命题。

0. 集合

$ A;t = A {t } $

良序关系

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

自然数的定义

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

自然数的定义：$0=∅,1=0+$。

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

数学归纳法

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

三歧性：$∀x,y∈A.x∈y∨x=y∨y∈x$。

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

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

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

有穷集合和无穷集合

习题： 证明 $ω^{++}$ 与 $ω$ 等势。

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

$A∩A_1=∅,B∩B_1=∅$；
$A∼B,A_1∼B_1$；

证明：$A∪A_1∼B∪B_1$。

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

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

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

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

可数集合

习题：设 $A,B$ 为两个可数集合，且 $A,B$ 不相交，即 $A∩B=∅$。证明：$A∪B$ 也是可数的。

习题（不考）：证明：

对任意 $k∈ω$ 有，$ω_k$ 都是可数集合（约定 $ω_0={∅},ω_1=ω$）；
集合 $⋃{ω_k|k∈ω}$ 是可数的。

不可数集合（不考）

序数

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

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

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

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

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

（1）如果 $α$ 是 $S$ 的最大元，则 $α=⋃S$；

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

超穷归纳法

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

习题：设 $α,β$ 为序数，且 $α≠0$。

（1）$α$ 是极限序数，当且仅当 $⋃α=α$；

（2）如果 $β∈α$，且 $β$ 是 $α$ 的最大元，则 $α=β^+$。

可数序数

定义 $ω_1=\{α∣α 是可数序数\}$。$ω_1$ 是序数，且不可数。

定义 $ω_α+1=\{β∣β\ 是序数且\ β⪯ω_α\}$。

基数

设 $α$ 是序数，如果对于任意的 $β<α$ 都有 $β≺α$，则称 $α$ 是基数。

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

$card\ A=card\ B⟺A∼B$

习题：设 $α$ 为基数，κ 为集合是序数且与等势$\{β|β 是序数且与 α 等势\}$ 的最小元。证明：$κ$ 是基数。

习题：对任意的 $α$ 都有，$α≤ωα$。

1. 命题逻辑

如果能谈论命题和命题的真假，我们应该也能谈论命题“并非”和“并且”的真假。

在逻辑学中，命题逻辑可以看作是一种 “零阶逻辑” (相比于一阶逻辑和高阶逻辑)，也就是不含任何变量绑定的逻辑。

1.1 命题逻辑的语言

合式公式（Well-Formed Formulas）：

每个命题符号$A_i$都是合式公式（原子公式，atomic formula）
若$\alpha$ ，$\beta$是合式公式，那么$(¬ \alpha)$和$(\alpha□ \beta)$也是合式公式。其中$□ $是$∧,∨,→$和$↔︎$ 中的一个
除此以外都不是合式公式。

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

习题：设 $α$ 是一个合式公式，$c$ 是二元连接符（$∧,∨,→,↔$）出现的次数，$s$ 是命题符合出现的次数（例如，若 $α=(A→(¬A))$，则 $c=1,s=2$）。使用归纳法证明：$s=c+1$。

1.2 真值指派

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

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

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

$\bar v: \bar S\rightarrow{T,F}$

我们称真值指派 $v$ 满足 $φ$，当且仅当 $\bar v(φ)=T$。

重言蕴含：$Σ⊨τ$ 当且仅当满足 $Σ$ 中每个合式公式的真值指派也满足 $τ$。$\{σ\}⊨τ$ 也记为 $σ⊨τ$。

重言式： $∅⊨τ$ 也记为 $⊨τ$。

重言等价：$σ⊨τ$ 并且 $τ⊨σ$，记为 $σ⊨=|τ$。

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

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

习题：（置换）$α_1$, $α_2$,… 一个合式公式的序列，对每个合式公式 $φ$，令 $φ^*$ 是用 $α_n$置换 $A_n$（对所有 $n$）后得到的结果。

设 $v$ 是所有命题符号的真值指派，定义 u 为满足 $u(A_n)=\bar v(α_n)$ 的真值指派，证明 $\bar u(φ)=v(φ^∗)$ 使用归纳法。
证明如果 $φ$ 是重言式，那么 $φ^∗$ 也是。（例如，$((A∧B)↔(B∧A))$ 是一个重言式，因此对任意的合式公式 $α,β$，通过置换可得 $((α∧β)↔(β∧α))$ 是重言式）

1.3 解析算法

输入：命题逻辑wff $\varphi$

输出： $\varphi$ 的解析树 $T$

习题（不考）：证明引理 13B 中关于运算 $ε¬$ 的情形。

习题：假定将合式公式的定义修改为去掉其中所有的右括号。对于$((A∧(¬B))→(C∨D))$，我们写成：$((A∧(¬B→(C∨D$ 。证明这种记法具有唯一可读性（即每个合式公式只有一个可能的分解方法）。提示：这种表达式具有的括号数和联结符号数相同。

1.4 归纳与递归

递归定义：

自上而下： \[S^* = \bigcap \{ S \mid S \text{ 包含所有命题符号且关于五种公式构造运算封闭} \}\]
自下而上： $S_0 = \{ A_1, \ldots \}$ $S_i = \{ \neg \alpha \mid \alpha \in S_{i-1} \} \cup \{ \alpha □ \beta \mid \alpha \in S_{i-1}, \beta \in S_{i-1}, □ = \land, \lor, \rightarrow, \leftrightarrow \} \cup S_{i-1}$ $S_* = \bigcup_{n} S_n$

$S^*=S_*$

关于命题逻辑的归纳原理：

令 $ P() $ 为一个关于命题逻辑的性质。假设：

对所有命题符号 $ A_i $，性质 $ P(A_i) $ 成立
对所有的命题公式 $ $ 和 $ $，若 $ P() $ 和 $ P() $ 成立，则 $ P() $ 和 $ P(()) $ 也成立，其中 $\Box$ 是 $\land$、$\lor$、$\rightarrow$ 和 $\leftrightarrow$ 中的任意一个

那么对于所有的命题公式 $ $ 有性质 $ P() $ 成立。

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

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

1.5 命题连接词

只用 $\neg, \land, \lor, \rightarrow, \leftrightarrow$ 五个联结词就可以实现任意 $n$ 元布尔函数

习题：设 $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）给出一个仅使用 $∧,∨,¬$ 的能够实现的合式公式；

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

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

1.7 紧致性和能行性（不考）

2. 一阶逻辑

在逻辑学中, 谓词逻辑是在命题逻辑的基础上加入量词得到的逻辑，量词包括全称和存在两个逻辑连接词。根据量词的强大程度，谓词逻辑可以进一步被分类为一阶逻辑、二阶逻辑乃至高阶逻辑等。

2.1 一阶语言

一阶语言是一类形式语言, 是一阶逻辑使用的语言。大部分现代数学都基于一阶逻辑（一阶语言包含集合论语言，一切数学都可被嵌入在集合论中）。

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

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

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

没有联结符号和量词符号的合式公式，项+谓词。

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

原子公式通过0次或多次联结符号和量词符号构成的表达式

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

2.2 真值与模型

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

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

全称量词 $∀$
n 元谓词符号 $P$
常数符号 $c$
$n$ 元函数符号 $f$

结构的基本思想就是给参数赋予意义。

若句子 $σ$ 在 $\mathfrak{A}$ 中为真，则称 $\mathfrak{A}$ 是 $σ$ 的一个模型，记为 $⊨ _\mathfrak{A} σ$ 。

对于结构 $\mathfrak{A}$，函数 $s:V→|\mathfrak{A}|$ 满足合式公式 $φ$ 记为 $⊨_\mathfrak{A}\varphi[s]$。

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

$\models_\mathfrak{A}(\varphi \rightarrow \psi)[s]$ 当且仅当或者$\not\models _\mathfrak{A}\varphi [s]$ 或者$\models _\mathfrak{A}\psi [s]$或者二者都成立。

逻辑蕴涵

合式公式集合 \[Γ\] 逻辑蕴含合式公式 $\varphi$ 记作 $Γ⊨φ$，当且仅当对语言中的每个结构 $\mathfrak{A}$ 和每个函数 $s:V→|A|$，使得 $\mathfrak{A}$ 以 $s$ 满足 $Γ$ 的每个元素时，$\mathfrak{A}$ 也以 $s$ 满足 $φ$。

$⊨$ 在命题逻辑中表示重言蕴含，在一阶语言中表示逻辑蕴含。

这里的逻辑蕴涵使用的（元语言）符号 $⊨$ 与第二章《命题逻辑》里一模一样。由于一阶逻辑包含（subsumes）命题逻辑（只需允许0元谓词存在），因此逻辑蕴涵包含重言蕴涵，也更接近我们在第一章《非形式化逻辑》里的定义

下面这段话来自教材：

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

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

习题：证明：${∀x(α→β),∀xα}⊨∀xβ$

习题：证明：如果 $x$ 在 $α$ 中不是自由出现的，那么 $α⊨∀xα$。

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

(a) $|\mathfrak{A}|$ 中恰好有两个元素。

习题： 全称公式 $(∀_1)$ 是形式为 $∀x_1 ···x_nθ$ 的公式, 存在公式 $(∃_1)$ 是形式为 $∃x_1 ···x_nθ$ 的公式。其中 $θ$ 是无量词. 设 $\mathfrak{A}$ 是 $\mathfrak{B}$ 的子结构，$s : V → |\mathfrak{A}|$.

(a) 证明:

如果 $⊨ _\mathfrak{A} ψ[s]$ 且 $ψ$ 是存在公式，那么 $⊨_\mathfrak{B} ψ[s]$.

如果 $⊨ _\mathfrak{B} \varphi[s]$且 $\varphi$ 是全称公式，那么 $⊨ _\mathfrak{A} φ[s]$.

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

(a) 试找出一个句子，它在一个结构中是真的，在另外一个中是假的.

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

说明: 该结果产生“不含等号的升洛文海–斯科伦定理”(见习题 2.6). 即，不含等号时, 任意一个结构 A 都有任意更高基数的扩充结构 $\mathfrak{B}$、使得 $\mathfrak{A}$ 与 $\mathfrak{B}$ 是初等等价的，除了相等。除非加入等号，否则这个结论是最强的.

2.3 解析算法

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

习题：证明对于一个合式公式 $α$ 的真的初始段 $α^′$，$K(α^′) < 1.$

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

2.4 演绎计算

替换、可替换

证明的定义：从 $\Gamma$ 到 $\varphi$ 的证明（推导）是一个有穷的 wff 序列 $\langle \alpha_0, \ldots, \alpha_n \rangle$，其中 $\alpha_n$ 就是 $\varphi$ 且对任意 $k \leq n$ 有：

$\alpha_k$ 属于 $\Gamma \cup \Lambda$（$\Lambda$ 为公理集）, 或者
$\alpha_k$ 是由序列中位于它前面的两个 wff 经过 MP 规则推导而得；即存在 $i, j \leq k$ 有 $\alpha_j$ 为 $\alpha_i \rightarrow \alpha_k$

若以上证明存在，我们就说 $\varphi$ 是从 $\Gamma$ 出发可证的（provable, deducible or derivable）, 或称 $\varphi$ 是 $\Gamma$ 中的定理（theorem of $\Gamma$）, 记为 $\Gamma \vdash \varphi$.

假言推理（Modus Ponen，又称 MP 规则或直言三段论）：$\frac {α,α→β} {β}$

逻辑公理的集合$Λ$ ：

重言式；
$∀xα→α_t^x$，其中 $t$ 是 $x$ 在 $α$ 中的替换，即把 $α$ 中出现的 $x$ 换成 $t$；
$∀x(α→β)→(∀xα→∀xβ)$；
$α→∀xα$，其中 $x$ 在 $α$ 中不是自由出现的（自由出现的意思是无量词限定，例如 $∀yx+y=2$ 中 $x$ 是自由出现的，$y$ 不是）；
$x=x$；
$x=y→(α→α^′)$，其中 $α$ 是原子的，$α^′$ 是有限次的将 $α$ 中的 $x$ 替换为 $y$ 得到的。

由 $Γ∪Λ$ 和假言推理可以获得的公式集叫做 $Γ$ 的定理集合。

概化定理：如果 $Γ⊢φ$ 且 x 不在 $Γ$ 的任何公式中自由出现，则 $Γ⊢∀xφ$。

规则 $T$ ：如果 $Γ⊢α1,…,Γ⊢αn$，且 ${α1,…,αn}$ 重言蕴含 $β$ ，那么 $Γ⊢β$。

演绎定理：如果 $Γ;Γ⊢φ$，那么 $Γ⊢(Γ→φ)$。从右到左叫做演绎，从左到右叫演绎定理。

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

$v(α)=T$ iff $⊨_\mathfrak{A}α[s]$

证明，对于任意公式（基本与否均可），有：$\bar v(α)=T$ iff $\ ⊨_\mathfrak{A}α[s]$。说明: 这个结论说明联结词 ¬与 → 在第二章与在第一章中的含义是一样的

(b)如果 $Γ$ 重言蕴含 $φ$，则 $Γ$ 逻辑蕴涵 $φ$。

习题： 设 x 不在 $α$ 中自由出现，证明 Q2b：$⊢(α→∃xβ)↔∃x(α→β)$；在同样的假设下，证明 Q3a：$⊢(∀xβ→α)↔∃x(α→β)$

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

(b)证明：如果 $y$ 不在 $φ$ 中出现，那么在 $φyx$ 和 $(φyx)xy=φ$ 中 $x$ 可替换 $y$。提示：对 $y$ 使用归纳法。

习题（不考）：证明 Eq3：$⊢∀x∀y∀z(x=y→y=z→x=z)$

2.5 可靠性与完备性理论

可靠性定理：如果 $Γ⊢φ$，那么 $Γ⊨φ$。

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

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

如果 $Γ⊨φ$，那么 $Γ⊢φ$。
任意和谐的公式集都是可满足的。

紧致性定理：

如果 $Γ⊢φ$，那么存在某个有限的 $Γ_0⊆Γ$，有 $Γ_0⊢φ$。
如果 $Γ$ 的每个有限子集 $Γ_0$ 都是可满足的，那么 $Γ$ 是可满足的。特别地，句子集 $Σ$ 有模型当且仅当其每个有限子集有模型。

可枚举定理：

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

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

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

习题：（语义规则 EI）假设常数符号 $c$ 不在 $φ$、$ψ$ 和 $Γ$ 中出现，$Γ;φ_c^x⊨ψ$，证明：$Γ;∃xφ⊨ψ$。（不使用可靠性定理和完备性定理）

习题（不考）：证明完备性定理 (a) 与 (b) 等价。提示：$Γ⊢φ$ 当且仅当 $Γ∪{¬φ}$ 是不可满足的，且 $Δ$ 是可满足的当且仅当 $Δ⊭⊥$，其中 Δ 是某个不可满足的、可批驳的公式集，如 $¬∀xx=x$。

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

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

$Γ⊢ϕ$ 意味着 $Γ⊨ϕ$ 。对于不含 $P$ 且 $s:V→|𝔄|$ 的语言的每个结构 $𝔄$ ，使得 $⊨_𝔄Γ[s]$ ，考虑含 $P$ 的语言的对应结构 $𝔄^′$ ，它通过定义 $P^𝔄=∅$ 扩展了 $𝔄$ 。然后 $⊨_{𝔄^′}Γ[s]$ （因为 $Γ$ 中没有 wff 使用 P ），因此 $⊨_{𝔄^′}ϕ[s]$ ，意味着 $⊨_𝔄ϕ[s^′]$（出于同样的原因）。因此，不含 $P$ 的语言中的 $Γ⊨ϕ$ 和 $Γ⊢ϕ$ 。

习题：设 $Γ={¬∀v1Pv1,Pv2,Pv3,…}$，$Γ$ 是否和谐？是否可满足？

2.6 理论的模型

紧致性定理：

如果 $Γ⊢φ$，那么存在某个有限的 $Γ_0⊆Γ$，有 $Γ_0⊢φ$；
如果 $Γ$ 的每个有限子集 $Γ_0$ 都是可满足的，那么 $Γ$ 是可满足的。特别地，句子集 $Σ$ 有模型当且仅当其每个有限子集有模型。

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

(a)$∃x∃y∃z[(Pxfx→Pxx)∨(Pxy∧Pyz∧¬Pxz)]$

习题：设 $T_1$ , $T_2$ 是同一语言的两个理论，使得$T_1 ⊆ T_2$、 $T_1$是完备的、 $T_2$是可满足的。证明: $T_1=T_2$

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

(a)$(∃xAx∧∃xBx)→Cx$

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

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

（b）证明：恒真的 $∀_2$ 句子集是可判定的。（$∀_2$ 公式是指具有形式 $∀x_1…∀x_m∃y_1…∃y_nθ$的公式，其中 $θ$ 是无量词的公式。）

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

2.7 理论之间的解释（不考）

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

习题：设 L0 是含有等号及二元函数符号 + 和 ⋅ 的语言，L1 也一样，只不过用三元谓词符号表示加法和乘法。令 Mi=(N;+,⋅)(i=0,1) 分别是包含自然数和加法、乘法的语言 Li 的结构。证明在 M0 中由 L0 公式定义的任何关系都能在 M1 中由 L1 公式定义。

3. 不可判定性

3.0 数论

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

Q: 定理30A的证明思路。

Q: 定理30A中三元关系R是怎么定义的？其中的符号a,b,c,？其中的推理是如何编码的？

3.3 数论的子理论

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

叙述题

1.简叙Goedel定理的证明思路

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

证明思路：

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

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

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

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

假设系统证明相容性：假设系统 $T$ 能够证明其相容性，即 $T⊢ConsT$。根据 $σ$ 的定义，我们有：$T⊢(σ↔¬Prb_T(σ))$

利用反射性质：通过反射性质，我们可以证明如果 $T⊢σ$，那么 $T⊢Prb_T(σ)$。然而，根据 $σ$ 的定义，这会导致矛盾，因为 $T$ 不能同时证明 $σ$ 和 $¬Prb_T(σ)$。

$Löb$ 定理的应用：$Löb$ 定理指出，如果 $T$ 证明“$Prb_T(τ)→τ$”，那么 $T$ 证明 $τ$。在这个情境下，如果 $T$ 证明 $ConsT$，那么根据 $Löb$ 定理，$T$ 会证明 $¬Prb_T(σ)$，即 $ConsT$ 本身。

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

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

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

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

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

2.定理30A的证明思路。

利用哥德尔数构造自指句子 $σ$；
使用反证法，通过假设推出矛盾以证明假设的反面；
得出结论。

3.定理30A中三元关系R是怎么定义的？其中的符号$a,b,c,\alpha$分别代表什么？其中的推理是如何编码的？

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

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

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

$⟨a_1,⋯,a_m⟩∈R⟺⊨_\mathfrak{N}ρ[a_1,⋯,a_m]⟺⊨_\mathfrak{N}ρ(S^{a1}0,⋯,S^{am}0)$.

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

$⟨a_1,⋯,a_m⟩∈R⇒⊨_\mathfrak{N}ρ(S^{a_1}0,⋯,S^{a_m}0)⟨a_1,⋯,a_m⟩∉R⇒⊨_\mathfrak{N}¬ρ(S^{a_1}0,⋯,S^{a_m}0)$

可表示关系：如果在上述两个蕴涵式中，“在 N 中为真”的概念可以被更强的概念“从 AE 中推出”取代，我们称 ρ 在理论 Cn AE 中可以表示 R。

$⟨a_1,⋯,a_m⟩∈R⇒ρ(S^{a_1}0,⋯,S^{a_m}0)∈T⟨a_1,⋯,a_m⟩∉R⇒¬ρ(S^{a_1}0,⋯,S^{a_m}0)∉T$

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

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

定理 33E 公式 $ρ$ 在 $Cn A_E$ 中表示关系 R 当且仅当

$ρ$ 由 $A_E$ 数字确定
$ρ$ 在 $\mathfrak{N}$ 中定义 $R$。

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

6.可表示函数、弱可表示的定义

可表示函数: 设 $f:\mathbb{N}^m→\mathbb{N}$ 是自然数上的 m 元函数，公式 $φ$ 中只有 $v_1,⋯,v_{m+1}$ 是自由变元。我们称 $φ$（在 $Cn A_E$ 中）函数表示 $f$，当且仅当对于 $\mathbb{N}$ 中的每一 $m$ 元组 $a_1,⋯,a_m$，

$A_E⊢∀v_{m+1}[φ(S^{a_1}0,⋯,S^{a_m}0,v_{m+1})↔v_{m+1}=S^{f(a_1,⋯,a_m)}0]$

弱可表示: 考虑递归可枚举集 $Q$，其中对于递归 $R$ : $a∈Q⇔∃b⟨a,b⟩∈R$

我们知道存在公式 $ρ$ 在 $Cn\ A_E$ 中表示 $R$ 。因此，公式 $∃v_2ρ$ 在 $N$ 中定义了 $Q$。这个公式在 $Cn\ A_E$ 中不能表示 $Q$，除非 $Q$ 是递归的。但我们说这个公式几乎可以表示 $Q$。

7.不动点定理的证明思路？

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

$A_E⊢[σ↔β(S^{♯σ}0)].$

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

8.解释范式定理中符号e,a,k,T_m,k,k’的意思

范式定理（Kleene，1943）

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

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

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

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

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

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