复旦大学：《数理逻辑》课程教学资源（讲义）第8章简化版本的自然数模型.pdf_大学文库

第1节紧致性定理及其应用第8章简化版本的自然数模型 (7)(归纳公理模式)对每一个一阶公式φ,都有对φ的归纳公理 (0)^x(yp(x)→y(S))→Vry(x) (我们把它记为Iy,这在最后一章会用到。) 皮亚诺公理的本意是把自然数的标准模型9=(N,0,S,+,x)的理论公理化。显然,9满足所有的皮亚诺公理。但是我们后面会看到皮亚诺公理的所有逻辑后承与9t (N,O,S,+,x)的理论相差很远。我们称与犷不同构的PA的模型为非标准模型例81.存在一个可数的非标准的PA模型9t 证明:首先扩展语言:添加一个新的常数符号c。令 ∑={0<c,S0<c,S50<c,…} 我们验证任何一个∑∪PA的有穷子集∑0都是可满足的:注意到∑0最多只有有穷条∑中的语句,我们可以找一个充分大的自然数k,并在标准模型中添上c的解释为k即可。PA 中的语句不牵扯到c,因此在标准模型中依然成立依照紧致性定理,Σ∪PA也有一个模型。完全性定理的证明告诉我们这个模型可以取为可数的。我们所要的模型鍁就是该模型在算术语言上的限制。显然9满足PA。剩下验证和9不同构。假定存在一个同构h:9→9。令m=h()。由于 0<,S0<,…,S…0<在模型中成立,因此h诱导出一个从m+1到m m多个的一个单一映射,这与抽屉原则矛盾。 812基数的预备知识紧致性定理为我们提供了一个构造模型的工具。本节中我们将利用这个工具证明一些模型论里面的基本定理。这些定理涉及到基数的概念。因此我们简单介绍一下有关术语,简单到够用为止。有兴趣的读者可以参考集合论教材中的有关部分。我们称两个集合A和B等势如果存在一个从A到B的双射。(在假定选择公理的前提下)每个集合A都具有一个基数或势。基数是用来衡量集合中元素多少的,确切定义我们留给集合论参考书。最小的那些基数为有穷基数,即自然数0,1,2,……。最小的无穷基数为自然数集N的基数,记为。具有基数的集合称为可数集。集合论中有一个经典定理定理82(康托尔)自然数的幂集P(a)是不可数的

第 1 节紧致性定理及其应用第 8 章简化版本的自然数模型 (7) （归纳公理模式）对每一个一阶公式 φ，都有对 φ 的归纳公理： [φ(0) ∧ ∀x(φ(x) → φ(Sx))] → ∀xφ(x)。（我们把它记为 Iφ，这在最后一章会用到。）皮亚诺公理的本意是把自然数的标准模型 N = (N, 0, S, +, ×) 的理论公理化。显然，N 满足所有的皮亚诺公理。但是我们后面会看到皮亚诺公理的所有逻辑后承与 N = (N, 0, S, +, ×) 的理论相差很远。我们称与 N 不同构的 PA 的模型为非标准模型。例 8.1. 存在一个可数的非标准的 PA 模型 M。证明: 首先扩展语言：添加一个新的常数符号 c。令 Σ = {0 < c, S0 < c, SS0 < c, · · · }。我们验证任何一个 Σ ∪ PA 的有穷子集 Σ0 都是可满足的：注意到 Σ0 最多只有有穷条 Σ 中的语句，我们可以找一个充分大的自然数 k，并在标准模型中添上 c 的解释为 k 即可。PA 中的语句不牵扯到 c，因此在标准模型中依然成立。依照紧致性定理，Σ ∪ PA 也有一个模型。完全性定理的证明告诉我们这个模型可以取为可数的。我们所要的模型 M 就是该模型在算术语言上的限制。显然 M 满足 PA。剩下验证 M 和 N 不同构。假定存在一个同构 h : M → M。令 m = h(c A )。由于 0 < cA , S0 < cA , · · · , SS · · · S | {z } m 多个 0 < cA 在模型 M 中成立，因此 h 诱导出一个从 m + 1 到 m 的一个单一映射，这与抽屉原则矛盾。 8.1.2 基数的预备知识紧致性定理为我们提供了一个构造模型的工具。本节中我们将利用这个工具证明一些模型论里面的基本定理。这些定理涉及到基数的概念。因此我们简单介绍一下有关术语，简单到够用为止。有兴趣的读者可以参考集合论教材中的有关部分。我们称两个集合 A 和 B 等势如果存在一个从 A 到 B 的双射。（在假定选择公理的前提下）每个集合 A 都具有一个基数或势。基数是用来衡量集合中元素多少的，确切定义我们留给集合论参考书。最小的那些基数为有穷基数，即自然数 0, 1, 2, · · · 。最小的无穷基数为自然数集 N 的基数，记为 ℵ0。具有基数 ℵ0 的集合称为可数集。集合论中有一个经典定理：定理 8.2 (康托尔). 自然数的幂集 P(ω) 是不可数的。 2

