第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