第6章哥德尔完全性定理 第1节可靠性定理 定理61(可靠性定理)如果rhφ,则rF 我们把证明分成一些小的步骤。首先注意到:如果rv并且r卡矽→φ,则 r}φ。(为什么?)换句话说,分离规则保持真确性。因此我们只需验证所有公理都是普 遍有效的。 根据习题??,一个公式θ是普遍有效的当且仅当θ是普遍有效的。我们得到 个普遍有效公式的概括仍是普遍有效的。所以我们只要检查六组公理,验证每一组中的公 式都是普遍有效的 习题??还告诉我们,{x(a→B),a}上WxB和当x不在a中自由出现时,a→ vra。因而第三和第四组公理都是普遍有效的。 我们把第一组公理的普遍有效性留做习题。 第五组公理x≈x的普遍有效性是显然的。 我们再来看第六组公理的普遍有效性:x≈y→(a→a),其中a为原子公式并且a 是将α中出现若干个用y替换所得到的。我们只需验证{x≈y,a}}a′。固定一个结 构和赋值s满足(a,s)}x≈y,即,s(x)=s(y)。通过对项t施行归纳(具体步骤省 略),我们可以证明3(1)=3()其中t是将t中出现若干个x用y替换所得到的。如果a 是t1≈t2,则a为t1≈t2,因而(,s)}a当且仅当3(t1)=5(t2)当且仅当3(t1)=(t2) 当且仅当(,s)}a′。类似的证明对形如Pt1…tn的原子公式a也适用。 所以我们只剩下验证第二组替换公理的普遍有效性。我们先证明一个引理。 引理6.I(替换引理)如果项t可以在公式φ中替换变元x,则(a,s)卜φ当且仅 当(,sx) 证明:我们对公式φ施行归纳 初始情形:φ是原子公式。首先利用对项u施行归纳,很容易证明:对任何项u和t, 都有x()=5o()我们这里只证明当φ为Pu12…tn的情形,而把p为a1≈2的
第 6 章 哥德尔完全性定理 第 1 节 可靠性定理 定理 6.1 (可靠性定理). 如果 Γ ⊢ φ，则 Γ |= φ。 我们把证明分成一些小的步骤。首先注意到：如果 Γ |= ψ 并且 Γ |= ψ → φ，则 Γ |= φ。（为什么？）换句话说，分离规则保持真确性。因此我们只需验证所有公理都是普 遍有效的。 根据习题 ??，一个公式 θ 是普遍有效的当且仅当 ∀xθ 是普遍有效的。我们得到：一 个普遍有效公式的概括仍是普遍有效的。所以我们只要检查六组公理，验证每一组中的公 式都是普遍有效的。 习题 ?? 还告诉我们，{∀x(α → β), ∀xα} |= ∀xβ 和当 x 不在 α 中自由出现时，α → ∀xα。因而第三和第四组公理都是普遍有效的。 我们把第一组公理的普遍有效性留做习题。 第五组公理 x ≈ x 的普遍有效性是显然的。 我们再来看第六组公理的普遍有效性：x ≈ y → (α → α ′ )，其中 α 为原子公式并且 α ′ 是将 α 中出现若干个 x 用 y 替换所得到的。我们只需验证 {x ≈ y, α} |= α ′。固定一个结 构 A 和赋值 s 满足 (A, s) |= x ≈ y，即，s(x) = s(y)。通过对项 t 施行归纳（具体步骤省 略），我们可以证明 s(t) = s(t ′ ) 其中 t ′ 是将 t 中出现若干个 x 用 y 替换所得到的。如果 α 是 t1 ≈ t2，则 α ′ 为 t ′ 1 ≈ t ′ 2，因而 (A, s) |= α 当且仅当 s(t1) = s(t2) 当且仅当 s(t ′ 1 ) = s(t ′ 2 ) 当且仅当 (A, s) |= α ′。类似的证明对形如 P t1 . . . tn 的原子公式 α 也适用。 所以我们只剩下验证第二组替换公理的普遍有效性。我们先证明一个引理。 引理 6.1 (替换引理). 如果项 t 可以在公式 φ 中替换变元 x，则 (A, s) |= φ x t 当且仅 当 (A, sx s(t) ) |= φ。 证明: 我们对公式 φ 施行归纳。 初始情形：φ 是原子公式。首先利用对项 u 施行归纳，很容易证明：对任何项 u 和 t， 都有 s(u x t ) = s x s(t) (u)。我们这里只证明当 φ 为 P u1u2 · · · un 的情形，而把 φ 为 u1 ≈ u2 的 1
第2节完全性定理 第6章哥德尔完全性定理 验证留给读者。 (l,s)(Pu1u2…tn) 当且仅当((u1)2),3(u2)2),…,3(un)2)∈P 当且仅当(s(u1,-o(v2),…,5o(un)∈P 当且仅当(,.x0)Pa12…t 归纳情形:我们只处理量词的情形,而把φ为艹ψ或者ψ→θ的情形留给读者。 如果φ为wy并且x不在φ中自由出现。只须注意s和s在出现在φ中的自由变 元上取值相同,还有y就是y,立刻可得知结论成立 剩下的情形为φ为ψyu并且x的确在φ中自由出现。由于t可以在φ中替换x, 我们有y不在t中出现并且t可以在ψ中替换x。所以,对论域||中的任何d都有 3(t)=s(t)。由于x≠y,=vyu。所以 (2, s)Hpi 当且仅当对所有d,(,d)v,根据归纳假定 当且仅当对所有d,(,(s)3()上=v 当且仅当对所有d,(l,(s)上v 当且仅当(x,sxa)上9 这就完成了对替换引理的归纳证明。 返回到对第二组公理可靠性的验证。假定t在φ中可以替换x并且(,s)}ry。我 们需要证明(,s)。我们知道对||中的任意元素d,都有(a,sa)hφo特别地 取d为3(t),我们有(,。xa)上φ。根据替換引理,(,s)F 到此可靠性定理验证完毕。我们叙述可靠性定理的两个常用推论。 推论61.如果}(φ4v),则φ和v语义等价。 推论62.如果r是可满足的,即存在结构以和赋值s满足r中的所有公式,则是相 容的 第2节完全性定理 如果一个一阶语句在所有的模型中都成立,那一定是因为有一个统一的 原因(证明),而不是源于偶然让它在不同的模型内或在不同的情形下因不同 的原因而成立。”一布拉斯1 布拉斯, Andreas blass(1947-),美国逻辑学家,数学家
第 2 节 完全性定理 第 6 章 哥德尔完全性定理 验证留给读者。 (A, s) |= (P u1u2 · · · un) x t 当且仅当 (s((u1) x t ), s((u2) x t ), · · · , s((un) x t )) ∈ P A 当且仅当 (s x s(t) (u1), s x s(t) (u2), · · · , s x s(t) (un)) ∈ P A 当且仅当 (A, sx s(t) ) |= P u1u2 · · · un。 归纳情形：我们只处理量词的情形，而把 φ 为 ¬ψ 或者 ψ → θ 的情形留给读者。 如果 φ 为 ∀yψ 并且 x 不在 φ 中自由出现。只须注意 s 和 s x s(t) 在出现在 φ 中的自由变 元上取值相同，还有 φ x t 就是 φ，立刻可得知结论成立。 剩下的情形为 φ 为 ∀yψ 并且 x 的确在 φ 中自由出现。由于 t 可以在 φ 中替换 x， 我们有 y 不在 t 中出现并且 t 可以在 ψ 中替换 x。所以，对论域 | A | 中的任何 d 都有 s(t) = s y d (t)。由于 x ̸= y，φ x t = ∀yψx t 。所以 (A, s) |= φ x t 当且仅当 对所有 d,(A, s y d ) |= ψ x t , 根据归纳假定 当且仅当 对所有 d,(A,(s y d ) x s(t) ) |= ψ 当且仅当 对所有 d,(A,(s x s(t) ) y d ) |= ψ 当且仅当 (A, sx s(t) ) |= φ。 这就完成了对替换引理的归纳证明。 返回到对第二组公理可靠性的验证。假定 t 在 φ 中可以替换 x 并且 (A, s) |= ∀xφ。我 们需要证明 (A, s) |= φ x t 。我们知道对 | A | 中的任意元素 d，都有 (A, sx d ) |= φ。特别地， 取 d 为 s(t)，我们有 (A, sx s(t) ) |= φ。根据替换引理，(A, s) |= φ x t 。 到此可靠性定理验证完毕。我们叙述可靠性定理的两个常用推论。 推论 6.1. 如果 ⊢ (φ ↔ ψ)，则 φ 和 ψ 语义等价。 推论 6.2. 如果 Γ 是可满足的，即存在结构 A 和赋值 s 满足 Γ 中的所有公式，则 Γ 是相 容的。 第 2 节 完全性定理 “如果一个一阶语句在所有的模型中都成立，那一定是因为有一个统一的 原因（证明），而不是源于偶然让它在不同的模型内或在不同的情形下因不同 的原因而成立。”– 布拉斯1 1布拉斯，Andreas Blass （1947 - ），美国逻辑学家，数学家。 2
第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
第2节完全性定理 第6章哥德尔完全性定理 枚举存在性是由语言的可数性保证的。令1为 vx1921→-(91)a1, 其中c1为第一个不在1中出现的新常数符号。假如我们已经处理完了前k个有序对,并 且定义了辛钦公理{61,O2,…,Ok},则令+1为 xk+142k+1→(k+1)c+1, 其中c+为第一个在1…,9k,9k+1,61,…,k中都不出现的新常数符号。这样不断地 做下去,我们最终得到一个公式集θ={61,2,……}。我们验证rU6仍然是相容的:如 果不相容的话,则根据证明序列的有限性和前面验证的r的相容性,就存在某个m≥0, 使得 rU{61,…,bm+1} 为不相容的。选取最小的这样的m。根据(RAA) rU{61,…,bm} 假设m+1为 ry→-y2o 根据重言规则,我们有 U{61,……,6n} 并且 rU{61,…,bm}+yg 注意到c在表达式左边不出现,根据常数概括定理,我们有 rU{61,…,bm} 这与m的极小性矛盾。 我们在相容公式集r∪θ继续扩张,以得到一个极大相容的公式集Δ,即对任何公式 φ或者φ∈Δ或者(-φ)∈Δ。具体做法与命题逻辑中林登鲍姆引理的证眀完全类似,这 里不再重复。注意任何的极大相容集Δ都对语法后承(或说对推导)封闭:如果△+y, 则相容性告诉我们△Hv所以(-)g△,在根据极大性,就有p∈△。 小结:我们扩充了语言,添加了辛钦公理集θ,并把r∪θ扩充成一个极大相容集 下一步我们将从Δ中“读出”一个新语言LC上的结构,但把等词≈暂时替换成 个新的二元谓词E。(等词的处理将使我们下一步的工作。)结构的定义如下:
第 2 节 完全性定理 第 6 章 哥德尔完全性定理 枚举存在性是由语言的可数性保证的。令 θ1 为 ¬∀x1φ1 → ¬(φ1) x1 ci1 , 其中 ci1 为第一个不在 φ1 中出现的新常数符号。假如我们已经处理完了前 k 个有序对，并 且定义了辛钦公理 {θ1, θ2, · · · , θk}，则令 θk+1 为 ¬∀xk+1φk+1 → ¬(φk+1) xk+1 cik+1 , 其中 cik+1 为第一个在 φ1 · · · , φk, φk+1, θ1, · · · , θk 中都不出现的新常数符号。这样不断地 做下去，我们最终得到一个公式集 Θ = {θ1, θ2, · · · }。我们验证 Γ ∪ Θ 仍然是相容 的：如 果不相容的话，则根据证明序列的有限性和前面验证的 Γ 的相容 性，就存在某个 m ≥ 0， 使得 Γ ∪ {θ1, · · · , θm+1} 为不相容的。选取最小的这样的 m。根据（RAA） Γ ∪ {θ1, · · · , θm} ⊢ ¬θm+1。 假设 θm+1 为 ¬∀xφ → ¬φ x c。 根据重言规则，我们有 Γ ∪ {θ1, · · · , θm} ⊢ ¬∀xφ, 并且 Γ ∪ {θ1, · · · , θm} ⊢ φ x c。 注意到 c 在表达式左边不出现，根据常数概括定理，我们有 Γ ∪ {θ1, · · · , θm} ⊢ ∀xφ, 这与 m 的极小性矛盾。 我们在相容公式集 Γ ∪ Θ 继续扩张，以得到一个极大相容的公式集 ∆，即对任何公式 φ 或者 φ ∈ ∆ 或者 (¬φ) ∈ ∆。具体做法与命题逻辑中林登鲍姆引理的证明完全类似，这 里不再重复。注意任何的极大相容集 ∆ 都对语法后承（或说对推导）封闭：如果 ∆ ⊢ φ， 则相容性告诉我们 ∆ ̸⊢ ¬φ 所以 (¬φ) ̸∈ ∆，在根据极大性，就有 φ ∈ ∆。 小结：我们扩充了语言，添加了辛钦公理集 Θ，并把 Γ ∪ Θ 扩充成一个极大相容集 ∆。 下一步我们将从 ∆ 中“读出”一个新语言 LC 上的结构 A，但把等词 ≈ 暂时替换成 一个新的二元谓词 E。（等词的处理将使我们下一步的工作。）结构 A 的定义如下： 4
第6章哥德尔完全性定理 第2节完全性定理 (a)论域|a为语言Lc上所有项的集合。 (b)定义二元关系E为(u,t)∈E当且仅当公式u≈t属于 (c)对每个m-元谓词符号P,定义n元关系P为 (t1,t2,…,tn)∈P当且仅当Pt2…tn∈△ (d)对每个m元函数符号f,定义为f(t1,t2,…,t)=ft2…tn (e)对每个常数符号c,定义c=co 定义赋值函数s:V→|为等同函数,即对所有的变元U,s(v)=t 引理62.对任意项t,(t)=to对任意公式φ,(,s)y*当且仅当φ∈△,其中φ*是 将φ中的等词用E替换而得到的。 证明:通过对项t施行归纳,不难证明3()=t。细节我们留给读者 我们下面对公式φ中出现的联词和量词的个数k施行归纳,证明(Q,s)g*当且仅 当p∈△ 初始情形:k=0则φ为原子公式。如果φ为Pt1t2…tn,则 当且仅当(a,s)=P1t2…t 当且仅当(3(t1),3(t2),……,s(tn)∈P 当且仅当(t1,t2,…,tn)∈P 当且仅当Pt1t2…tn∈△ 如果φ为u≈t,则 (2,S)p 当且仅当(a,s)F=uEt 当且仅当((u),3(t)∈E2 当且仅当(u,t)∈E2 当且仅当u≈t∈△ 归纳情形:假定我们已经证明了引理对联词和量词个数为k的公式成立。考察某个 联词和量词个数为k+1的公式y。p有三种可能性:,a→B和vx,其中v,a和B 的联词和量词个数小于或等于k 假如φ为—υ,则通常的归纳可以走通,我们略去细节
第 6 章 哥德尔完全性定理 第 2 节 完全性定理 (a) 论域 | A | 为语言 LC 上所有项的集合。 (b) 定义二元关系 E A 为 (u, t) ∈ E A 当且仅当公式 u ≈ t 属于 ∆。 (c) 对每个 n-元谓词符号 P，定义 n-元关系 P A 为 (t1, t2, · · · , tn) ∈ P A 当且仅当 P t1t2 · · ·tn ∈ ∆。 (d) 对每个 n-元函数符号 f，定义 f A 为 f A (t1, t2, · · · , tn) = f t1t2 · · ·tn。 (e) 对每个常数符号 c，定义 c A = c。 定义赋值函数 s : V →| A | 为等同函数，即对所有的变元 v，s(v) = v。 引理 6.2. 对任意项 t，s(t) = t。对任意公式 φ，(A, s) |= φ ∗ 当且仅当 φ ∈ ∆，其中 φ ∗ 是 将 φ 中的等词用 E 替换而得到的。 证明: 通过对项 t 施行归纳，不难证明 s(t) = t。细节我们留给读者。 我们下面对公式 φ 中出现的联词和量词的个数 k 施行归纳，证明 (A, s) |= φ ∗ 当且仅 当 φ ∈ ∆。 初始情形：k = 0 则 φ 为原子公式。如果 φ 为 P t1t2 · · ·tn，则 (A, s) |= φ ∗ 当且仅当 (A, s) |= P t1t2 · · ·tn 当且仅当 (s(t1), s(t2), · · · , s(tn)) ∈ P A 当且仅当 (t1, t2, · · · , tn) ∈ P A 当且仅当 P t1t2 · · ·tn ∈ ∆。 如果 φ 为 u ≈ t，则 (A, s) |= φ ∗ 当且仅当 (A, s) |= uEt 当且仅当 (s(u), s(t)) ∈ E A 当且仅当 (u, t) ∈ E A 当且仅当 u ≈ t ∈ ∆。 归纳情形：假定我们已经证明了引理对联词和量词个数为 k 的公式成立。考察某个 联词和量词个数为 k + 1 的公式 φ。φ 有三种可能性：¬ψ，α → β 和 ∀xψ，其中 ψ, α 和 β 的联词和量词个数小于或等于 k。 假如 φ 为 ¬ψ，则通常的归纳可以走通，我们略去细节。 5