Gödel 完备性定理

Gödel 完备性定理是数理逻辑中的基本定理, 它说明了一阶语言的完备性, 即语义蕴涵与句法蕴涵等价.

通俗来说, Gödel 完备性定理说明了 “所有真的命题都是可证明的”.

1定理

定理 1.1 (Gödel 完备性定理). 设 $\mathcal{L}$ 是一个一阶语言, $\Phi$ 是其中的某个公式集, 而 $\chi$ 是其中的某个公式. 那么我们有: $$\Phi ⊢\chi ⟺\Phi \models \chi .$$

2证明

我们采取 Henkin 的证明.

模型存在定理

首先只需要证明如下的模型存在定理:

定理 2.1 (模型存在定理). 如果语句集 $\Phi$ (句法) 相容, 即 $\Phi /⊢\perp$, 则 $\Phi$ 存在一个模型.

模型存在定理可以推出 Gödel 完备性定理 (1.1). 首先无妨假设 Gödel 完备性定理中的 $\Phi$ 只包含语句: 否则只需要把那些自由出现的变元视作一个新语言 ${\mathcal{L}}^{\prime }$ 中的常数, 而 ${\mathcal{L}}^{\prime }$ 也仅仅只在 $\mathcal{L}$ 上添加这些常数. 然后我们证明:

•	$\Phi ⊢\chi \Rightarrow \Phi \models \chi$ 是明显的: 验证推导规则每一步即可.
•	假设 $\Phi \models \chi$. 则有 $\Phi \cup \{\neg \chi \}$ 没有模型. 由模型存在定理 (2.1), 知 $\Phi \cup \{\neg \chi \}⊢\perp$. 利用排中律和否定规则便得 $\Phi ⊢\chi$.

下面我们证明模型存在定理 (2.1).

Henkin 语言

首先我们需要扩充语言 $\mathcal{L}$ 和语句集 $\Phi$.

在实质性地构造之前, 我们先把 “$=$” 和其公理加进 $\mathcal{L}$. 它不影响证明.

定义 2.2.

•	我们按如下步骤定义 ${\mathcal{L}}^{\ast }$: 1. 对于 $\mathcal{L}$ 中的语句 $\exists x\phi$, 我们定义常数 $c_{(x,\phi )}$. 定义$${\mathcal{L}}^{(1)}=\mathcal{L}\bigsqcup \{c_{(x,\phi )}{\}}_{\exists x\phi \text{ 是语句}}.$$ 2. 定义 ${\mathcal{L}}^{(2)}={\left({\mathcal{L}}^{(1)}\right)}^{(1)}$. 以此类推 ${\mathcal{L}}^{(n)}$. 3. 定义$${\mathcal{L}}^{\ast }=\bigcup _n{\mathcal{L}}^{(n)}.$$ ${\mathcal{L}}^{\ast }$ 被称作 Henkin 语言.
•	对于 ${\mathcal{L}}^{\ast }$ 中的语句 $\exists x\phi$, 记$${\eta }_{(x,\phi )}:=\exists x\phi \to \phi \{x\mapsto c_{(x,\phi )}\}.$$它被称为 Henkin 公理.

引理 2.3. $\Phi \cup \{{\eta }_{(x,\phi )}{\}}_{\exists x\phi \text{ 是语句}}$ 在 ${\mathcal{L}}^{\ast }$ 中相容.

证明. 首先 $\Phi$ 在 ${\mathcal{L}}^{\ast }$ 中相容. 若否, 则 $\Phi {⊢}_{{\mathcal{L}}^{\ast }}\perp$. 从而存在一段演绎使得其叶的后件形如 $\varphi \in \Phi$, 其根的后件是 $\perp$, 每个节点的后件是 ${\mathcal{L}}^{\ast }$ 中的公式. 但是 ${\mathcal{L}}^{\ast }$ 的公式只是 $\mathcal{L}$ 的公式添加一些常数, 所以我们可以把所有出现在节点后件公式中, 却不在 $\mathcal{L}$ 中的常数替换成不出现在这段演绎的变元. 由于叶和根的后件是 $\mathcal{L}$ 中的公式, 所以这个替换不影响叶和根; 但替换之后所有节点的后件都是 $\mathcal{L}$ 的公式, 故 $\Phi {⊢}_{\mathcal{L}}\perp$, 与 $\Phi$ 的相容性矛盾.

其次证明如果 $\Phi$ 是 ${\mathcal{L}}^{\ast }$ 中相容的语句集, 且其中的语句不含 $c_{(x,\phi )}$, 那么 $\Phi \cup \{{\eta }_{(x,\phi )}\}$ 也是 ${\mathcal{L}}^{\ast }$ 中相容的公式集. 若否, 则 $\Phi ⊢\neg \eta$. 通过推导规则便知 $\Phi ⊢\exists x\phi$ 且 $\Phi ⊢\neg \phi \{x\mapsto c_{(x,\phi )}\}$. 因为 $\Phi$ 中的语句不含 $c_{(x,\phi )}$, 利用与第一段同样的替换可得 $\Phi ⊢\neg \phi \{x\mapsto y\}$, 其中 $y$ 是不出现在 $\Phi$ 中的变元. 全称概括告诉我们 $\Phi ⊢\forall y\neg \phi \{x\mapsto y\}$, 即 $\Phi ⊢\neg \exists y\phi \{x\mapsto y\}$. 所以 $\Phi ⊢\neg \exists x\phi$ (由存在列举). 结合 $\Phi ⊢\exists x\phi$ 知这与 $\Phi$ 的相容性矛盾.