第8章简化版本的自然数模型第1节紧致性定理及其应用著名的连续统假设的一种叙述为:实数集的基数为。最根据康托尔定理,存在不可数集,例如,实数集R。最小的不可数的基数记为N 有穷数的加法和乘法可以自然延伸到无穷基数。事实上,涉及到无穷基数的加法和乘法反而简单了,因为有下面的“吸收定律定理83(基数算术定理).对任何基数和λ,如果κ≤λ并且λ是无穷的,则κ+入=入此外,如果κ≠0,则κ·λ=λ。简而言之,小势被大势吸收。另一个要用到的事实是定理8.4.假设A是一个无穷集。则A上有穷序列的集合Ul∈A与A等势。 813勒文海姆斯寇伦定理有了基数的概念之后,我们就可以叙述下面两个模型论中的基本定理,都称为勒文海姆-斯寇伦定理。首先一个语言L的势定义为 max({L中非逻辑符号}|,No)。例如,集合论的语言和初等数论的语言具有势N,即,都是可数语言。定理85(下行的勒文海姆-斯寇伦定理)令语言L的势为κ并且r为一个L上的一个可满足的公式集。则存在一个满足r的结构,它的势不超过κ。特别地,如果r为一个可数语言上的公式集,并且是可满足的,则存在一个满足r的可数结构。证明:我们给出一个证明概要。考察可满足公式集I,根据可靠性定理,I是相容的。我们按照完全性定理证明的步骤来构造一个r的模型。该模型为一个商结构/E其中的论域为常数扩充后的语言L∪Lc中的项。注意到集合Lc的势等于L中公式集的势κ;所以||的势为κ(在计算公式和项的个数时,我们都用到了定理84)。而结构WE的论域是由中元素的等价类组成的,因此它的势不超过r 给定一个可数语言L。假定L上有一个不可数的结构。根据下行的勒文海姆-斯寇伦定理(用在的理论上),存在一个可数的Th的模型9。因此≡。反过来情形如何呢?即假定L上有一个可数无穷的结构〗,是否能得到一个不可数无穷且与之初等等价的结构呢?注意,假如是有穷的并且L中包含等词,则习题??告诉我们这是不可能的。下面的定理回答了这类问题定理86(上行的勒文海姆-斯寇伦定理).令r为一个势为k的语言上的一个公式集。如果存在一个r的无穷模型,则对每一个基数λ≥κ,都存在基数为λ的r的模型

