经过几十年的考察，正当集合论被广为接受，成了数学的基础时，1903年罗素（Russell）和策墨罗（Zermelo）几乎同时发现了悖论。罗素悖论是：定义罗素集R为所有不包含自己作为元素的集合：R = { x | x ∉ x }，然后问R是不是属于这个集合？麻烦的是，如果R ∈ R，即R是集合R的元素，依定义有R ∉ R；反之如果R ∉ R，按集合R的定义，R是集合R的元素，即R ∈ R。无论哪一种情况都是矛盾。

为了让这个悖论更通俗易懂，罗素编了个“理发师悖论”：村里的理发师宣布，他给自己不刮胡子的人刮胡子。问他给不给自己刮胡子？R为理发师给刮胡子人的集合，R的成员条件是自己不刮胡子的人，问理发师是否属于这个集合。这就把罗素悖论对应于理发师悖论。

罗素悖论是受1899年康托尔“宇宙集（universal set）”悖论的启发后设计的：设宇宙集U为包含所有集合的集合，问它的势是多少？由康托尔定理知道，集合U的幂集P(U)（即集合中所有子集构成的集合）的势比U的势大，|P(U)|>|U|。但是按定义，集合U包含所有的集合，P(U)的元素都是集合，它当然也包含了集合P(U)的所有元素，所以|U|≥|P(U)|，这产生了矛盾。

康托尔悖论的技术含量不在这逻辑里，他的精华是在康托尔定理的证明中。这定理先假设定理的反命题成立，造成一个自我指涉的悖论来反证。其中的技巧被罗素借用来构造他的悖论。关于罗素悖论和康托尔定理的详细证明请参考看【1】。

集合论的悖论在数学界引起极大的震动，虽然谎言悖论早已知道，人们总是以为是语言歧义引起的，多说几句话就可以澄清了。数学要求极其精确严谨，基础理论中任何的不一致都将导致整个数学系统崩溃。作为数学基础的集合论出现了自相矛盾的现象，这该怎么办？

挑剔疵瑕或编个自圆其说的解释来绕过它？这是糊弄自己。判断是不是悖论，不是按照自己的想象，而是按照大家公认的逻辑和原则。本质的问题没解决，还会以其他的面目出现。

说这两个例子不合法？你必须说出它具体违反了什么规则，才能有效地排除类似的悖论。

禁止自我指涉？生活和数学中有无数的自我指涉，这打击面太宽。科学研究要找出一般的规律和通用的规则，不是仅仅为了解脱眼前的困境来因例设规。基础的修补要保留原来基础上的绝大多数成果，而不是重起炉灶。

康托尔的朴素集合论基于一个非常直观的思想：给定一个属性，等价于定义一个集合包含着具有这种属性的所有个体。这让集合成为非常基本，几乎是自明的概念，从而被广泛接受成为数学的基础。这个思想叫“无限制的抽象原理（unrestricted abstraction）”或者unrestricted comprehension principle，用形式逻辑的公式表示为：

∀u (u ∈ { x | φ(x) } ↔ φ(u)), for all formulae φ(x).

罗素悖论证明了“朴素集合论不相容定理（Inconsistency of Naive Set Theory）”：

任何理论包含有无限制的抽象原理，会产生自相矛盾。

塔斯基定理和它类比的说法是：形式化表达直观自然的真理，将导致自相矛盾。

不相容定理说明我们必须对集合定义加以限制，才能避免悖论。这两个悖论都因自我指涉，在集合和它元素间的包含关系上出现了矛盾。第一个补救方案由罗素和Whitehead作出，叫做“类型理论（type theory）”。他们认为函数的变量是限定在一定类型的，所以定义集合的公式φ(x)的变量也必须受到类型的限制。于是建造了一个类型的层次结构，每个数学对象都属于一个类型，数学对象的类型从底层一直明确定义上来，互不兼容。这样避免了自我指涉。这相似于塔斯基的语言层次结构。实际上塔斯基是受到类型理论的启发，建立起语言层次结构的。所以用类型理论定义的集合，也有塔斯基方案中过多限制，生硬不好用的缺点。

现代数学中最广为接受的是Zermelo-Fraenkel集合论（ZF）。它是个隐层次结构的解决方案，类似于Kripke的真理论，用构造的方法逐步定义集合，从而在集合间分出层次来。由于多数教科书只谈康托尔的朴素集合（naive set），对大多数只了解朴素集合和基本集合论（Basic Set Theory）的人，在悖论出现后，可能会不知所措。

朴素集合论是直观的，给予一个属性的描述，就能定义一个集合。集合的悖论否定了这种简单想法。公理化的集合论通过严格的方式给集合的构造一个约束，来避免这些悖论。ZF用严谨的形式逻辑语言来书写，又因公理化的定义方式，对此不熟悉的人比较难懂。这里用熟知的集合概念，简略剖析一下ZFC【2】的公理和目的，给出一个直观的图像，让大家重拾信心知道趋避。ZF是由下面几个公理组成的。

外延公理（Axiom of extensionality）定义集合相等，是它们有着相同的元素。

正规公理（Axiom of regularity）禁止集合具有循环包含和无限包含链的情况。

