一个激进的经验主义者相信正整数是一个一 个被发现的1！ 让·皮亚杰 世间的精彩，或正来自于其充满着无限的可能。时间上，文明延绵不绝， 从几千年前的刀耕火种到如今的机器轰鸣；空间上，征途是星辰大海，人类从 非洲无垠的草原出发，已快要登上火星。人们一代人接着一代人，前赴后继， 在无限的时空上孜孜不倦地前进着。 然而，于每一个个体，一切又都是有限的。我们的生命不过几十年，能看 过不过几百本书，能结识不过几千人，能行走不过几万里路。无怪乎庄子曾感 慨道“吾生也有涯，而知也无涯。以有涯随无涯，殆已！”追逐无涯，很累啊！ 但是，你我并没有就此被囚禁在一个牢笼之中。纵使我们的肉体没办法突 破有限牢笼的禁锢，我们的思维却可以在无限的海洋中尽情地遨游！我们可以 想象无穷，可以感受它，琢磨它，甚至把握与驯服它！而数学的伟大成就之一， 便是对无穷的征服。 当然，这征途并非一帆风顺。直面无穷的早期，人们真是充满了困惑。比 如下面这个看起来很荒谬的结论，其改编于著名的芝诺（Zeno）悖论2： 悖论 3.1 龟兔赛跑中，若乌龟先跑出一段，那么兔子便永远追不上乌龟。 因为，若要追上，兔子得先跑到乌龟此刻的位置，但此时乌龟已经又跑出去一 小段。如此循环往复无穷无尽，故兔子永远追不上乌龟。 再比如，回到我们之前提过的问题 2.2：什么是 p2。如果你写一个计算机 程序来计算它，随着时间的推移，你会算得越来越精确，源源不断地得到其小 1英文原文：A radical empiricist believe the series of positive integers was discovered one at a time， 语出瑞士心理学家让·皮亚杰（Jean Piaget）。其主要从事认知方面的研究，这句话也是其对人类何以认识 “数”这个概念的诙谐吐槽。显然，我们不是一个一个认识数的，有某种无穷的概念早已天生印刻在我们的认 知之中了。 2“悖论”就是那种感觉不太对但也说不出个所以然的论证。 第 3 章 无穷 数点后越来越多位： . 1.414 . 1.414213 . 1.41421356 . 1.41421356237 ... 这个过程可以永远持续下去，不会停止，不会到头，不会出现循环，不会出现 规律。我们永远也写不完 p2。 难道兔子真的追不上乌龟吗？难道 p2 真的永远也写不出来吗？当然不 是，兔子一眨眼便会超过乌龟，“p2”这个符号已经把 p2 写完了呀！上面的 一切困惑，仅表明一个问题：我们对自己认知无穷本能的理解还非常肤浅，或 者说朴素。 3.1 我 在 说 谎 在越过无穷这座山丘之前，让我们先休息一会，也顺便热热身，来聊一聊 前人的一次伟大但失败的登山尝试。虽然先前的登山者没有越过它，但却留下 了宝贵的经验与财富，让我们这些后来者得以沿着他们踩出的路继续前行。这 位登山先驱的名字叫康托尔（Cantor），他为登山所创立的理论如今称为朴素 集合论（naive set theory）。 顾名思义，一来这个理论通过所谓“集合”来把握无穷，二来这个理论是 “朴素”的。于是，我们先来聊聊“集合”是什么，再来看其为何朴素。如果 你有高中数学的基础，那将会发现本节并没啥新鲜的东西3。 概念 3.2 集合（set）是若干不同对象组成的无序整体。 如果经过第 2 章的熏陶，上面的概念你读来非常不舒服，那就太好了。显 然如此这般的定义充满了模糊，什么叫“整体”、什么叫“对象”、什么叫“无 序”、什么又叫“组成”？但不要担心，我们很快就将在严格的形式基础上毫无 歧义地定义集合，在这里我们先凭借咱们天然的理解能力，在“康托尔创造的 乐园里4”闲庭漫步游览一番。 3在这一节我们不会使用“定义”，因为这里的概念都不属于本书正式搭建的体系。 4语出希尔伯特“任何人都不能把我们从康托尔创造的乐园里赶出去（No one shall expel us from the paradise that Cantor has created for us）”。集合论在创立早期曾招致大量争议与反对，因为其得出的关于 无穷的很多结论太过反直觉，令人震惊，难以接受。希尔伯特作为当时数学界的领袖，说了前面那番话，公 开表示支持康托尔，号召大家沿着他的思路继续探索无穷。顺便说一句，康托尔最终在精神病院抑郁而终。 · 54 · 3.1 我 在 说 谎 概念 3.3 令 A 为一个集合。若 a 是 A 的组成对象之一，我们称 a 是 A 的一个元素（element），记做 a 2 A。若 x 不是 A 的元素，我们记 x /2 A。 让我们来看几个集合的例子： . A = 苹果，香蕉，梨子 . B = x j x 是男人 . C = n j n 是一个偶数 . D = p j p 是一个可以被二整除的奇数 我们用花括号来表示一个集合。定义一个集合的方式有两种，一种是将其元素 一个一个列出来，比如 A。这个方式虽然直截了当，但也有一个问题，即它只 能表达元素个数有限的集合。 概念 3.4 令 A 是一个集合，若其只有有限个元素，我们便称其是一个 有限集（finite set），并将其元素个数记为 jAj。否则称其为无限集5（infinite set）。 另一种定义集合的方式是通过描述集合中元素所具有的性质来确定该集 合，比如 B 就是由全体男人构成的集合，C 就是由全体偶数构成的集合。这 种方式最大的优势在于，可以通过有限来表示无穷！描述性质的汉字肯定是有 限多个，但是其所刻画的对象却可以无穷无尽！上面的例子中，B 依旧是一个 有限集——全世界的男人再多，但终究是有限个，但 C 可就是一个实打实的 无限集了，它由无穷多个偶数构成。 最后我们再来看 D，存在能被二整除的奇数吗？如果我们按照常识来理 解“被二整除”与“奇数”，那么立马会发现，这样的数是不存在的，进而 D 根本不含有任何元素！ 概念 3.5 我们称不含任何元素的集合为空集（empty set），并以符号 . 记之。 概念 3.2 的字虽然不多，但还是有三个词需要强调一下。第一个词是“若 干”，零个、一个、五个、无穷个都叫若干，这一点已经由上述有限集、无限集 和空集阐明了。另一个词是“不同”，集合的组成对象必须是彼此不同的，或 者说相同的对象会被视为一个。比如考虑 f1, 1, 2, 2, 3g，即使不说它不是一个 集合，我们也说它其实就是 f1, 2, 3g。最后一个需要强调的词是“无序”。我们 在书写时不得不按照一个顺序写下集合中的元素（比如上面例子中的 A），但 是这个顺序是无所谓的，f1, 2, 3g 和 f3, 1, 2g 是同样的集合。 5也叫“无穷集”。中文里“无穷”与“无限”“有穷”与“有限”都是可以互换的同义词，我们将不予区分。 · 55 · 第 3 章 无穷 对于一个集合，我们可以通过其元素构成新的集合。 概念 3.6 令 A 为一个集合。若集合 B 的所有元素都是 A 的元素，我们 称 B 是 A 的一个子集（subset），记做 B  A。若 A 中存在元素不属于 B， 那么称 B 是 A 的真子集（proper subset），记为 B . A。 举个例子，如果 A = f1, 2, 3g，那么 f1, 2, 3g  A，f1, 2g . A。 概念 3.7 令 A 为一个集合。A 的所有子集全体构成一个新的集合，称 作 A 的幂集（power set），记做 2A := fX j X  Ag。 还以之前的集合 A 为例，我们有 2A = f., f1g , f2g , f3g , f1, 2g , f1, 3g , f2, 3g , f1, 2, 3gg 它是一个集合的集合，一共有 8 个元素，每个元素是 A 的一个子集。你可能 会好奇为什么要用记号 2A。其实原因很简单，假如 A 是一个有限集且有 n 个 元素，不难发现它的幂集有 2n 个元素。 对于两个集合，我们还可以谈论它们之间的关系。 概念 3.8 令 A,B 为两个集合。 . 二者的公共元素构成一个新的集合，称为它们的交集（intersection）， 记为 A \ B := fx j x 2 A 且 x 2 Bg . 二者的全部元素构成一个新的集合，称为它们的并集（union），记为 A [ B := fx j x 2 A 或 x 2 Bg . A 独有的元素叫做它关于 B 的补集（complement），记为 A n B := fx j x 2 A 且 x /2 Bg 举个例子，比如 A = f1, 2, 3g ,B = f2, 4g，那么 . A \ B = f2g . A [ B = f1, 2, 3, 4g . A n B = f1, 3g 另外，如果我们想把很多个集合 A1,A2,    ,An 交起来6，除了写成 A1 \ A2 \    \ An 6对于并集类似。 · 56 · 3.1 我 在 说 谎 往往还会精炼地写成 n \i=1 Ai 这在表达无穷个集合取交集时尤其方便。最一般的，我们用记号 \ X满足某性质 X 来表示满足某性质的所有集合的交集。 至此，我们便介绍完了朴素集合论中最基本的概念与记号。你可能要问， 然后呢？为什么呢？意义何在呢？不难看出，朴素集合论绝不是第 2 章意义 下的形式语言，它无非就是自然语言的符号化，发明了一些符号用以代表自然 语言的描述，使得我们可以用更加简洁精炼的公式进行表达与演算。诚然，这 已经是一项了不起的成就了——如果你看看《九章算术》中描述的解题过程与 现在机械化的方程求解步骤，便会意识到符号化的巨大价值。但康托尔的贡献 不止于此，朴素集合论的核心在于它为数学提供了一种语言，虽然并非形式语 言，但也强大到足以让我们把握无穷——通过有穷的办法。但我们也将看到， 正是因为它毫无边界地强大，最终摧毁了自己的根基。这一切的核心蕴藏在之 前提到过的那条看上去并不起眼的构造集合的方法之中：通过描述其元素的性 质来构造集合。方法论上，我们称之为普遍概括原则： 原则 3.9 (普遍概括原则 Principle of Universal Comprehension) 给定一 个关于性质的描述 P，我们可以基于此定义一个集合 A，其元素为所有满足 该性质的对象7： A = fx j P(x)g 看起来再自然合理不过了，不是吗？显然，若想要构建一个无穷集，我们 不可能一个一个地罗列元素。普遍概括原则的强大之处便在于它使得我们得 以用有限的字符来概括无限个对象！“所有三角形”寥寥五个字，天下无穷无 尽的三角形尽入吾彀中！得益于此，在进行推理前我们都会先明确研究对象的 性质，利用集合来框定推理的边界，这也正是洞察 2.8 所表达的精神。比如下 面这些，都是基于普遍概括原则构造的集合： . A = x j x 是一个大于零的自然数 7P(x) 可以读作“x 使 P 成立”。所谓“关于性质的描述”，形式地说来，即一个一元谓词。但这里我们 并未在严格建立公理系统，故凭借直觉理解即可。 · 57 · 第 3 章 无穷 . B = x j x 是一个元素个数少于三个的集合 . C = x j x 是一个非空集合 看上去没啥问题吧，让我们来仔细看看这三个例子，关注的重点是它们与 自身的关系。A 的元素是 1, 2, 3, 4, 5 这样的数，但 A 自己是一个数的集合，显 然 A 的元素与 A 本身是八竿子打不着的。B 就不同了，B 的元素可是集合 了——是那些元素个数少于三个的集合。世界上有多少元素个数少于三个的集 合呢？无穷无尽吧，我随手就能写下四个：f1g , f2g , f3g , f4g。于是乎，B 的 元素至少有四个，所以 B 并不是自己本身的元素： B /2 B 是不是感觉有点不对劲了？再来看看 C，它的元素也是集合——是那些非空的 集合。世界上有非空的集合吗？当然有咯！所以 C 是空集吗？当然不是咯！于 是，C 是自己的元素： C 2 C 这里就蕴藏着大问题了！如果你曾经在洗澡的时候琢磨过“我在说谎”这句 话8，那应该能体会到如下我自己的感悟： 洞察 3.10 悖论常源于自指。 当然，至此并没发生什么，C 2 C 没啥问题，但准备工作已经就绪了。我 们发现，基于朴素集合论的体系以及普遍概括原则，我们可以谈论一个集合是 否属于自身。于是，下面这个集合的定义是毫无问题的： R = x j x 是一个不属于自身的集合 翻译成符号也即 R = fx j x /2 xg (3.1) 现在我要问：R 属于自身吗？我们来看一看。如果 R 不属于自身，那么按其 元素的性质，R 应该是 R 中的元素；如果 R 属于自身，那么同样按照其元素 的性质，R 应是一个不属于自身的集合。横竖都不是，这正是“我在说谎”的 翻版啊！其实，这里的 R 正是著名的罗素悖论的符号表示，它的通俗版是这 么说的： 8简单说来，这句话的问题在于，如果我的确在说谎，那么我在说真话并没说谎；如果我没有说谎，那么如 我所说我应该在说谎……总之横竖都不是。 · 58 · 3.1 我 在 说 谎 悖论 3.11 (罗素悖论 Russell’s Paradox) 村子里有一个理发师，他只为不 给自己理发的人理发。那请问，他应该给自己理发吗？ 说实话，这条悖论今天看来似乎也不过尔尔，是问题，但也不至于地震。 但是在当年就不同了，那可是各路英雄豪杰正在雄心勃勃地建模人类理性的年 代。1902 年，当德国数学家弗雷格（Frege）历经十载写成的《算术原理》9第 二卷即将付梓之际，他收到了罗素的来信。信中罗素告诉他，自己在他书中构 建的体系内构造出了矛盾，即罗素悖论。弗雷格尝试对自己的体系进行修复， 但并未成功。最终，第二卷《算术原理》如期出版，但是他补充了一个附录， 介绍了罗素悖论，并不无悲伤地写下了下面这句话10： 令一名学者最为痛心的事莫过于在其理论大厦完工时，它的一块地 基动摇了。 从此，弗雷格结束了自己一手创立的数理逻辑研究，原本计划的《算术原理》 第三卷从未出版，他再也没有发表过任何有价值的成果，拒绝了各种大学讨论 会与学术论坛的邀请，郁郁寡欢，直至终老。 历史自然不是一帆风顺的，登山也并非一片坦途。罗素悖论一方面摧毁了 弗雷格建立的体系，但另一方面也为人们提供了关于人类心智更深刻的理解。 不难发现，症结的根源在于普遍概括原则毫不限制选取对象的边界，一切人类 的想象力所及与不及之处的任何事物，都能被一句短短几个字的描述轻松纳入 所构建的集合之中。平时无伤大雅，但若这个性质涉指了自身，那么如“我在 说谎”般的悖论便无可避免。于是，为了消除悖论与矛盾，我们必须为普遍概 括原则加上边界，是为受限概括原则： 原则 3.12 (受限概括原则 Principle of Restricted Comprehension) 给定 一个集合 Σ 以及一个关于性质的描述 P，我们可以基于此定义一个集合 A， 其元素为 Σ 中所有满足该性质的元素： A = fx j x 2 Σ 且 P(x)g 可以看到它与普遍概括原则 3.9 唯一的区别在于，我们再也不能天马行空 地选取对象了，一切用以构造集合的对象必须来源于一个已事先明确的全集 9德文名为 Grundgesetze der Arithmetik, begriffsschriftlich abgeleitet。 10原文当然是德文，这里的中文译自文献 [8] 第 253 页 Afterword 一章的开头：“Hardly anything more unwelcome can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished.” · 59 · 第 3 章 无穷 Σ！我们的想象力必须被加上边界！为了强调这一点，我们一般将这个全集写 在竖线的前面： A = fx 2 Σ j P(x)g 我们在朴素集合论的短暂停留至此便告一段落。弗雷格与罗素同时期及 后来的数学家们沿着他们的足迹继续前行，终于将被动摇的地基重新加固。其 坚不可破，牢不可摧，至今仍支撑着早已高耸入云的数学大厦。让我们收拾行 囊，离开朴素集合论的泥沼，踏上公理化集合论为我们铺平的康庄大道，将本 章所提到的所有概念、记号与原则，建立在一个严密坚实的形式系统之上！ 3.2 把语言关进笼子 在正式形式化定义集合之前，你不妨先自己来尝试定义一下集合。概念 3.2 是我推敲了良久却仍不满意但也无计可施的措辞。我一开始很想定义说 “集合是一堆东西构成的……”什么呢？“构成的集合”……嘣，不行，这是 在用集合定义集合。还能怎么说呢？用英文我倒还能取巧地定义为“A set is a collection of distinct objects”，巧（狡）妙（猾）地借助了英文中“set”与 “collection”这两个直观上同义的不同单词。其实中文里我也可以说“集合是 一簇各异的对象”，利用“簇”这个“集合”的别名。但种种这般努力后，相 信你也会遗憾地发现，若要用自然语言来定义集合，无法避免模糊与歧义，难 以绕开诉诸同义反复与偷梁换柱。 那要怎么办呢？不知你是否还记得我们曾说过，应通过期望对象所满足的 性质来定义它（洞察 2.7 与洞察 2.8）！对于集合，数学家们精心挑选了不多不 少七个性质，即下面我们将要看到的七条公理11。 定义 3.13 公理化集合论(axiomatic set theory) 是一个建立在谓词逻辑 上的公理系统，其中： . 字母表：增加了一个符号 2； . 语法：增加了一个二元原子谓词 x 2 y； . 公理：下文所定义的空集公理 3.1、无穷公理 3.2、对集公理 3.3、并集 公理 3.4、替换公理 3.5、幂集公理 3.6、基础公理 3.7 七条公理。 11如果你已经熟悉 ZFC 公理集合论，那可能会觉得这里似乎少了三条公理：外延公理、分离公理与选择公 理。不添加外延公理是因为（正如第 2 章脚注 38 所说）我们回避谈论集合相等，而选择在定义 3.17 中定义 等号；不添加分离公理是因为（正如脚注 17 所说）它是空集公理和替换公理的推论；不添加选择公理是暂时 的，当在后面我们需要它时自会补上。 · 60 · 3.2 把语言关进笼子 我们不加定义地直接引入一个毫无意义的形式符号 2，并将通过规定若 干条公理的方式框定它的性质，使得在直观上它将扮演我们熟悉的“属于” 符号。 定义 3.14 在给定解释下，我们将谓词 x 2 y 中变量 x, y 可被赋予的值 称为集合（set）。 这里我们就得仔细说道说道了。集合是什么？是变量可能的赋值。可变量 是能被赋予不特定值的符号（定义 2.50）。那这样一来，任何东西不都成了集 合？！别急，我们知道若一个符号是谓词，那么它在其自由变量的任何赋值下 都必须要成为一个命题（定义 2.51）。因为 x 2 y 是一个二元原子谓词（定义 3.13），故变量 x、y 的论域不是随便的，只有那些使得 x 2 y 成为一个命题的 值才有资格置于 x 与 y 的论域之中！你可能仍然感到纳闷，难道还有不能让 x 2 y 成为命题的赋值？还真有！这又得回到命题的定义了。什么是命题？命 题要么是原子命题，要么是它们通过逻辑连词的连接（定义 2.32）。原子命题 是只能被解释为真或假的符号（定义 2.31），而逻辑连词仅定义了连接后符号 的真值如何依赖各部件，于是我们不难得到，与原子命题一样，命题也是只能 被解释为真或假的符号。进而我们其实证明了： 断言 3.15 在给定解释下，如果符号 x、y 存在赋值 x := a、y := b 使得 符号 a 2 b 并非为真或为假，那么在该解释下至少 a、b 二者之一不是集合。 举个例子，以我们的直觉作为解释，考察两个变量 x 和 y，它们的论域都 是水果。若将 x 赋值为“苹果”，y 赋值为“梨”，那么“苹果 2 梨”会被解 释为“苹果属于梨”，这是一个毫无意义的话，无所谓真假。于是，至少“苹 果”和“梨”二者之一不是集合——当然，它们全都不是集合。 排除了“苹果”是集合似乎无关痛痒，但不知你有没有意识到，借助断言 3.15，我们其实从最一开始就已经剥夺了导致罗素悖论的那个自指的“集合” (3.1) 成为集合的资格！ 断言 3.16 在朴素集合论中构造的集合 (3.1)，即 R = fx j x /2 xg 不是公理集合论允许的集合。 证明 以朴素集合论为解释，将符号 x 2 y 理解为断言“x 属于 y”，并 将 x 与 y 均赋值为 R。我们下面检查此时 x 2 y 是否是一个命题，即是否或 真或假。 · 61 · 第 3 章 无穷 若 x 2 y 为真，这即表明 R 属于 R。但按照 R 的定义，这意味着 R 不 属于 R，矛盾，故 x 2 y 不能为真。 若 x 2 y 为假，这即表明 R 不属于 R。但按照 R 的定义，这意味着 R 属 于 R，又矛盾，故 x 2 y 不能为假。 于是，x 2 y 在该解释下既不能为真，也不能为假，故 R 不是公理集合论 中的集合（断言 3.15）。 我们一个公理还没有提，尚未施加任何额外限制，仅仅通过明确了定义， 便将曾经不可一世的罗素悖论拒之门外。可见正如第 2 章开头所说过的，在开 始研究问题之前明确定义是多么重要！ 其实吧，定义 3.14 直观上就是在说——脑子里把 2 想象成我们期望建模 的“属于”符号——仅那些能够被判断属于关系的两个事物才能被称为集合。 但什么叫“属于”又只可意会不可言传了。接下来，我们便要通过公理的方式 为符号 2 加上限制，使其刻画了直观上“属于”的概念，不然的话它与任意 一个二元谓词就没区别了。 为了说话方便，我们先来定义一些新的记号。 定义 3.17 我们定义如下缩写记号： . x /2 y := :x 2 y . x  y := 8a : (a 2 x ! a 2 y) . x = y := (x  y) ^ (y  x) . x 6= y := :(x = y) . x . y := (x  y) ^ (x 6= y) 这些记号在朴素集合论中都出现过（比如概念 3.6），分别对应“不属 于”“子集”“相等”“不相等”“真子集”，想必直观上你也看得出来。但一定 要知道 /2、、=、. 都不是公理集合论中的符号，它们只是我们用来写下其 中公式时为了偷懒与清晰而定义的缩写。特别的，两个集合相等被定义为它们 包含彼此。 另外，我们再定义一个新的量词： 定义 3.18 令 P 为一个一元谓词，我们定义如下记号12 (91x : P(x)) := (9x : P(x)) ^ (8y : 8z : P(y) ^ P(z) ! y = z) 12也有人会使用记号 .!，但我喜欢此处定义的记号，因为恰好中文里“唯一”一词含有数字“一”，用 .1 很方便记忆。英文中 unique 虽然与 1 有关系，但还是隔了一层，故他们才使用了感叹号罢！ · 62 ·