第2节完全性定理 第6章哥德尔完全性定理 假如φ为a→B,则 (,s)}(a→B)*当且仅当(,s)≠a*或者(,s)=B 当且仅当ag△或者B∈△, 当且仅当-a∈Δ或者B∈△。 无论ηa∈Δ还是β∈Δ,我们都有Δ(a→B)。根据△对推导的封闭性,我们有 (a→B)∈△。另一方面,如果(a→B)∈△,则或者ag△或者[a∈△并且△}] 因而或者a∈△或者β∈△,再反向倒溯上文的论证,就得到(,s)}(a→B)*。 假如φ为ⅵr,我们证明:(,s)kx”*当且仅当vr∈△(注意我们用了wrv 为(ru)*这一事实。)从左向右,我们先选好c为辛钦公理x→-v中的常数c,然 后有 (l,s)Vx→(l,a)t →(2,s)}(v)由替换引理 →(2,s)(v) vg△ (Vxv)g△因为6∈△并且△对推导封闭 vr∈△ 从右向左,首先利用约束变元替换先选一个公式使得和v的差别仅在于约束变元 (因而联词和量词的个数不变)并且t(t的选法见下文)在φ中可以替换x。我们有 a,s)≠vx*→(a,s)长*对某个t,选好并固定 →(2,s2)长因为v*和φ语义等价 →(,s)≠(φ)*根据替换引理 →Δ根据归纳假设 →Vrg△ →rv∈Δ根据约束变元替换引理。 这就完成了对归纳情形的证明。 小结:我们得到了一个结构和一个赋值s,它们满足Δ里面所有不含等词≈的公 我们下面处理等词。首先看看等词到底带来什么问题。回忆一下我们对等词的解释 的特殊要求。例如,假定我们的语言中本来有常数符号d,我们在添加辛钦公理时,会 把彐r(x≈d→c≈d添加进去,其中c是一个新的常数符号,特别地,c≠d。所以第 2 节 完全性定理 第 6 章 哥德尔完全性定理 假如 φ 为 α → β，则 (A, s) |= (α → β) ∗ 当且仅当 (A, s) ̸|= α ∗ 或者 (A, s) |= β ∗ , 当且仅当 α ̸∈ ∆ 或者 β ∈ ∆, 当且仅当 ¬α ∈ ∆ 或者 β ∈ ∆。 无论 ¬α ∈ ∆ 还是 β ∈ ∆，我们都有 ∆ ⊢ (α → β)。根据 ∆ 对推导的封闭性，我们有 (α → β) ∈ ∆。另一方面，如果 (α → β) ∈ ∆，则或者 α ̸∈ ∆ 或者 [α ∈ ∆ 并且 ∆ ⊢ β]。 因而或者 ¬α ∈ ∆ 或者 β ∈ ∆，再反向倒溯上文的论证，就得到 (A, s) |= (α → β) ∗。 假如 φ 为 ∀xψ，我们证明：(A, s) |= ∀xψ∗ 当且仅当 ∀xψ ∈ ∆ （注意我们用了 ∀xψ∗ 为 (∀xψ) ∗ 这一事实。）从左向右，我们先选好 c 为辛钦公理 ¬∀xψ → ¬ψ x c 中的常数 c，然 后有： (A, s) |= ∀xψ∗ ⇒ (A, sx c ) |= ψ ∗ ⇒ (A, s) |= (ψ ∗ ) x c 由替换引理 ⇒ (A, s) |= (ψ x c ) ∗ ⇒ ψ x c ∈ ∆ ⇒ ¬ψ x c ̸∈ ∆ ⇒ (¬∀xψ) ̸∈ ∆ 因为 θ ∈ ∆ 并且 ∆ 对推导封闭 ⇒ ∀xψ ∈ ∆。 从右向左，首先利用约束变元替换先选一个公式 ϕ 使得 ϕ 和 ψ 的差别仅在于约束变元 （因而联词和量词的个数不变）并且 t（t 的选法见下文）在 ϕ 中可以替换 x。我们有 (A, s) ̸|= ∀xψ∗ ⇒ (A, sx t ) ̸|= ψ ∗ 对某个 t，选好并固定 ⇒ (A, sx t ) ̸|= ϕ ∗ 因为 ψ ∗ 和 ϕ ∗ 语义等价 ⇒ (A, s) ̸|= (ϕ x t ) ∗ 根据替换引理 ⇒ ϕ x t ̸∈ ∆ 根据归纳假设 ⇒ ∀xϕ ̸∈ ∆ ⇒ ∀xψ ̸∈ ∆ 根据约束变元替换引理。 这就完成了对归纳情形的证明。 小结：我们得到了一个结构 A 和一个赋值 s，它们满足 ∆ 里面所有不含等词 ≈ 的公 式。 我们下面处理等词。首先看看等词到底带来什么问题。回忆一下我们对等词的解释 的特殊要求。例如，假定我们的语言中本来有常数符号 d，我们在添加辛钦公理时，会 把 ∃x(x ≈ d) → c ≈ d 添加进去，其中 c 是一个新的常数符号，特别地，c ̸= d。所以 6