第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