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

第8章简化版本的自然数模型 第1节紧致性定理及其应用 811紧致性定理(复习) 我们的《数理逻辑导论》是以一阶逻辑的紧致性定理为结束的。我们这里复习一下, 定理81(紧致性定理).(a)如果ry,则存在r的某个有穷子集Io使得Io卜φ b)如果r的每个有穷子集Io都是可满足的,则T也是可满足的。 我们也证明了存在自然数的非标准模型。下面我们也复习以下它的证明,不过我们用 皮亚诺公理来叙述。 我们在《导论》中曾经给出了皮亚诺本人版本的皮亚诺公理,但由于在皮亚诺的时 代,逻辑发展还不成熟,因此对公理的叙述是在什么语言上做的,甚至逻辑系统是一阶 的还是二阶的都没有讨论,而只是笼统的给出了在经典数学中够用的公理系统。现在 我们已经学过一阶逻辑,可以把公理叙述得更精确。首先我们在一阶逻辑上讨论算术的 公理系统,规定算术(或初等数论)的语言如下:Car={0,5,+,x,≈}。小于符号≤也 经常被直接包括,或作为被定义的符号而引进,例如,我们可以定义x≤y当且仅当 彐(x+z≈y)。皮亚诺公理系统PA是由下列公式的全称概括所组成的: (1)Sx0 (2)Sr≈S (3)x+0≈x (4)x+Sy≈S(x+y) (5)x×0≈0 (6)x×Sy≈x×y+x

第 8 章 简化版本的自然数模型 第 1 节 紧致性定理及其应用 8.1.1 紧致性定理（复习） 我们的《数理逻辑导论》是以一阶逻辑的紧致性定理为结束的。我们这里复习一下。 定理 8.1 (紧致性定理). (a) 如果 Γ |= φ，则存在 Γ 的某个有穷子集 Γ0 使得 Γ0 |= φ。 (b) 如果 Γ 的每个有穷子集 Γ0 都是可满足的，则 Γ 也是可满足的。 我们也证明了存在自然数的非标准模型。下面我们也复习以下它的证明，不过我们用 皮亚诺公理来叙述。 我们在《导论》中曾经给出了皮亚诺本人版本的皮亚诺公理，但由于在皮亚诺的时 代，逻辑发展还不成熟，因此对公理的叙述是在什么语言上做的，甚至逻辑系统是一阶 的还是二阶的都没有讨论，而只是笼统的给出了在经典数学中够用的公理系统。现在 我们已经学过一阶逻辑，可以把公理叙述得更精确。首先我们在一阶逻辑上讨论算术的 公理系统，规定算术（或初等数论）的语言如下：Lar = {0, S, +, ×, ≈}。小于符号 ≤ 也 经常被直接包括，或作为被定义的符号而引进，例如，我们可以定义 x ≤ y 当且仅当 ∃z(x + z ≈ y)。皮亚诺公理系统 PA 是由下列公式的全称概括所组成的： (1) Sx ̸≈ 0。 (2) Sx ≈ Sy → x ≈ y。 (3) x + 0 ≈ x。 (4) x + Sy ≈ S(x + y)。 (5) x × 0 ≈ 0。 (6) x × Sy ≈ x × y + x。 1

第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

第1节紧致性定理及其应用 第8章简化版本的自然数模型 证明:令%为一个满足r的无穷结构。往语言中添加λ个新的常数符号C={ca:a< ∑={ca关eB:a<B<外 (这里我们假设α,B为序数,但暂时可以理解成指标集的两个不同指标。)则公式集∑Ur 的任意有穷子集∑都是可满足的。因为∑0中至多涉及有穷多个∑中的语句,所以至多 用到有穷多个新常数。由于以是无穷的,所以可以向α中添加这些新常数的解释,使得 不同的常数符号有不同的解释,因而满足Σ。根据紧致性定理,存在一个Σ∪r的模型 仍。再根据下行的勒文海姆-斯寇伦定理,我们可以进一步假定9的基数不超过入,因为 扩张后语言的基数为κ+λ=λ。但任何∑的模型显然至少有基数λ。所以9的基数为入 再把限制在原来的语言上即可。 注:根据勒文海姆-斯寇伦定理,对一个无穷的结构来说,我们无法用一阶语言“完 全”把它描述清楚,这与有穷结构形成对照,参见习题??。 814集合论的公理系统ZFC 集合论的语言L={∈,≈},其中∈是“属于”关系。由于我们不会用到具体的集合 论公理,我们仅仅把集合论的公理系统ZFC的公理名称罗列如下 (1)外延公理 (2)分离公理模式 (3)并集公理 (4)对集公理 (5)幂集公理 (6)无穷公理 (7)替换公理模式 (8)基础公理 (9)选择公理 注意:这里每一条公理(或公理模式中的每一个实例)都是语言L={∈,≈}上的一阶语 句

第 1 节 紧致性定理及其应用 第 8 章 简化版本的自然数模型 证明: 令 A 为一个满足 Γ 的无穷结构。往语言中添加 λ 个新的常数符号 C = {cα : α < λ}。 令 Σ = {cα ̸≈ cβ : α < β < λ}。 （这里我们假设 α, β 为序数，但暂时可以理解成指标集的两个不同指标。）则公式集 Σ∪Γ 的任意有穷子集 Σ0 都是可满足的。因为 Σ0 中至多涉及有穷多个 Σ 中的语句，所以至多 用到有穷多个新常数。由于 A 是无穷的，所以可以向 A 中添加这些新常数的解释，使得 不同的常数符号有不同的解释，因而满足 Σ0。根据紧致性定理，存在一个 Σ ∪ Γ 的模型 B。再根据下行的勒文海姆 - 斯寇伦定理，我们可以进一步假定 B 的基数不超过 λ，因为 扩张后语言的基数为 κ + λ = λ。但任何 Σ 的模型显然至少有基数 λ。所以 B 的基数为 λ， 再把 B 限制在原来的语言上即可。 注：根据勒文海姆 -斯寇伦定理，对一个无穷的结构来说，我们无法用一阶语言“完 全”把它描述清楚，这与有穷结构形成对照，参见习题 ??。 8.1.4 集合论的公理系统 ZFC 集合论的语言 L = {∈, ≈}，其中 ∈ 是“属于”关系。由于我们不会用到具体的集合 论公理，我们仅仅把集合论的公理系统 ZFC 的公理名称罗列如下： (1) 外延公理 (2) 分离公理模式 (3) 并集公理 (4) 对集公理 (5) 幂集公理 (6) 无穷公理 (7) 替换公理模式 (8) 基础公理 (9) 选择公理 注意：这里每一条公理（或公理模式中的每一个实例）都是语言 L = {∈, ≈} 上的一阶语 句。 4

第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