第6章哥德尔完全性定理 第2节完全性定理 c≈d∈△。可是在我们的结构中,c≈d当且仅当c=d即c=d,也就是c和d 是同一个常数符号,这显然是不对的 我们解决方案是考虑商结构/E,它的定义为α模掉等价关系E。大致上说,就是 把像c,d这样的满足c≈d∈Δ的项等同起来,看成一个东西。问题就解决了。具体细节 如下 引理63.E2是论域|上的一个合同关系,也就是说, 1)E是论域||上的一个等价关系 (2)对语言中的任何一个不是等词的m-元谓词符号P,任何的项t和v(i=1,2,…,n) 如果对所有的i<n,t1E2u,则 (t1,t2,…,tn)∈P蕴涵( un)∈P (3)对语言中的任何一个m-元函数符号∫,任何的项t和v1(i=1,2,…,n)如果对所 有的i≤n,tEu,则 证明:引理的证明本质上是第??章中那些关于等词的内定理。我们留作习题。 对每个||中的元素t,令团表示包含它的等价类。定义商结构/E如下: (a)论域|/E|={团]:t∈},即由t的等价类团形成的集合。 (b)对每个n-元谓词符号P (团],回t2…,tn])∈P/当且仅当(t1,t2,…,tn)∈P3。 (c)对每个n元函数符号f, f(,回tl…,[tn])=[f(t1,t2,…,tn)。 (d)对每个常数符号c,c3/E=(2] 引理64.对任意公式,(/E,S)上φ当且仅当φ∈△,其中赋值S为S(v)=回。 我们可以把S看成由等同赋值s诱导出的赋值。更一般地,每一个赋值r都自然诱 导出一个商结构的赋值R,即对每一个变元U,R()=[r(U)。证明的思路是依照引理62 和商结构的定义,进行惯常的归纳验证第 6 章 哥德尔完全性定理 第 2 节 完全性定理 c ≈ d ∈ ∆。可是在我们的结构 A 中，A |= c ≈ d 当且仅当 c A = d A 即 c = d，也就是 c 和 d 是同一个常数符号，这显然是不对的。 我们解决方案是考虑商结构 A/E，它的定义为 A 模掉等价关系 E A。大致上说，就是 把像 c, d 这样的满足 c ≈ d ∈ ∆ 的项等同起来，看成一个东西。问题就解决了。具体细节 如下： 引理 6.3. E A 是论域 | A | 上的一个合同关系，也就是说， (1) E A 是论域 | A | 上的一个等价关系。 (2) 对语言中的任何一个不是等词的 n-元谓词符号 P，任何的项 ti 和 ui（i = 1, 2, · · · , n） 如果对所有的 i ≤ n，tiE Aui，则 (t1, t2, · · · , tn) ∈ P A 蕴涵 (u1, u2, · · · , un) ∈ P A。 (3) 对语言中的任何一个 n-元函数符号 f，任何的项 ti 和 ui （i = 1, 2, · · · , n）如果对所 有的 i ≤ n，tiE Aui，则 f A (t1, t2, · · · , tn)E A f A (u1, u2, · · · , un)。 证明: 引理的证明本质上是第 ?? 章中那些关于等词的内定理。我们留作习题。 对每个 | A | 中的元素 t，令 [t] 表示包含它的等价类。定义商结构 A/E 如下： (a) 论域 | A/E |= {[t] : t ∈| A |}，即由 t 的等价类 [t] 形成的集合。 (b) 对每个 n-元谓词符号 P， ([t1], [t2], · · · , [tn]) ∈ P A/E当且仅当(t1, t2, · · · , tn) ∈ P A。 (c) 对每个 n-元函数符号 f， f A/E ([t1], [t2], · · · , [tn]) = [f A (t1, t2, · · · , tn)]。 (d) 对每个常数符号 c，c A/E = [c A ]。 引理 6.4. 对任意公式 φ，(A/E, S) |= φ 当且仅当 φ ∈ ∆，其中赋值 S 为 S(v) = [v]。 我们可以把 S 看成由等同赋值 s 诱导出的赋值。更一般地，每一个赋值 r 都自然诱 导出一个商结构的赋值 R，即对每一个变元 v，R(v) = [r(v)]。证明的思路是依照引理 6.2 和商结构的定义，进行惯常的归纳验证。 7