第2节完全性定理 第6章哥德尔完全性定理 证明:根据引理62,只需证明:(Q/E,S)}φ当且仅当(,s)}φ*。 我们对φ施行归纳,证明下列略微强一点的命题:对任意赋值r,(Q/E,F)卜φ当 且仅当(,r)}φ*,其中R为由r诱导出的赋值 首先,通过对项t施行归纳,很容易证明:对任意项t,R(t)=(t)。而且对所有项 ,r诱导出的赋值为1° 初始情形:φ为原子公式。如果φ为Pt1t2…tn,其中P为不是等词的n-元谓词符 (/E,R)FPt1t2…tn 当且仅当(R(t1),R(t),…,R(tn)∈P3/E 当且仅当((t1),r(t2)小,…,(tn))∈P3/B 当且仅当(F(t1),F(t2,…,元(tn)∈P3 当且仅当(,r)}Pt1t2…tn 如果φ是原子公式t≈t,则 (Q/E,R)Ft≈t 当且仅当R(t)=R(t) 当且仅当[(t)=r() 当且仅当r(t)E(t) 当且仅当(2.,r)(t≈t)。 归纳情形:我们把联词一和→的处理留给读者,只考察φ为xψ的情形 (Q/E,R)Fφ 当且仅当对每一个项u,(a/E,)上 当且仅当对每一个项u,(Q,a)*归纳假定 当且仅当(a,r)waru* 当且仅当(,r)y 这就完成了对引理的归纳证明。 引理6.4似乎完成了完全性定理的证明。但实际上我们做过头了。我们需要的是一个 语言L的结构,即一个定义域为L中符号的(解释)函数,我们得到的是一个扩充后的 语言Lc上的结构。因此我们把结构/E限制在扩充前的语言L上,所得到的结构就是 完全性定理所要的。 8第 2 节 完全性定理 第 6 章 哥德尔完全性定理 证明: 根据引理 6.2，只需证明：(A/E, S) |= φ 当且仅当 (A, s) |= φ ∗。 我们对 φ 施行归纳，证明下列略微强一点的命题：对任意赋值 r，(A/E, R) |= φ 当 且仅当 (A, r) |= φ ∗，其中 R 为由 r 诱导出的赋值。 首先，通过对项 t 施行归纳，很容易证明：对任意项 t，R(t) = [r(t)]。而且对所有项 u，r x u 诱导出的赋值为 Rx [u]。 初始情形：φ 为原子公式。如果 φ 为 P t1t2 · · ·tn，其中 P 为不是等词的 n-元谓词符 号。则 (A/E, R) |= P t1t2 · · ·tn 当且仅当 (R(t1), R(t2), · · · , R(tn)) ∈ P A/E 当且仅当 ([r(t1)], [r(t2)], · · · , [r(tn)]) ∈ P A/E 当且仅当 (r(t1), r(t2), · · · , r(tn)) ∈ P A 当且仅当 (A, r) |= P t1t2 · · ·tn。 如果 φ 是原子公式 t ≈ t ′，则 (A/E, R) |= t ≈ t ′ 当且仅当 R(t) = R(t ′ ) 当且仅当 [r(t)] = [r(t ′ )] 当且仅当 r(t)E A r(t ′ ) 当且仅当 (A, r) |= (t ≈ t ′ ) ∗。 归纳情形：我们把联词 ¬ 和 → 的处理留给读者，只考察 φ 为 ∀xψ 的情形： (A/E, R) |= φ 当且仅当 对每一个项 u， (A/E, Rx [u] ) |= ψ 当且仅当 对每一个项 u， (A, rx u ) |= ψ ∗ 归纳假定 当且仅当 (A, r) |= ∀xψ∗ 当且仅当 (A, r) |= φ。 这就完成了对引理的归纳证明。 引理 6.4 似乎完成了完全性定理的证明。但实际上我们做过头了。我们需要的是一个 语言 L 的结构，即一个定义域为 L 中符号的（解释）函数，我们得到的是一个扩充后的 语言 LC 上的结构。因此我们把结构 A/E 限制在扩充前的语言 L 上，所得到的结构就是 完全性定理所要的。 8