第6章哥德尔完全性定理 第4节紧致性定理及其应用 第4节紧致性定理及其应用 定理63(紧致性定理)佃a)如果r}φ,则存在r的某个有穷子集Io使得roF b)如果r的每个有穷子集Io都是可满足的,则T也是可满足的。 证明:见习题?? 下面我们看一些紧致性定理的应用 定理6.4.假定语言中包含等词。如果一个闭语句集∑有任意大的有穷模型,则它一定有 个无穷模型。 证明:回忆一下,在第?章第??节中,对任意整数k≥2我们都给出了一个闭语句彐表 达“至少存在k个元素”。例如, 3U13t2t1 3=d3123t3(1t∧t关t3An23) 考察公式集r=∑∪{彐2,彐3,…}。根据假定,I的任何一个有穷子集都是可满足的。紧致 性定理告诉我们,I本身也是可满足的。显然任何满足r的模型都必须是∑的一个无穷 模型。 推论64.固定一个有等词的语言L。L上的所有有穷结构形成的类不是广义初等类EC△ 所有无穷结构形成的类不是初等类EC。 注 1.定理64和推论64很好地阐明了逻辑学是研究手段的极限的主旨。虽然在数学内所 有的有穷结构显然是可以表述的,但如果我们把语言限制在一阶语言上,则我们无 法划清有穷与无穷的界限,哪怕我们允许用无穷多条描述。在习题中我们还会看到 些一阶逻辑无法表达的概念,它们多少都有些“有穷对无穷”的影子在里面。 2.推论64也回答了前面欠下的问题:即所有的无限群不形成一个初等类。 我们再看一个紧致性定理另外一个重要应用,非标准算术模型的存在性,它也回答了 前面欠下的另一个问题,即存在初等等价但不同构的模型。 例6.L.考察标准算术模型=(N,0,S,<,+,)。存在一个可数模型与初等等价但不 同构第 6 章 哥德尔完全性定理 第 4 节 紧致性定理及其应用 第 4 节 紧致性定理及其应用 定理 6.3 (紧致性定理). (a) 如果 Γ |= φ，则存在 Γ 的某个有穷子集 Γ0 使得 Γ0 |= φ。 (b) 如果 Γ 的每个有穷子集 Γ0 都是可满足的，则 Γ 也是可满足的。 证明: 见习题 ??。 下面我们看一些紧致性定理的应用。 定理 6.4. 假定语言中包含等词。如果一个闭语句集 Σ 有任意大的有穷模型，则它一定有 一个无穷模型。 证明: 回忆一下，在第 ?? 章第 ?? 节中，对任意整数 k ≥ 2 我们都给出了一个闭语句 ∃k 表 达“至少存在 k 个元素”。例如， ∃2 =df ∃v1∃v2 v1 ̸≈ v2, ∃3 =df ∃v1∃v2∃v3 (v1 ̸≈ v2 ∧ v2 ̸≈ v3 ∧ v1 ̸≈ v3)。 考察公式集 Γ = Σ ∪ {∃2, ∃3, · · · }。根据假定，Γ 的任何一个有穷子集都是可满足的。紧致 性定理告诉我们，Γ 本身也是可满足的。显然任何满足 Γ 的模型都必须是 Σ 的一个无穷 模型。 推论 6.4. 固定一个有等词的语言 L。L 上的所有有穷结构形成的类不是广义初等类 EC∆。 所有无穷结构形成的类不是初等类 EC。 注： 1. 定理 6.4 和推论 6.4 很好地阐明了逻辑学是研究手段的极限的主旨。虽然在数学内所 有的有穷结构显然是可以表述的，但如果我们把语言限制在一阶语言上，则我们无 法划清有穷与无穷的界限，哪怕我们允许用无穷多条描述。在习题中我们还会看到 一些一阶逻辑无法表达的概念，它们多少都有些“有穷对无穷”的影子在里面。 2. 推论 6.4 也回答了前面欠下的问题：即所有的无限群不形成一个初等类。 我们再看一个紧致性定理另外一个重要应用，非标准算术模型的存在性，它也回答了 前面欠下的另一个问题，即存在初等等价但不同构的模型。 例 6.1. 考察标准 算术模型 A = (N, 0, S, <, +, ·)。存在一个可数模型 B 与 A 初等等价但不 同构。 11