第6章哥德尔完全性定理 第2节完全性定理 接下来我们证明可靠性定理的逆定理一完全性定理。最初的证明是哥德尔在1929年 证明1930年发表的。我们下面采用的证明是辛钦2在1949年给出的。我们只考虑一阶语 言是可数的情形,即语言中所有的符号组成一个可数集。3 定理62(完全性定理) a)如果r9,则rhφ b)任何相容的公式集都是可满足的。 根据引理?,(a)与(b)等价。(虽然引理?!讨论的是命题逻辑,但证明稍加改动便 对一阶逻辑也适用。)所以我们只证明(b)。我们首先考虑语言中没有等词的情况。假定r 是一个相容的公式集。证明的思路与命题逻辑的完全性定理相似。我们首先把T扩充成 个极大相容集Δ还包括一族新的“辛钦公理”,以帮助我们处理量词。所谓辛钦公理 的形式如下 其中c是“新的”常数符号。我们要做的其实是添加彐xv→v,即对每一个存在性的语 句都添加一个直接证据c。我们写成以上的等价形式是因为后面用起来更直接。本质上 说,辛钦公理其实就是量词消去,代价是添加新的常数。有了这样的△之后,我们很容 易“读出”一个满足Δ中(除了带等词的)所有公式的结构和赋值。 首先我们向语言L中添加可数多个新的常数符号C={c0,1,…}。把扩展后的语言 记作LC。我们验证r在新的语言中仍然是相容的。这听起来是显然的,但添加了常数符 号后,公理变多了,我们还是有必要验证一下。(这实际上是后面归纳验证辛钦公理的相 容性的一部分。)假如在扩张语言之后T变得不相容了,则存在(Lc内的)公式B和某 个(Lc内的)从r到B∧-B的证明序列。注意到证明序列中包含的新常数符号为有穷 多。我们可以用常数概括定理把它们都替换成变元,从而得到一个从I到(B∧-β)(在 L中的)证明序列,其中β是从β中把新常数符号替换成变元而得到的。由于β"是L中 的公式,这与r的相容性矛盾。 接下来我们添加所谓辛钦公理,即对所有(Lc中的)公式p和所有的变元x,我们 都向中添加公式 其中c是某个新常数符号。具体做法如下4:固定一个(Lc中)公式和变元有序对(y,x 的枚举 2辛钦, Leon henkin(1921-2006),美国逻辑学家。 3完全性定理对不可数语言也成立,只不过证明要用到选择公理等集合论工具 4另一种常见的做法是:从语言Lo=L出发,添加可数多常数C使得Lo中的公式都有辛钦公理相配,但语言扩展 成L1=Lo∪Co之后,我们还要添新的常数C1使得L1中的公式都有辛钦公理相配,如此下去,我们需要扩充u步才 能达到目的。第 6 章 哥德尔完全性定理 第 2 节 完全性定理 接下来我们证明可靠性定理的逆定理 – 完全性定理。最初的证明是哥德尔 在 1929 年 证明 1930 年发表的。我们下面采用的证明是辛钦 2在 1949 年给出的。我们只考虑一阶语 言是可数的情形，即语言中所有的符号组成一个可数集。3 定理 6.2 (完全性定理). (a) 如果 Γ |= φ，则 Γ ⊢ φ。 (b) 任何相容的公式集都是可满足的。 根据引理 ??，(a) 与 (b) 等价。（虽然引理 ?? 讨论的是命题逻辑，但证明稍加改动便 对一阶逻辑也适用。）所以我们只证明 (b)。我们首先考虑语言中没有等词的情况。假定 Γ 是一个相容的公式集。证明的思路与命题逻辑的完全性定理相似。我们首先把 Γ 扩充成 一个极大相容 集 ∆ 还包括一族新的“辛钦公理”，以帮助我们处理量词。所谓辛钦公理 的形式如下： ¬∀xφ → ¬φ x c , 其中 c 是“新的”常数符号。我们要做的其实是添加 ∃xψ → ψ x c ，即对每一个存在性的语 句都添加一个直接证据 c。我们写成以上的等价形式是因为后面用起来更直接。本质上 说，辛钦公理其实就是量词消去，代价是添加新的常数。有了这样的 ∆ 之后，我们很容 易“读出”一个满足 ∆ 中（除了带等词的）所有公式的结构和赋值。 首先我们向语言 L 中添加可数多个新的常数符号 C = {c0, c1, · · · }。把扩展后的语言 记作 LC。我们验证 Γ 在新的语言中仍然是相容的。这听起来是显然的，但添加了常数符 号后，公理变多了，我们还是有必要验证一下。（这实际上是后面归纳验证辛钦公理的相 容性的一部分。）假如在扩张语言之后 Γ 变得不相容了，则存在（LC 内的）公式 β 和某 个（LC 内的）从 Γ 到 β ∧ ¬β 的证明序列。注意到证明序列中包含的新常数符号为有穷 多。我们可以用常数概括定理把它们都替换成变元，从而得到一个从 Γ 到 (β ′ ∧ ¬β ′ ) （在 L 中的）证明序列，其中 β ′ 是从 β 中把新常数符号替换成变元而得到的。由于 β ′ 是 L 中 的公式，这与 Γ 的相容性矛盾。 接下来我们添加所谓辛钦公理 ，即对所有（LC 中的）公式 φ 和所有的变元 x，我们 都向 Γ 中添加公式 ¬∀xφ → ¬φ x c , 其中 c 是某个新常数符号。具体做法如下4：固定一个（LC 中）公式和变元有序对 (φ, x) 的枚举： (φ1, x1),(φ2, x2), · · · 2辛钦，Leon Henkin (1921 - 2006)，美国逻辑学家。 3完全性定理对不可数语言也成立，只不过证明要用到选择公理等集合论工具。 4另一种常见的做法是：从语言 L0 = L 出发，添加可数多常数 C0 使得 L0 中的公式都有辛钦公理相配，但语言扩展 成 L1 = L0 ∪ C0 之后，我们还要添新的常数 C1 使得 L1 中的公式都有辛钦公理相配，如此下去，我们需要扩充 ω 步才 能达到目的。 3