第2节可判定的理论 第8章简化版本的自然数模型 5)对任何闭语句a和r,如果T}a∨r,则或者Tσ或者T卜r。 证明:练习。 注意:完备的理论并不一定是极大相容的,因为极大相容集需要考虑所有的公式, 而不仅仅是闭语句。 我们先看一个不完备理论的例子,完备的例子稍后再举。这需要一点代数的知识 域的理论是不完备的,因为域可以有不同的特征。 定义8.2.我们称一个理论T是可公理化的如果存在一个可判定的闭语句集∑使得T是∑ 语义后承集,即,T={:∑}a}。如果∑是有穷的,则称T为可有穷公理化的。 例如,特征为0的域的理论是可公理化的,但不可有穷公理化,见习题。 定义8.3.我们称一个理论T为可判定的,如果存在一个算法使得对任何闭语句σ,该算 法都能告诉我们σ是否属于T。 在我们后面讲了哥德尔编码以后,我们可以更精确地定义一个理论T是可判定的, 如果它的编码的集合#T={:σ∈T}是一个递归集。 引理82.任何完备的可公理化的理论都是可判定的。 在递归论部分里,我们证明了如果一个集合和它的补集都是递归可枚举的,则该集合 是递归的。引理82可以视为它的一个特例。两者的证明思路是一样的。假定理论T可公 理化。令∑为T的一个公理集,即,T={:∑}a}={a:∑+a}。由于∑是可判定 的,我们有算法系统地生成所有∑所能证明的公式。利用这个算法,我们可以判断任何 个给定的闭语句τ是否属于T:由于T是完备的,τ和之一迟早会出现在该算法生 成的公式中。那时我们就可以轻易判断r是否属于T。 821入-范畴的理论 定义84.我们称一个理论T为入范畴的,如果对所有T的模型和,=|=A蕴 涵坐仍,即T的所有具有基数入的模型都同构 (1)“范畴的”来源于英文 categorical,也包含“绝对”或“根本”的意思,但早期文献 中把它译成“范畴的”,我们也“从众
第 2 节 可判定的理论 第 8 章 简化版本的自然数模型 (5) 对任何闭语句 σ 和 τ，如果 T ⊢ σ ∨ τ，则或者 T ⊢ σ 或者 T ⊢ τ。 证明: 练习。 注意：完备的理论并不一定是极大相容的，因为极大相容 集需要考虑所有的公式， 而不仅仅是闭语句。 我们先看一个不 完备理论的例子，完备的例子稍后再举。这需要一点代数的知识。 域的理论是不完备的，因为域可以有不同的特征。 定义 8.2. 我们称一个理论 T 是可公理化的 如果存在一个可判定的闭语句集 Σ 使得 T 是 Σ 语义后承集，即，T = {σ : Σ |= σ}。如果 Σ 是有穷的，则称 T 为可有穷公理化的。 例如，特征为 0 的域的理论是可公理化的，但不可有穷公理化，见习题。 定义 8.3. 我们称一个理论 T 为可判定的，如果存在一个算法使得对任何闭语句 σ，该算 法都能告诉我们 σ 是否属于 T。 在我们后面讲了哥德尔编码以后，我们可以更精确地定义一个理论 T 是可判定的， 如果它的编码的集合 ♯ T = {♯σ : σ ∈ T} 是一个递归集。 引理 8.2. 任何完备的可公理化的理论都是可判定的。 在递归论部分里，我们证明了如果一个集合和它的补集都是递归可枚举的，则该集合 是递归的。引理 8.2 可以视为它的一个特例。两者的证明思路是一样的。假定理论 T 可公 理化。令 Σ 为 T 的一个公理集，即，T = {σ : Σ |= σ} = {σ : Σ ⊢ σ}。由于 Σ 是可判定 的，我们有算法系统地生成所有 Σ 所能证明的公式。利用这个算法，我们可以判断任何 一个给定的闭语句 τ 是否属于 T：由于 T 是完备的，τ 和 ¬τ 之一迟早会出现在该算法生 成的公式中。那时我们就可以轻易判断 τ 是否属于 T。 8.2.1 λ-范畴的理论 定义 8.4. 我们称一个理论 T 为λ-范畴的，如果对所有 T 的模型 A 和 B，|A| = |B| = λ 蕴 涵 A ∼= B，即 T 的所有具有基数 λ 的模型都同构。 注： (1) “范畴的”来源于英文 categorical，也包含“绝对”或“根本”的意思，但早期文献 中把它译成“范畴的”，我们也“从众”。 6
第8章简化版本的自然数模型 第2节可判定的理论 (2)显然两个具有不同基数的模型是不可能同构的,因此无限制的范畴性概念没有意 义,λ-范畴是我们的最佳期望。后续课程中我们会讲莫雷定理:令T为一个可数语 言上的一个完备理论。如果对某个不可数基数κ,T是h-范畴的,则对所有不可数 基数λ,T是λ-范畴的。莫雷定理说明对可数语言来说,“不可数范畴性”是有意义 的。 (3)如果T是入范畴的,则T只有唯一的一个基数为λ的模型(在同构的意义下)。对 比一下完备性的概念,如果T是完备的,则T在初等等价的意义下只有唯一的一个 模型。当然,初等等价是比同构弱得多的概念 例8.2.令CE={≈},和等词的理论TE为语言CE上所有普遍有效的闭语句的集合。则 对任何的基数λ,理论TE都是λ-范畴的。 我们再看另一个例子。考察序的语言C<={<,≈}上的一个闭语句集△,它是由包 括线序公理、稠密性、即, 丑xyx≠y, vmvy3z(x<y→(x<z∧z<y) 及无端点,即 Vray<y, Vx3z2< 令T为所有△的语义后承的集合。 定理87(康托尔.任何可数的无端点的稠密线序都同构于(Q,<q),换言之,T是No-范 畴的。 对于每个素数p或P=0,我们用ACF表示特征是p的代数闭域理论。代数中的斯 坦尼兹定理告诉我们对任何特征p,理论ACF都是x1范畴的。 822乌什-沃特判别法 定理88(乌什-沃特判别法)令T为一个可数语言上的理论并满足 (1)对某个无穷基数λ,T是A-范畴的 2)T的所有模型都是无穷的,即T没有有穷模型。 乌什-沃特判别法 Los. Vaught Test乌什, Jerzy los(1920-1998),波兰逻辑学家,数学家;沃特, Robert Vaught (1926-2002),美国逻辑学家,数学家
第 8 章 简化版本的自然数模型 第 2 节 可判定的理论 (2) 显然两个具有不同基数的模型是不可能同构的，因此无限制的范畴性概念没有意 义，λ-范畴是我们的最佳期望。后续课程中我们会讲莫雷定理：令 T 为一个可数语 言上的一个完备理论。如果对某个不可数基数 κ，T 是 κ-范畴的，则对所有不可数 基数 λ，T 是 λ-范畴的。莫雷定理说明对可数语言来说，“不可数范畴性”是有意义 的。 (3) 如果 T 是 λ-范畴的，则 T 只有唯一的一个基数为 λ 的模型（在同构的意义下）。对 比一下完备性的概念，如果 T 是完备的，则 T 在初等等价的意义下只有唯一的一个 模型。当然，初等等价是比同构弱得多的概念。 例 8.2. 令 LE = {≈}，和等词的理论 TE 为语言 LE 上所有普遍有效的闭语句的集合。则 对任何的基数 λ，理论 TE 都是 λ-范畴的。 我们再看另一个例子。考察序的语言 L< = {<, ≈} 上的一个闭语句集 ∆，它是由包 括线序公理、稠密性、即， ∃x∃yx ̸≈ y, ∀x∀y∃z(x < y → (x < z ∧ z < y)); 及无端点，即 ∀x∃y x < y, ∀x∃z z < x。 令 T 为所有 ∆ 的语义后承的集合。 定理 8.7 (康托尔). 任何可数的无端点的稠密线序都同构于 (Q, <Q)，换言之，T 是 ℵ0-范 畴的。 对于每个素数 p 或 p = 0，我们用 ACFp 表示特征是 p 的代数闭域理论。代数中的斯 坦尼兹定理告诉我们对任何特征 p，理论 ACFp 都是 ℵ1-范畴的。 8.2.2 乌什 -沃特判别法 定理 8.8 (乌什 -沃特判别法1 ). 令 T 为一个可数语言上的理论并满足 (1) 对某个无穷基数 λ，T 是 λ-范畴的。 (2) T 的所有模型都是无穷的，即 T 没有有穷模型。 1乌什 -沃特判别法 Łoś-Vaught Test。乌什，Jerzy Łoś（1920 - 1998），波兰逻辑学家，数学家；沃特，Robert Vaught （1926 – 2002），美国逻辑学家，数学家。 7