第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