从而引理得证: 我们只需从 $\Phi$ 开始, 一步步添加 Henkin 公理, 每一步都利用上一段的论述即证.

$\square$

最后我们利用 Lindenbaum 引理将上述语句集扩充成 ${\mathcal{L}}^{\ast }$ 上的一个完备理论, 记为 ${\Phi }^{\ast }$.

Henkin 模型

定义 2.4. 定义如下 ${\mathcal{L}}^{\ast }$ - 结构:

•	$A={\mathcal{C}}^{\ast }/\sim$, 其中 ${\mathcal{C}}^{\ast }$ 是 ${\mathcal{L}}^{\ast }$ 中所有常数, $\sim$ 是等价关系 $c\sim d⟺{\Phi }^{\ast }⊢c=d$.
•	对于 $n$ 元函数 $f$, $f[A]([c_1],\dots ,[c_n])=c_{(x,\exists xx=f(c_1,\dots ,c_n))}$.
•	对于 $n$ 元谓词 $p$, $([c_1],\dots ,[c_n])\in p[A]⟺{\Phi }^{\ast }⊢p([c_1],\dots ,[c_n])$.

显然此定义是良定的, 且 Henkin 公理 (2.2) 告诉我们常数在此结构下保持不变 (即 $c\sim c_{(x,\exists xx=c)}$).

引理 2.5. 对于任意 ${\mathcal{L}}^{\ast }$ 中的语句 $\phi$, 有$$A\models \phi ⟺{\Phi }^{\ast }⊢\phi .$$

证明. 对 $\phi$ 递推.

•

语句 $\phi$ 最基础的形式是 $p([c_1],\dots ,[c_n])$. 此时 $A\models \phi$ 等价于 $([c_1],\dots ,[c_n])\in p[A]$, 也就是等价于 ${\Phi }^{\ast }⊢\phi$.

•

对形成语句的规则逐一验证 (需要用到 ${\Phi }^{\ast }$ 的完备性), 唯一不平凡的验证是对规则 $\phi =\exists x\chi$ 的验证 ($\forall$ 可以通过 $\neg \exists \neg$ 消去). 如果 ${\Phi }^{\ast }⊢\phi$, 那么 Henkin 公理 (2.2) 说明 ${\Phi }^{\ast }⊢\chi \{x\mapsto c_{(x,\chi )}\}$. 从而便说明 $A$ 是语句 $\chi \{x\mapsto c_{(x,\chi )}\}$ 的模型. 由 $A\models \exists x\chi$ 的定义可以直接得到 $A\models \phi$. 另一方面, 如果 $A\models \phi$, 则存在 $c$ 使得 $A\models \chi \{x\mapsto c\}$, 从而有 ${\Phi }^{\ast }⊢\chi \{x\mapsto c\}$. 存在概括说明 ${\Phi }^{\ast }⊢\phi$.

从而证明了引理.

$\square$

完成证明

模型存在定理 (2.1). 取上述 ${\Phi }^{\ast }$ - 模型 $A$, 由于 $\Phi \subset {\Phi }^{\ast }$, 知 ${\mathcal{L}}^{\ast }$ - 结构 $A$ 也是 $\Phi$ 的模型. 但是 ${\mathcal{L}}^{\ast }$ 是 $\mathcal{L}$ 的扩充, 所以作为 $\mathcal{L}$ - 结构, $A$ 也是 $\Phi$ 的模型.

$\square$

对于不可数语言, 证明完备性定理需要使用 Zorn 引理.

3应用

定理 3.1. 向下 Löwenheim–Skolem 定理: 若可数句子集 $T$ 是一致的, $\mathcal{L}$ 为一个可数语言, 则它有一个论域至多 ${\aleph }_0$ 的模型.

证明. 在完备性定理的证明中, 我们证明了存在极大一致且具有见证性的 $\Delta$ 使得 $T\subseteq \Delta$. $\Delta$ 满足项模型的商模型 $A/\sim$. 显然它的论域 $A/\sim$ 是至多可数的.

$\square$

Lowenheim-Skolem-Tarski 定理要比这要强: 如果一个一阶逻辑语言 $\mathcal{L}$ 的理论存在无穷大的模型模型, 那么这个模型存在一个基数至多为 $|\mathcal{L}|+{\aleph }_0$ 的子模型; 还可以要求, 在不违背模型基数要求的情况下, 原模型中任意元素被包含进子模型内. 这一性质 Henkin models 不满足.

(...)