第 8 章简化版本的自然数模型第 1 节紧致性定理及其应用根据康托尔定理，存在不可数集，例如，实数集 R。最小的不可数的基数记为 ℵ1。著名的连续统假设的一种叙述为：实数集的基数为 ℵ1。有穷数的加法和乘法可以自然延伸到无穷基数。事实上，涉及到无穷基数的加法和乘法反而简单了，因为有下面的“吸收定律”：定理 8.3 (基数算术定理). 对任何基数 κ 和 λ，如果 κ ≤ λ 并且 λ 是无穷的，则 κ + λ = λ。此外，如果 κ ̸= 0，则 κ · λ = λ。简而言之，小势被大势吸收。另一个要用到的事实是：定理 8.4. 假设 A 是一个无穷集。则 A 上有穷序列的集合 ∪ n∈N An 与 A 等势。 8.1.3 勒文海姆 -斯寇伦定理有了基数的概念之后，我们就可以叙述下面两个模型论中的基本定理，都称为勒文海姆 -斯寇伦定理。首先一个语言 L 的势定义为 max(| {L 中非逻辑符号} |, ℵ0)。例如，集合论的语言和初等数论的语言具有势 ℵ0，即，都是可数语言。定理 8.5 (下行的勒文海姆 -斯寇伦定理). 令语言 L 的势为 κ 并且 Γ 为一个 L 上的一个可满足的公式集。则存在一个满足 Γ 的结构，它的势不超过 κ。特别地，如果 Γ 为一个可数语言上的公式集，并且是可满足的，则存在一个满足 Γ 的可数结构。证明: 我们给出一个证明概要。考察可满足公式集 Γ，根据可靠性定理，Γ 是相容的。我们按照完全性定理证明的步骤来构造一个 Γ 的模型。该模型为一个商结构 A/E 其中 A 的论域为常数扩充后的语言 L∪LC 中的项。注意到集合 LC 的势等于 L 中公式集的势 κ；所以 | A | 的势为 κ （在计算公式和项的个数时，我们都用到了定理 8.4）。而结构 A/E 的论域是由 A 中元素的等价类组成的，因此它的势不超过 κ。给定一个可数语言 L。假定 L 上有一个不可数的结构 A。根据下行的勒文海姆 -斯寇伦定理（用在 A 的理论上），存在一个可数的 Th A 的模型 B。因此 A ≡ B。反过来情形如何呢？即假定 L 上有一个可数无穷的结构 B，是否能得到一个不可数无穷且与之初等等价的结构 A 呢？注意，假如 B 是有穷的并且 L 中包含等词，则习题 ?? 告诉我们这是不可能的。下面的定理回答了这类问题。定理 8.6 (上行的勒文海姆 -斯寇伦定理). 令 Γ 为一个势为 κ 的语言上的一个公式集。如果存在一个 Γ 的无穷模型，则对每一个基数 λ ≥ κ，都存在基数为 λ 的 Γ 的模型。 3