空集公理（Axiom of null set）定义了空集的存在。

并集公理（Axiom of union）包含有几个集合中的所有元素，构成一个集合。

幂集公理（Axiom of power set）集合的所有的子集，也构成一个集合。

无穷公理（Axiom of infinity）提供迭代公式来构造一个无穷集合，它对应于自然数集合。

替代公理（Axiom schema of replacement）集合A的映射像F(A)是个集合【3】。这对任何的映射（functional formula）F都有效，所以称为公理的模式。

上面几个公理支撑起ZF集合论。有些ZF的介绍还包含着分类公理和配对公理，但它们都可以从这里推出。对已有朴素集合论知识的人，上面公理的性质都很容易理解。由这些公理导出合法的ZF集合，比朴素集合多的限制只是正规公理和替代公理。正规公理说：非空的集合，必须至少有一个元素它不包含这集合里的其他元素。这样就杜绝了循环包含（如：x∈y & y∈z & z∈x）和无限包含（如：… x3 ∈ x2 ∈ x1 ∈ x0）non-well-founded的情况。这意味着集合系统是个well-founded的阶层结构。替代公理用来从已有的集合产生新的集合。

替代公理和空集公理可以导出著名的“分类公理（Axiom schema of separation）”，它原是在Z里设计为限制“无限制的抽象原理”的核心公理。它类似于替代公理，只不过把这个映射变成是对已知集合A中元素的约束φ(x)，以此来构造（A的子）集合{ x ∈A | φ(x) } 。从而可用类似朴素集合论的方法来定义集合，只要把它局限在已有的集合里，就不必担心会发生悖论。已知的集合包括数学上常见的各种集合。这时无限制的抽象原理在ZF下改变为局限抽象原理：

∀u(u ∈ { x∈A | φ(x) } ↔ φ(u)), for all formulae φ(x) on set A.

有朴素集合论的概念的人，运用分类公理足以定义普通数学应用所需要的集合。只有对数学基础的研究，需要特定公理化集合论特征的集合时才用到替代公理及其他。

替代公理和分类公理必须从已知的集合中生成新的集合。那些初始的集合是从哪里来的？它们是类似于Kripke方案那样逐层构造的。从空集开始迭代地用并集和幂集公理，建立起越来越大的集合系统。空集是最底层，集合的幂集高一个层次，只有高层集合对低一层的集合，存有集合与元素的包含关系。无穷公理说明它们可以高到无穷，并构造了自然数集。并集和替代公理构造的集合填充了每一层，外延公理说明了集合相等的条件。正规公理阻止了低阶集合包含高阶集合的可能，让每个集合呆在这累积层次结构的某一层。这杜绝了罗素集和宇宙集的生成，也就避免了悖论。虽然我们无法确信ZF将来不会再有悖论，但这个隐层次结构已经避免了已知的集合悖论。

在ZF公理里加一个选择公理（AC），便是ZFC。这个AC如同平面几何里的第五公设一样，有了它，就可以用来非构造性地证明许多数学定理，使得现有的数学丰富精彩。没有它则按构造主义主张，只承认能被构造出来的事实才存在。这很可靠，但没有想象力的世界很单调。

选择公理（Axiom of choice）说：在集合的一组互不相交的非空子集里，存在着一个方法能够从每一个子集挑出一个元素来。这个选择公理与Zorn引理，Tukey引理和Zermelo定理互相等价，其中最有应用的是Zermelo定理：任何集合都可以良序化。

隐层次结构的另一种补救方案是Quine（1937）的新基础（New Foundations）集合论（NF），它认为ZF排除过多不至于产生悖论的集合。【4】Quine把无限制的抽象原理改为分层抽象原理（NF comprehension）：

∀u(u ∈ { x | φ(x) } ↔ φ(u)), for all stratified formulae φ(x).

公式φ(x)是分层的（stratified formulae）指存在着一个从公式φ的变量到自然数的映射σ符合这样的关系：对于φ的子公式u ∈ v，则有σ(v) = σ(u)+1，对 u = v 则有 σ(v) = σ(u). 显然罗素悖论中公式x ∉ x是不满足分层的，这也避免了罗素悖论。

现行的几种集合论补救方案都通过限制某些集合的生成，成功地避免的悖论，付出的代价是集合不再像过去那样无所不包，也不再像过去那样简明直观。朴素的集合论就像物理和化学的原子论一样，单纯质朴。集合的悖论如同打破原子不可分的发现一样，颠覆了这个思想。现在形式公理化的描述，像用复杂的基本粒子理论来构造原来单纯的原子。集合论曾以简单直观被视为数学的基础，现在要了解这个基础超越了大多数人的数学训练。这是科学发展的宿命，研究越深入麻烦也越多。

（待续）

【参考资料】

【1】科学网博文，理解数学——逻辑（2）http://blog.sciencenet.cn/blog-826653-709084.html【2】Wikipedia，Zermelo–Fraenkel set theory http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory

【3】Wikipedia Axiom schema of replacement   http://en.wikipedia.org/wiki/Axiom_schema_of_replacement#Axiom_schema_of_collection

【4】SEP，Quine's New Foundations http://plato.stanford.edu/entries/quine-nf/