Gödel 不完备性定理

Gödel 不完备性定理包括 Gödel 第一不完备性定理与 Gödel 第二不完备性定理. 前者指的是一阶 Peano 算术系统, 只要是相容的, 就不是完备的, 并且甚至无法添加有限个语句来完备化 Peano 算术. 后者则指的是此系统不能证明本身的自洽性.

1Gödel 第一不完备性定理

陈述

定理 1.1 (Gödel 第一不完备性定理). 任何包含 ${\mathsf{PA}}_1$, 递归的, 且相容的理论 $T$ 都不是完备的.

证明

下述的推理过程对所有满足定理 (1.1) 条件的理论 $T$ 都类似, 所以我们只对 $T={\mathsf{PA}}_1$ 证明. 取标准的 Gödel 编号 $\#$, 并且设 $\mathrm{True}(x)$ 定义 $\#\mathrm{Th}({\mathsf{PA}}_1)$.

引理 1.2 (对角线引理). 对于任意只含一个自由变元 $x$ 的公式 $\phi (x)$, 存在语句 $\gamma$ 使得$${\mathsf{PA}}_1⊢\gamma \leftrightarrow \phi (\#\gamma ).$$

证明. 首先, 如下的函数可以延拓到某个可定义函数: $$\begin{array}{cccc}d:& \#\mathrm{Free}(x)& \to & \mathbb{N}\\ & \#\varphi & \mapsto & \#\varphi (\#\varphi ).\end{array}$$这是因为它是递归可枚举函数, 从而在算术阶层里属于 ${\Sigma }_1^0$ (Post 定理), 故它可定义. 取 $\gamma$ 为 $\chi (\#\chi )$, 其中$$\chi (x)=\exists y(y=d(x)\wedge \phi (y))$$且 $\#\chi$ 代表句法上的 “$\#\chi$”, 即$$\#\chi :=S(\cdots S(0)).$$下验证 ${\mathsf{PA}}_1⊢\gamma \leftrightarrow \phi (\#\gamma )$.

•

一方面 ${\mathsf{PA}}_1\cup \{\gamma \}⊢\phi (\#\gamma )$. 这是因为 $d$ 的假设说明 ${\mathsf{PA}}_1⊢(y=d(\#\chi )\to y=\#\gamma )$, 并且 $\{\gamma \}⊢\exists y(y=d(\#\chi )\wedge \phi (y))$, 由存在列举得$$\begin{array}{c}\underline{{\mathsf{PA}}_1\cup \{\gamma \}⊢\exists y(y=d(\#\chi )\wedge \phi (y)){\mathsf{PA}}_1\cup \{\gamma \}\cup \{y=d(\#\chi )\wedge \phi (y)\}⊢y=\#\gamma \wedge \phi (y)}\\ {\mathsf{PA}}_1\cup \{\gamma \}⊢\phi (\#\gamma ).\end{array}$$

•

另一方面 ${\mathsf{PA}}_1\cup \{\phi (\#\gamma )\}⊢\gamma$. 这是因为 ${\mathsf{PA}}_1\cup \{\phi (\#\gamma )\}⊢\#\gamma =d(\#\chi )\wedge \phi (\#\gamma )$, 由存在概括得 ${\mathsf{PA}}_1\cup \{\phi (\#\gamma )\}⊢\gamma$.

综上两方面, 利用演绎定理得到 ${\mathsf{PA}}_1⊢\gamma \leftrightarrow \phi (\#\gamma )$.

$\square$

引理 1.3. 对于任意语句 $\phi$, 如果 ${\mathsf{PA}}_1⊢\phi$, 那么 ${\mathsf{PA}}_1⊢\mathrm{True}(\#\phi )$.

证明. 由 $\mathrm{True}(x)$ 的定义知 ${\mathsf{PA}}_1⊢\phi ⟺\mathbb{N}\models \mathrm{True}(\#\phi )$. 我们想证明不仅仅是对 $\mathbb{N}$, 而是对 ${\mathsf{PA}}_1$ 的任何模型都有上述关系. 但是注意 $\#\mathrm{Th}({\mathsf{PA}}_1)$ 是递归可枚举集合, 故 $\mathrm{True}(x)$ 可被选作属于 ${\Sigma }_1^0$, 即所有量词都是有界的. 由于 $\mathrm{True}(\#\phi )$ 所有量词都是有界的, 故它等价于某个不含量词者, 因为 ${\mathsf{PA}}_1$ 包含如下公理: $$\exists x\le n\to x=0\vee \cdots \vee x=n.$$但是不含量词者如果以 $\mathbb{N}$ 作为模型, 就必定以所有 ${\mathsf{PA}}_1$ 的模型作为模型, 再由 Gödel 完备性定理得到 ${\mathsf{PA}}_1⊢\mathrm{True}(\#\phi )$.

$\square$

Gödel 第一不完备性定理的证明. 在对角线引理 (1.2) 中取 $\phi =\neg \mathrm{True}(x)$, 得$${\mathsf{PA}}_1⊢\gamma \leftrightarrow \neg \mathrm{True}(\#\gamma ).$$从而:

•	如果 ${\mathsf{PA}}_1⊢\gamma$, 则引理 (1.3) 说明 ${\mathsf{PA}}_1⊢\mathrm{True}(\#\gamma )$, 矛盾.
•	如果 ${\mathsf{PA}}_1⊢\neg \gamma$, 则 ${\mathsf{PA}}_1⊢\mathrm{True}(\#\gamma )$, 故 $\mathbb{N}\models \mathrm{True}(\#\gamma )$, 即 ${\mathsf{PA}}_1⊢\gamma$, 也矛盾.

也就是说, ${\mathsf{PA}}_1$ 无法证明 $\phi$ 也无法证明 $\neg \phi$.

$\square$

Tarski 不可定义定理

主条目: Tarski 不可定义定理

我们也可以仅仅利用语义来证明定理 (1.1). 由于 $T$ 相容, 它有模型 $\mathcal{M}$. 下面的过程对所有这样的模型都类似, 所以我们只对 $\mathcal{M}=\mathbb{N}$ 为标准模型时证明.

利用 Tarski 不可定义定理, 得到 $\#\mathrm{Th}(\mathbb{N})$ 不是可定义集. 但是 $\#\mathrm{Th}(T)$ 是可定义集, 因为它是由一些递归的公理出发, 通过推导规则产生的 Gödel 数的集合. 故$$\mathrm{Th}(\mathbb{N})\ne \mathrm{Th}(T).$$从而 $T$ 不是完备的.

2Gödel 第二不完备性定理

延续上一节的记号.

陈述

定理 2.1 (Gödel 第二不完备性定理). 任何包含 ${\mathsf{PA}}_1$, 递归的, 且相容的理论 $T$ 都满足$$T⊬\neg \mathrm{True}(\#\perp ).$$一般也把 $\neg \mathrm{True}(\#\perp )$ 记作 $\mathrm{Con}(T)$.

注 2.2. 它是 “$T$ 不能证明自身完备性” 的句法翻译. 因为 “能证明自身完备性” 代表 “能证明 $T⊬\perp$”, 即 “能证明 $\mathbb{N}⊭\mathrm{True}(\#\perp )$”, 即 “能证明 $\mathbb{N}\models \neg \mathrm{True}(\#\perp )$”, 即 $T⊢\neg \mathrm{True}(\#\perp )$.

证明

下述的推理过程对所有满足定理 (2.1) 条件的理论 $T$ 都类似, 所以我们只对 $T={\mathsf{PA}}_1$ 证明. 取标准的 Gödel 编号 $\#$, 并且设 $\mathrm{True}(x)$ 定义 $\#\mathrm{Th}({\mathsf{PA}}_1)$.

引理 2.3. Peano 算术 ${\mathsf{PA}}_1$ 满足如下条件, 被称作 Bernays–Hilbert–Löb 条件:

1.	如果 ${\mathsf{PA}}_1⊢\phi$, 那么 ${\mathsf{PA}}_1⊢\mathrm{True}(\#\phi )$.
2.	${\mathsf{PA}}_1⊢\mathrm{True}(\#(\phi \to \chi ))\to (\mathrm{True}(\#\phi )\to \mathrm{True}(\#\chi ))$.
3.	${\mathsf{PA}}_1⊢\mathrm{True}(\#\phi )\to \mathrm{True}(\#\mathrm{True}(\#\phi ))$.

证明. 逐一检验:

1.	这就是引理 (1.3).
2.	只需证明 ${\mathsf{PA}}_1\cup \{\mathrm{True}(\#(\phi \to \chi ))\}\cup \{\mathrm{True}(\#\phi )\}⊢\mathrm{True}(\#\chi )$. 考虑如下语义 “$y$ 作为 Gödel 数所代表的一串序列表示一个证明序列, 在 ${\mathsf{PA}}_1$ 中证明 $x$ 作为 Gödel 数所代表的公式”, 它是可以被一个 ${\Sigma }_1$ 中的公式 $\mathrm{Prov}(x,y)$ 定义的关系. 考虑如下语句$$\mathrm{ModusPonens}(x,y):=\mathrm{Prov}(\#\phi ,x)\wedge \mathrm{Prov}(\#(\phi \to \chi ),y)\to \mathrm{Prov}(\#\chi ,c(x,y)),$$其中 $c(x,y)$ 代表连接 $x$, $y$ 这两个序列 (语义上即是把两个证明拼接成一个证明), 是一个递归可枚举函数, 故可以被 ${\Sigma }_1$ 中的公式定义. 那么$${\mathsf{PA}}_1⊢\mathrm{ModusPonens}(x,y),$$因为 $\mathrm{ModusPonens}(x,y)$ 是属于 ${\Sigma }_1$ 的, 由引理 (1.3) 的证明一样的道理, 只需证明其在 $\mathbb{N}$ 中满足, 但是这就是 $\mathrm{Prov}$ 的定义. 从而进行如下演绎: ∘ $\{\mathrm{True}(\#\phi )\}⊢\exists x\mathrm{Prov}(\#\phi ,x)$. ∘ $\{\mathrm{True}(\#(\phi \to \chi ))\}⊢\exists y\mathrm{Prov}(\#(\phi \to \chi ),y)$. ∘ ${\mathsf{PA}}_1\cup \{\mathrm{True}(\#(\phi \to \chi ))\}\cup \{\mathrm{True}(\#\phi )\}⊢\exists z\mathrm{Prov}(\#\chi ,z)$. ∘ $\{\exists z\mathrm{Prov}(\#\chi ,z)\}⊢\mathrm{True}(\#\chi )$. 这说明结论成立.
3.	事实上我们可以对所有属于 ${\Sigma }_1$ 中的公式 $\psi$ 证明: $${\mathsf{PA}}_1⊢\psi \to \mathrm{True}(\#\psi ).$$由第一条得, 对任意的 $\phi$ 的一个证明, 我们都可以构造出 $\mathrm{True}(\#\phi )$ 的一个证明, 在 Gödel 编号后, 它也定义了一个递归可枚举函数. 而$$\mathrm{Prov}(\#\phi ,x)\to \mathrm{Prov}(\mathrm{True}(\#\phi ),f(x))$$是 ${\Sigma }_1$ 中的公式, 在 $\mathbb{N}$ 里验证便可以得到$${\mathsf{PA}}_1⊢\mathrm{Prov}(\#\phi ,x)\to \mathrm{Prov}(\mathrm{True}(\#\phi ),f(x)).$$从而 ${\mathsf{PA}}_1⊢\mathrm{True}(\#\phi )\to \mathrm{True}(\#\mathrm{True}(\#\phi ))$.

验证完毕.

$\square$

Gödel 第二不完备性定理的证明. 取与 (证明) 中一样的 $\gamma$: $${\mathsf{PA}}_1⊢\gamma \leftrightarrow \neg \mathrm{True}(\#\gamma ).$$进行如下推导:

•	${\mathsf{PA}}_1⊢\gamma \to (\mathrm{True}(\#\gamma )\to \perp )$.
•	${\mathsf{PA}}_1⊢\mathrm{True}(\#(\gamma \to (\mathrm{True}(\#\gamma )\to \perp )))$.
•	${\mathsf{PA}}_1⊢\mathrm{True}(\#\gamma )\to (\mathrm{True}(\#\mathrm{True}(\#\gamma ))\to \mathrm{True}(\#\perp ))$.
•	${\mathsf{PA}}_1⊢\mathrm{True}(\#\gamma )\to \mathrm{True}(\#\perp )$.
•	${\mathsf{PA}}_1⊢\neg \mathrm{True}(\#\perp )\to \neg \mathrm{True}(\#\gamma )$.
•	${\mathsf{PA}}_1⊢\neg \mathrm{True}(\#\perp )\to \gamma$.

如果 ${\mathsf{PA}}_1⊢\neg \mathrm{True}(\#\perp )$, 那么 ${\mathsf{PA}}_1⊢\gamma$, 我们已经在 (证明) 中说明这违背 $T$ 的相容性.

$\square$

Löb 定理

主条目: Löb 定理

Löb 定理把第二不完备性定理的证明更加形式化, 其陈述为:

定理 2.4. 如果一个形式系统 ($T$, $\mathrm{Prov}$) 满足对角线引理:

对于任意只含一个自由公式变元 $X$ 的公式 $F(X)$, 存在语句 $\gamma$ 使得 $T⊢\gamma \leftrightarrow F(\mathrm{Prov}(\gamma ))$,

且满足 Bernays–Hilbert–Löb 条件:

1.	如果 $T⊢\phi$, 那么 $T⊢\mathrm{Prov}(\phi )$.
2.	$T⊢\mathrm{Prov}((\phi \to \chi ))\to (\mathrm{Prov}(\phi )\to \mathrm{Prov}(\chi ))$.
3.	$T⊢\mathrm{Prov}(\phi )\to \mathrm{Prov}(\mathrm{Prov}(\phi ))$.

那么对任意公式 $\psi$, 都有 “如果可以证明 ‘$\psi$ 的可证明性可以推出 $\psi$’, 那么 $\psi$ 就是可以证明的”. 用形式语言说就是$$\begin{array}{c}\underline{T⊢\mathrm{Prov}(\psi )\to \psi }\\ T⊢\psi \end{array}.$$

它蕴涵第二不完备性定理 (2.1), 因为取 $\mathrm{Prov}=\mathrm{True}(\#)$, $\psi =\perp$ 即可.

3影响

(有谁通读不完备性定理历史可以来写写)

术语翻译

Gödel 不完备性定理 • 英文 Gödel’s incompleteness theorems • 德文 gödelsche Unvollständigkeitssätze • 法文 théorèmes d’incomplétude de Gödel