第8章简化版本的自然数模型第2节可判定的理论 815斯寇伦悖论现在我们可以叙述斯寇伦悖论:显然集合论的语言是可数的。一方面根据下行的勒文海姆-斯寇伦定理,ZFC有一个可数的模型A。而另一方面,康托尔定理(定理82)是 zFC的定理,所以A中包含一个不可数集,即自然数的幂集P(u)。这是不是一个矛盾斯寇伦悖论的消解我们留给读者自己思考;英文版的维基百科上有很好的解释。通常在集合论的课程中会仔细讨论斯寇伦悖论,因为它对理解绝对性概念很有帮助。斯寇伦构造可数模型的方法在逻辑(尤其是在集合论和模型论)和数学中都有着广泛的应用。最后讲一个“花絮”,据维基百科,斯寇伦本人是一个形式主义者,完全不相信不可数集合的存在,对他来说,著名的勒文海姆-斯寇伦定理谈论的都是没有意义的对象,传说他甚至认为自己的名字与该定理联系在一起是可耻的! 第2节可判定的理论如果一个闭语句集T对语义蕴涵封闭,即对任何闭语句a如果Ta则a∈T,则称T为一个理论。显然,根据完全性定理,理论T也可以被定义成对推演封闭的闭语句集例如,任何一个语言上的所有普遍有效语句就形成一个理论。再如,对任何一个结构 ,Th也是一个理论,这也是我们命名的理由。更一般地,对一个结构类,定义K 的理论为在κ中所有成员内都成立的闭语句,记为Th人,换言之, ThK={o:对所有∈K,}a} 请读者自行验证ThK的确为一个理论定义81.我们称一个理论T为完备的如果对每一个闭语句σ,或者σ∈T或者-σ∈T。例如,对任何结构划,Th则总是完备的。完备的理论还有如下的等价刻画。引理8.1.对相容的理论T来说,下列命题是等价的 1)T是一个完备的理论。 (2)任何T的真扩张T”(即,T≤T")都是不相容的 (3)对任何T的模型都有T=Tha 4)对任何T的模型和都有≡。特别地,ThK是完备的当且仅当任何两个K 中的结构都是初等等价的

第 8 章简化版本的自然数模型第 2 节可判定的理论 8.1.5 斯寇伦悖论现在我们可以叙述斯寇伦悖论：显然集合论的语言是可数的。一方面根据下行的勒文海姆 -斯寇伦定理，ZFC 有一个可数的模型 A。而另一方面，康托尔定理（定理 8.2）是 ZFC 的定理，所以 A 中包含一个不可数集，即自然数的幂集 P(ω)。这是不是一个矛盾呢？斯寇伦悖论的消解我们留给读者自己思考；英文版的维基百科上有很好的解释。通常在集合论的课程中会仔细讨论斯寇伦悖论，因为它对理解绝对性概念很有帮助。斯寇伦构造可数模型的方法在逻辑（尤其是在集合论和模型论）和数学中都有着广泛的应用。最后讲一个“花絮”，据维基百科，斯寇伦本人是一个形式主义者，完全不相信不可数集合的存在，对他来说，著名的勒文海姆 -斯寇伦定理谈论的都是没有意义的对象，传说他甚至认为自己的名字与该定理联系在一起是可耻的! 第 2 节可判定的理论如果一个闭语句集 T 对语义蕴涵封闭，即对任何闭语句 σ 如果 T |= σ 则 σ ∈ T，则称 T 为一个理论。显然，根据完全性定理，理论 T 也可以被定义成对推演封闭的闭语句集。例如，任何一个语言上的所有普遍有效语句就形成一个理论。再如，对任何一个结构 A，Th A 也是一个理论，这也是我们命名的理由。更一般地，对一个结构类 K，定义 K 的理论为在 K 中所有成员内都成立的闭语句，记为 Th K，换言之， Th K = {σ : 对所有 A ∈ K, |=A σ}。请读者自行验证 Th K 的确为一个理论。定义 8.1. 我们称一个理论 T 为完备的如果对每一个闭语句 σ，或者 σ ∈ T 或者 ¬σ ∈ T。例如，对任何结构 A，Th A 总是完备的。完备的理论还有如下的等价刻画。引理 8.1. 对相容的理论 T 来说，下列命题是等价的： (1) T 是一个完备的理论。 (2) 任何 T 的真扩张 T ′（即，T ( T ′）都是不相容的。 (3) 对任何 T 的模型 A 都有 T = Th A。 (4) 对任何 T 的模型 A 和 B 都有 A ≡ B。特别地，Th K 是完备的当且仅当任何两个 K 中的结构都是初等等价的。 5

第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 是 κ-范畴的，则对所有不可数基数 λ，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

第3节只含后继的自然数模型第8章简化版本的自然数模型则T是完备的。证明:根据引理8.1,我们只需证明T的任意两个模型和都初等等价。令和为 T的两个模型。根据(2),它们都是无穷的。无妨设的基数≤λ,的基数≥入(其它情形类似)。根据上行和下行的勒文海姆-斯寇伦定理,存在T的模型￠和父,都具有势 λ,并且Ⅻ≡￠,仍≡D。由条件(1),￠①。因此三￠分≡ 我们就得到≡9。由于同构的概念强于初等等价的概念,也许有人会感到奇怪,为什么乌什-沃特判别法用同构来证明初等等价呢?原因是在数学领域内,尤其是代数中,已经有了大量的证明同构的工具。这些工具让我们避开语言的限制来讨论问题,从而给我们带来方便。根据康托尔定理,无端点的稠密线序的理论T满足乌什-沃特判别法中的条件,因此是完备的。依照引理8.1,T的任何两个模型都是初等等价的,特别地再依照引理82,理论T也是可判定的。有理数和实数这一对线序结构很好地说明了初等等价和同构的区别。一方面它们显然是不同构的,因为它们的基数不同,而另一方面,由于语言的限制,基数不同是无法用序的语言来描述的。从序的一阶性质上看,有理数和实数是无法区分的推论81.理论Th(Q,<)和ACF都是可判定的。第3节只含后继的自然数模型我们现在开始讨论初等数论(或称算术)的模型。尽管我们的目的是标准模型,但对非标准模型的讨论会有助于我们对标准模型的理解,因此,我们也会常常提到和看到非标准模型。我们会先考察一些简化版本的算术理论。一方面是为了循序渐进,逐步加深我们的理解,另一方面我们也通过这些简化版本的理论来介绍一些模型论的基础知识。我们以最简单的结构9s=(N,0,S)开始,语言自然是Cs={0,S}。(我们默认等号≈总是包含在语言中的。)让我们试图来刻画结构9s。最显然的事实应该是S诱导出个以0开头类似于线序的结构,至少没有有限的圈。于是我们考察由下列公式的全称概括所组成的闭语句集。 (S1)0关S (S2)Sx≈Sy→x≈y, (S3)x≈0→3y(x≈Sy), 4n)∧Sn1≈x+1→10≠x 8

第 3 节只含后继的自然数模型第 8 章简化版本的自然数模型则 T 是完备的。证明: 根据引理 8.1，我们只需证明 T 的任意两个模型 A 和 B 都初等等价。令 A 和 B 为 T 的两个模型。根据 (2)，它们都是无穷的。无妨设 A 的基数 ≤ λ，B 的基数 ≥ λ （其它情形类似）。根据上行和下行的勒文海姆 -斯寇伦定理，存在 T 的模型 C 和 D，都具有势 λ，并且 A ≡ C，B ≡ D。由条件 (1)，C ∼= D。因此 A ≡ C ∼= D ≡ B 我们就得到 A ≡ B。由于同构的概念强于初等等价的概念，也许有人会感到奇怪，为什么乌什 -沃特判别法用同构来证明初等等价呢？原因是在数学领域内，尤其是代数中，已经有了大量的证明同构的工具。这些工具让我们避开语言的限制来讨论问题，从而给我们带来方便。根据康托尔定理，无端点的稠密线序的理论 T 满足乌什 -沃特判别法中的条件，因此是完备的。依照引理 8.1，T 的任何两个模型都是初等等价的，特别地， (Q, <Q) ≡ (R, <R)。再依照引理 8.2，理论 T 也是可判定的。有理数和实数这一对线序结构很好地说明了初等等价和同构的区别。一方面它们显然是不同构的，因为它们的基数不同，而另一方面，由于语言的限制，基数不同是无法用序的语言来描述的。从序的一阶性质上看，有理数和实数是无法区分的。推论 8.1. 理论 Th (Q, <) 和 ACFp 都是可判定的。第 3 节只含后继的自然数模型我们现在开始讨论初等数论（或称算术）的模型。尽管我们的目的是标准模型，但对非标准模型的讨论会有助于我们对标准模型的理解，因此，我们也会常常提到和看到非标准模型。我们会先考察一些简化版本的算术理论。一方面是为了循序渐进，逐步加深我们的理解，另一方面我们也通过这些简化版本的理论来介绍一些模型论的基础知识。我们以最简单的结构 NS = (N, 0, S) 开始，语言自然是 LS = {0, S}。（我们默认等号 ≈ 总是包含在语言中的。）让我们试图来刻画结构 NS。最显然的事实应该是 S 诱导出一个以 0 开头类似于线序的结构，至少没有有限的圈。于是我们考察由下列公式的全称概括所组成的闭语句集。 (S1) 0 ̸≈ Sx, (S2) Sx ≈ Sy → x ≈ y, (S3) x ̸≈ 0 → ∃y(x ≈ Sy), (S4.n) ∧ i<n Sxi ≈ xi+1 → x0 ̸≈ xn。 8

第8章简化版本的自然数模型第3节只含后继的自然数模型注意它们在结构9s上显然是成立的,后面我们会证明它们就是Th9s的一组公理令T为上述公理的所有逻辑后承构成的集合。Ts是一个理论。理论T的模型%的一般形式是怎样的呢?显然它必须包含一个同构于(N,0,S)的标准部分”:{02,(S0)3,(S50)3,…}。如果它不包含非标准元素,则=9s。否则,假定它包含某个非标准的元素a∈,则它必须包含{S(a),S"S2a,…},同时根据(S3) 还必须包含a的前驱,a的前驱的前驱,等等。形象地说,一定要包含一条含有a像整数一样的“Z-链”。假如中还有不在这条Z链中的非标准元素b的话,它又会有条包含b的z-链。继续分析下去,整个模型α就可以完全被z链的条数所决定。更精确的做法是,对中的任意两个元素a和b,定义关系a~b如果存在某个自然数n, (S2)y(a)=b或者(S2)y(b)=a。不难验证~是上的一个等价关系;并且每个等价类回或者是标准部分0]~或者是一条Z链。此外,如果两个模型和9具有相同个数的Z-链,由于任何两条Z-链都是同构的,和9也是同构的。于是我们有如下刻画引理83.令为一个Ts的模型。则商集|/~可以写成 {0]~}U{回a:a∈|∧i∈} 其中I是某个指标集。此外,如果另一个s的模型的商集是 {]{小:b∈∧j∈小且指标集I和J的基数相同,则和〗同构。证明:我们只证此外部分,很显然,的标准部分可以一一对应到标准部分,而对Z-链部分,指标集的一一对应自然地诱导出到Z-链部分的一一对应,所以和〗同构推论8.2.T5不是沁o-范畴的,但它是1-范畴的。证明:假设和仍都是T的模型,并且都具有基数1。由于每一条z-链都是可数的, 根据基数算术,两个模型都分别有正好1条z-链。根据引理,结论立得。事实上对所有的不可数基数λ,它都是λ-范畴的。我们前面提到过,这是莫雷定理的个特例。根据乌什-沃特判别法,我们有推论8.3.T5是完备的并且是可判定的。推论8..理论Th9ts等于Ts,因而也是可判定的。证明:因为巧是完备的,对Ts的任何一个模型以,都有Ts=Th则。特别地,挑选 9s即可得到结论

第 8 章简化版本的自然数模型第 3 节只含后继的自然数模型注意它们在结构 NS 上显然是成立的，后面我们会证明它们就是 Th NS 的一组公理。令 TS 为上述公理的所有逻辑后承构成的集合。TS 是一个理论。理论 TS 的模型 A 的一般形式是怎样的呢？显然它必须包含一个同构于 (N, 0, S) 的 “标准部分”： {0 A ,(S0) A ,(SS0) A , · · · }。如果它不包含非标准元素，则 A = NS。否则，假定它包含某个非标准的元素 a ∈ |A|，则它必须包含 {S A (a), S A S A a, · · · }，同时根据 (S3)， A 还必须包含 a 的前驱，a 的前驱的前驱，等等。形象地说，A 一定要包含一条含有 a 像整数一样的“Z- 链”。假如 A 中还有不在这条 Z-链中的非标准元素 b 的话，它又会有一条包含 b 的 Z-链。继续分析下去，整个模型 A 就可以完全被 Z-链的条数所决定。更精确的做法是，对 |A| 中的任意两个元素 a 和 b，定义关系 a ∼ b 如果存在某个自然数 n， (S A ) n (a) = b 或者 (S A ) n (b) = a。不难验证 ∼ 是 |A| 上的一个等价关系；并且每个等价类 [a]∼ 或者是标准部分 [0 A ]∼ 或者是一条 Z-链。此外，如果两个模型 A 和 B 具有相同个数的 Z-链，由于任何两条 Z-链都是同构的，A 和 B 也是同构的。于是我们有如下刻画：引理 8.3. 令 A 为一个 TS 的模型。则商集 |A|/ ∼ 可以写成 {[0 A ]∼} ∪ {[ai ]∼ : ai ∈ |A| ∧ i ∈ I} 其中 I 是某个指标集。此外，如果另一个 TS 的模型 B 的商集是 {[0 B]∼} ∪ {[bj ]∼ : bj ∈ |B| ∧ j ∈ J} 且指标集 I 和 J 的基数相同，则 A 和 B 同构。证明: 我们只证此外部分，很显然，A 的标准部分可以一一对应到 B 标准部分，而对 Z-链部分，指标集的一一对应自然地诱导出到 Z-链部分的一一对应，所以 A 和 B 同构。推论 8.2. TS 不是 ℵ0-范畴的，但它是 ℵ1-范畴的。证明: 假设 A 和 B 都是 TS 的模型，并且都具有基数 ℵ1。由于每一条 Z-链都是可数的，根据基数算术，两个模型都分别有正好 ℵ1 条 Z-链。根据引理，结论立得。事实上对所有的不可数基数 λ，它都是 λ-范畴的。我们前面提到过，这是莫雷定理的一个特例。根据乌什 -沃特判别法，我们有：推论 8.3. TS 是完备的并且是可判定的。推论 8.4. 理论 Th NS 等于 TS，因而也是可判定的。证明: 因为 TS 是完备的，对 TS 的任何一个模型 A，都有 TS = Th A。特别地，挑选 A = NS 即可得到结论。 9

第3节只含后继的自然数模型第8章简化版本的自然数模型 831量词消去法理论Ts的判定性是从它的完备性得到的。如果我们真想判断一个闭语句a是否属于Ts,我们必须把Ts的全部成员(通过列举证明序列)一一列举出来,直到a或=o出现为止。显然这是非常没有效率的。下面讲的量词消去法提供给我们一个更有效率的判定算法。并且它还提供给我们更多的关于可定义集的信息。量词消去是模型论中的一个重要技巧,在代数和理论计算机科学上也都有广泛的应用。定义8.5.我们称一个理论T接受量词消去,如果对任何一个公式φ都存在一个不含量词的公式ψ使得T}φ+v。当然,依照完全性定理,我们也可以等价地说T十p分ψ,但用语义蕴涵的好处是不依赖于证明系统的选取引理84(塔尔斯基).一个理论T接受量词消去当且仅当对每一个具有如下形式的公式p 其中α;或者是一个原子公式,或者是某个原子公式的否定式,都存在一个不含量词的公式v使得T卡φ分。证明:想法是将φ写成前束范式,并将不含量词的部分写成析取范式。对量词的个数进行归纳。细节我们留作习题。定理89.Th9s接受量词消去。从而我们有一个效率更高的判定算法。注:当T=Th时,T}φ分如当且仅当对所有赋值s,(a,s)}φ分υ。我们选取T=Th?而不用Ts(尽管两者相等),原因是我们想在下面的证明中利用模型9s的直观,论证(9s,s)φ比论证Tsy要容易一些。证明:令y:=3x(a0A…∧an)为具有塔尔斯基引理中那种形式的公式。我们只需消去φ中的存在量词即可。 Cs中含x的原子公式的一般形式为:s"u≈S"v,其中u,t或者是0或者是一个变断言1.我们只需处理cx;为S"x≈S"υ或是它的否定的情形,还可以进一步假定v不是x。(证明省略。) 下面我们分两个情形来讨论情形1.所有的a1都是方程式的否定。断言2在这种情形下φ等价于0≈0。(因为对所有赋值s,都有(9ts,s)φ

第 3 节只含后继的自然数模型第 8 章简化版本的自然数模型 8.3.1 量词消去法理论 TS 的判定性是从它的完备性得到的。如果我们真想判断一个闭语句 σ 是否属于 TS，我们必须把 TS 的全部成员（通过列举证明序列）一一列举出来，直到 σ 或 ¬σ 出现为止。显然这是非常没有效率的。下面讲的量词消去法提供给我们一个更有效率的判定算法。并且它还提供给我们更多的关于可定义集的信息。量词消去是模型论中的一个重要技巧，在代数和理论计算机科学上也都有广泛的应用。定义 8.5. 我们称一个理论 T 接受量词消去，如果对任何一个公式 φ 都存在一个不含量词的公式 ψ 使得 T |= φ ↔ ψ。当然，依照完全性定理，我们也可以等价地说 T ⊢ φ ↔ ψ，但用语义蕴涵的好处是不依赖于证明系统的选取。引理 8.4 (塔尔斯基). 一个理论 T 接受量词消去当且仅当对每一个具有如下形式的公式 φ ∃x(α0 ∧ · · · ∧ αn) 其中 αi 或者是一个原子公式，或者是某个原子公式的否定式，都存在一个不含量词的公式 ψ 使得 T |= φ ↔ ψ。证明: 想法是将 φ 写成前束范式，并将不含量词的部分写成析取范式。对量词的个数进行归纳。细节我们留作习题。定理 8.9. Th NS 接受量词消去。从而我们有一个效率更高的判定算法。注：当 T = Th A 时，T |= φ ↔ ψ 当且仅当对所有赋值 s，(A, s) |= φ ↔ ψ。我们选取 T = Th N 而不用 TS（尽管两者相等），原因是我们想在下面的证明中利用模型 NS 的直观，论证 (NS, s) |= φ 比论证 TS ⊢ φ 要容易一些。证明: 令 φ := ∃x(α0 ∧ · · · ∧ αn) 为具有塔尔斯基引理中那种形式的公式。我们只需消去 φ 中的存在量词即可。 LS 中含 x 的原子公式的一般形式为：S mu ≈ S n v，其中 u, v 或者是 0 或者是一个变元。断言 1. 我们只需处理 αi 为 S mx ≈ S n v 或是它的否定的情形，还可以进一步假定 v 不是 x。（证明省略。）下面我们分两个情形来讨论：情形 1. 所有的 αi 都是方程式的否定。断言 2. 在这种情形下 φ 等价于 0 ≈ 0。（因为对所有赋值 s，都有 (NS, s) |= φ。） 10

复旦大学：《数理逻辑》课程教学资源（讲义）第8章 简化版本的自然数模型

复旦大学：《数理逻辑》课程教学资源（讲义）第8章简化版本的自然数模型