一，二，三，很多……

选择公理

出于对民主的一贯敬意，我愿意把选择公理理解成“人民要有选择的权利”。这不是你（政府，或者上帝）面对无数个非空的抽象集合时一次从每个集合里都选出一个元；这种强力干涉的独裁手腕是不可能的。我愿意把选择公理理解成，这是那无数个非空的抽象集合们每一个都自发地从自己的元中选举一个出来。当然这跟数学完全没有关系。选择公理的陈述是：

如果 ∀λ∈Λ, A_λ ≠ ∅，则 ∏ A_λ ( λ∈Λ ) ≠ ∅。

这意思是说，如果每个 A_λ 都非空，那么我们给集合 Λ 中的每一个元 λ 对应集合 A_λ 中的一个元，这样的对应是存在的。或者更直白一些，在每个 A_λ 中都选取一个元是可能的。如果一个集合非空，从里面选取一个元当然是可能的。但选择公理保证的是，即使有无限多个集合，甚至是不可数的无限多个，只要每个集合都非空，那我们就可以在一次神秘的操作之后从每个集合里都得到一个元。这中间当然存在逻辑的飞跃。注意在这里我们只知道 A_λ 是集合。如果我们还知道别的一些信息，有时不用选择公理也可以从每个 A_λ 里选出一个元来。比如说假如有无限多双鞋子，我们可以说“从每双鞋中取出左脚穿的那只”，这就没有用到选择公理。但是如果是无限多双袜子，由于袜子是不分左右的，要从每双里取一只出来就难了！

选择公理是非常强有力的公理。首先来看一个简单的应用：

定理。对于非空集合 A、 B，以下两个命题是等价的：
1) 存在从 A 到 B 的单射
2) 存在从 B 到 A 的全射

证明。 1) ⇒ 2) 并不需要借助选择公理。如果存在从 A 到 B 的单射 f，我们当然可以在 f ( A ) 上定义 f 的逆映射。而对于 B ∖ f ( A )，只要在 A 中随便选取一个元，把 B ∖ f ( A ) 都映到那个元就可以。这样定义的从 B 到 A 的映射显然是一个全射。注意这里只做了一次选择，所以是没有借助选择公理的。 2) ⇒ 1) 如果存在从 B 到 A 的全射，则对于 A 的每个元 a， f^-1 ( a ) 都非空。所以根据选择公理我们可以从每个 f^-1 ( a ) 中选出一个元 b_a。把 a 映到 b_a 定义了一个从 A 到 B 的映射，而 f^-1 ( a ) 们显然是互不相交的，所以这是一个单射。（证毕）

在数学中我们常常会想要做无限次的操作。比如说我们想要这么证明“ ℕ 是最小的无限集合”：对任意无限集合 A，显然 A 非空，所以从里面取出一个元 a₀。 A 是无限的，所以 A ∖ { a₀ } 也是无限的，于是又可以从里面取出一个元 a₁，……依此类推，我们就得到了一个从 ℕ 到 A 的单射。这个“证明”的省略号省略得有没有道理？一般来说无限次的操作是不被允许的。我们可以归纳地定义自然数的函数 f ( n )（也就是说，用 f ( 0 ), f ( 1 ), …, f ( k - 1 ) 的值来规定 f ( k )），这是因为本质上对于每一个 n 我们只要经过有限的操作就可以得到 f ( n ) 的值。但是这个“证明”中的并不是一个归纳的定义。所谓“取出一个元”是有任意性的。如果 A 只是一个抽象的集合，我们就没有办法明确规定到底取出的是哪一个元。那么选择公理呢？选择公理保证我们可以做无限次的选出操作。但是选择公理保证的是同时的、相互独立的选出操作，在这里每一个元的选出都依赖于以前做出的选择。所以看起来这个省略号是欠缺说服力的？然而只要稍用一点技巧，像这样的直观论证是可以通过选择公理来正当化的。

定理。 ℕ 是最小的无限集合。

证明。假设集合 A 是无限的，则对于 A 的任意有限子集 U， A ∖ U 都非空。于是根据选择公理，我们可以给每个有限子集 U 对应一个 A ∖ U 中的元。把这元记为 a_U。 ∅ 当然是 A 的有限子集，所以对应了一个元 a₀。现在我们定义把 0 映到 a₀。 { a₀ } 也是 A 的有限子集，所以也对应了一个元 a₁，然后定义把 1 映到 a₁。同样 { a₀, a₁ } 也是 A 的有限子集，所以对应了一个元 a₂, … 一般地，我们把有限子集 { a₀, a₁, …, a_k } 所对应的元记为 a_{k + 1}，然后定义把 k + 1映到 a_{k + 1}。这样就归纳地定义了一个从 ℕ 到 A 的函数，它显然是单射。（证毕）

接下来你也许会想用同样的直观论证来证明“任意两个集合都是可比较的”：从集合 A 中取一个元 a，让它对应集合 B 中的一个元 b。如果 A ∖ { a } 已经是空集，我们就得到了一个单射。而如果 B ∖ { b } 是空集，我们就得到了一个全射。如果都不是，那就可以再分别从 A ∖ { a } 和 B ∖ { b } 中各取出一个元来互相对应，这样一直进行下去，最后总会得到一个单射或者全射。然而遗憾的是，在这里集合 A 可能是不可数的，所以我们的严密论证不能再像前面的证明那样直接地使用归纳的定义了。解决这个问题方法来自于对“数数”这个直观概念中所蕴涵的逻辑的深入发掘，这发掘给我们带来了所谓的“超限归纳法”。使用超限归纳法再加上上面定理的证明中那样的技巧，我们能够得到一个非常具有通用性的框架来把“像这样的直观论证”化成严密的数学论证。

良序集合

良序集合的概念是关于“数出来的自然数”这一概念的扩张，从直观上来说良序集合简直也就是“可以数出来”的。

定义。把满足下列条件的偏序集合 X 称为良序集合： X 的任意非空子集都有最小元。显然良序集合的任意子集也是良序集合。

ℕ 是一个良序集合，这是因为对于 ℕ 的任意非空子集 V，只要从 V 中取出一个元 v，比 v 小的自然数就只有有限个，所以其中当然有一个是 V 的最小元。

定理。良序集合是全序集合。
证明。对于良序集合的任意两个元 a、 b， { a, b} 做成一个子集，这子集有最小元，所以当然 a 与 b 是可比较的。（证毕）

定义。对于一个元 a，如果 a < b 而且不存在满足 a < x < b 的元 x，就把 b 称为 a 的后继。
定理。良序集合除最大元之外的每个元都有后继。
证明。对良序集合的任意元 a，如果 a 不是最大元则集合 { 严格大于 a 的元全体 } 非空，这集合的最小元就是 a 的后继。（证毕）

定义。对于良序集合 X 和 X 的任意元 a，定义 X_a := { x∈X | x < a }，称为 X 的a-切片。显然一个切片 X_a 满足条件“比 X_a 中某个元小的所有元都属于 X_a”。反过来，如果 X 的任意真子集 A 满足这个条件，它就是 X 的一个切片：我们只要取 X ∖ A 的最小元 b，易知 A = X_b。

定理。（超限归纳法）假设对一个良序集合 X 的每个元都规定了一个命题P。这时如果 1) P对于 X 的最小元成立；2) 对于 X 的任意元 a，只要命题对 X_a 的每个元成立，它就对 a 成立。 这两个条件满足，P就一定对 X 的所有元成立。
证明。假设集合 { a∈X | P对 a不成立 } 不为空，就一定有最小元 b。由于P对于 X 的最小元成立，所以 b 不是 X 的最小元。这时切片 X_b 不为空且P对 X_b 的每个元都成立，所以P也应该对 b 成立，矛盾。（证毕）

定理。对于任意良序集合 X：
1) 如果 f: X ← X 是保持顺序不变的单射，则 ∀x∈X, x ≥ f ( x )。
2) ∀a∈X, X 与 X_a（作为偏序集合）不同构。同样 ∀ a, b ∈X, 只要 a、 b 不同， X_a 与 X_b 就不同构。
证明。 1) 假设集合 A := { a∈X | f ( x ) < x } 不为空，取它的最小元 b。我们有 f ( b ) < b，而 f 是保持顺序不变的单射，所以 f ( f ( b ) ) < f ( b )，于是 f ( b ) ∈ A，这和 b 的定义矛盾。 2) 假设有从 X 到 X_a 的同构 f。 X_a 是 X 的子集，所以 f 可以看成是从 X 到 X 的保持顺序不变的单射，并且 f ( a ) ∈X_a 所以 f ( a ) < a，由 1) 这是不可能的。对于 X_a 和 X_b 也是一样。（证毕）

定理。（良序集合的比较定理）对于良序集合 X、 Y，以下三种情况总有唯一一种成立：
1) X 与 Y 同构
2) X 与 Y 的某一切片同构
3) Y 与 X 的某一切片同构

证明。定义 X 的子集 U := { x∈X | X_x 与 Y 的某个切片同构 }。则对于 U 的任意元 u， X_u 就与 Y 的某个切片 Y_y 同构。而根据前定理，这 y 是由 u 所唯一确定的。于是我们规定把 u 映到这样的 y 就定义了一个从 U 到 Y 的映射 f， f 显然是单射且保持顺序不变（这映射 f 相当于是说，如果在所有比 x 小的元上定义了对应，就自然地把这对应扩张到 x 上）。如果 f 是全射且 U = X，当然 X 与 Y 同构；如果 f 是全射但 U 是 X 的真子集，由于 U 显然满足条件“比 U 中某个元小的所有元都属于 U”，所以 U 是 X 的一个切片，于是 Y 与 X 的某一切片同构。而如果 f 不是全射，显然 f ( U ) 是 Y 的一个切片，这时假如 U 也是 X 的真子集则 U 等于一个切片 X_b 并且 X_b 与 Y 的切片 f ( U ) 同构。可是 b∉U，这与 U 的定义矛盾。所以 U 必须等于 X，于是 X 与 Y 的某一切片同构。（证毕）

定理。如果良序集合 X 和 Y 同构，则同构映射是唯一的。

证明。设有两个同构 f、 g，我们用超限归纳法证明 ∀x∈X, f ( x ) = g ( x )：首先 f 和 g 都把 X 的最小元映到 Y 的最小元，所以对 X 的最小元命题成立；然后假设 f 和 g 在切片 X_a 上是一致的，这时由于 f ( X_a ) = g ( X_a ) 是 Y 上某个元 b 的 b-切片，所以 f 和 g 都必须把 a 映到 b。（证毕）

Zorn引理

应用良序集合的理论结合选择公理的技巧，Zorn引理提供了一个把我们的直观论证化成严密数学论证的非常方便的框架。

定义。我们把满足下面条件的偏序集合 A 称为归纳的：对于 A 的任意良序子集 V，在 A 中总有一个元要大于 V 中所有的元。（大于的意思包括等于）

定理。（Zorn引理）任意一个非空的归纳的偏序集合 A 都有极大元。更细致的说，我们从 A 的任意元 x 开始，“数过一个良序集合之后”，总能到达一个极大元。也就是说，对于 A 的任意元 x，总存在一个 A 的良序子集 V 满足： x 是 V 的最小元， V 有最大元，而且那个最大元是 A 的极大元。

证明。从直观上来说，我们可能想这么证明：从 A 中取一个元，如果它已经是极大的那当然好。如果不是，就有比它大的另一个元，像这样不停的取下去就做成了一个良序子集。然后又有比这良序子集大的元，如果它还不是极大，就再取比它大的，这样一直取下去，最后比把取出来的所有这些元都大的应该就是极大元了吧。这论证当然绝不能算严密，但严密的论证本质上也就是这么做的。
对于 A 的任意一个以 x 为最小元的良序子集 T，把比 T 中所有元都大的元的集合记为 S_T。因为 A 是归纳的，所以 S_T 非空。如果 S_T ⊆ T，这也就是说 S_T 中的元比 T 的元都大而其本身又属于 T，这时当然 S_T 中只能有一个元就是 T 的最大元。但 S_T 是比 T 中所有元都大的元的集合，它只有一个 T 的最大元说明 A 中再没有比这个最大元更大的了，因此这个 T 的最大元就是 A 的极大元。如果对于任何 T， S_T都不被包含在 T 里面，则根据选择公理，我们可以给每个 T 对应一个 S_T ∖ T 的元 f ( T )。我们将证明这会导致矛盾。
导致矛盾的战略是，从 x 出发， { x } 是 A 的良序子集，所以对应了一个元 f ( { x } )，把 f ( { x } ) 记为 x₁。然后 { x, x₁ } 也是 A 的良序子集，所以对应了一个 f ( { x, x₁ } )……把所有这些搜集起来，这整个也是一个良序集合，于是又有比它大的新的元，但这和“把所有这些搜集起来”的定义矛盾。严密的论证如下：
把 R 定义为所有满足下列条件 (*) 的 A 的良序子集 X 的集合： X 的最小元为 x 且对于 X 的任意切片 X_a 都有 a = f ( X_a )。我们将证明，对于 R 中任意两个元 X、 Y，要么 X = Y，要么 X 是 Y 的切片或 Y 是 X 的切片。这样一来把 R 中所有元合并起来就仍然是一个良序子集，对这个良序子集 T 定义了一个 f ( T )， T ∪ { f ( T ) } 也满足条件 (*) 所以属于 R，但 f ( T ) 又不是 T 的元，这和 T 的定义是矛盾的。
至于为什么对于 R 中任意两个元 X、 Y，要么 X = Y，要么 X 是 Y 的切片或 Y 是 X 的切片，这是因为由良序集合的比较定理可得要么 X 和 Y 同构，要么 X 和 Y 的切片同构或 Y 和 X 的切片同构，不妨设 X 和 Y 同构，这时设同构映射为 h: X → Y，我们用超限归纳法证明 h 是恒等映射：首先 X 和 Y 的最小元都是 x，所以命题对最小元成立。然后假设在切片 X_s 上 h 是恒等映射，设 h ( X_s ) 是 Y 的 t-切片，由于 X 和 Y 都满足条件 (*)，所以 s = f ( X_s )， t = f ( h ( X_s ) ) = f ( X_s )，所以 t = s，而 h 是同构所以必须把 s 映到 t。（证毕）

Zorn引理的应用非常广泛，单在集合论里就做出强有力的结论。

定理。（Zermelo的良序定理）对于任意集合 A 都存在适当的顺序使得 A 成为良序集合。

证明。考虑所有这样的有序对 ( U, ≤ )：其中 U 是 A 的子集而 ≤ 是 U 上的一个良序。对任意两个 ( U, ≤₁ )、( V, ≤₂ )，我们说 ( U, ≤₁ ) 比 ( V, ≤₂ )“小”当且仅当 U、 V 包括良序结构完全相等或者 U 是 V 的切片。这是一个归纳的偏序关系，所以有极大元 ( W, ≤ )。如果 W 不等于 A，在 A ∖ W 上任选一元 a，在 W ∪ { a } 上定义顺序“W 上保持已有顺序不变， a 大于所有的元”这就做成了一个良序集合而且 W 是它的切片。这和 W 的极大性矛盾。（证毕）

推论。任意两个集合都是可比较的。这由良序集合的比较定理即得。

推论。对于任意集合 A，都存在集合 B，其浓度严格大于 A，并且是所有浓度严格大于 A 的集合中浓度最小的。

证明。 X := ℘ ( A ) 的浓度严格大于 A，由Zermelo的良序定理可以把 X 看成良序集合，X 的子集 { x∈X | X_x 的浓度严格大于A } 如果非空就取其最小元 b 的切片 X_b、否则的话取集合 X，就是满足条件的集合 B。这是因为对于任意浓度严格比 A 大的集合 C，由Zermelo的良序定理把它看成良序集合，再由良序集合的比较定理得要么 B 与 C 同构，要么 B 与 C 的切片同构或反之，而由 B 的定义， C 与 B 的切片同构是不可能的。（证毕）

定理。对于任意无限集合 A，都有 A ~ A ∐ A ~ A × A。

证明。对于无限集合 A，由于 ℕ 是最小的无限集合，因此可以在 A 中找出一个子集 V₁ 与 ℕ 同等。如果 A ∖ V₁ 仍然是无限的，又可以在里面找出一个子集 V₂ 与 ℕ 同等，依此类推，最后总可以把 A 分成一些与 ℕ 同等的部分和一个有限集合（这是直观论证，严密论证当然是用Zorn引理：考虑所有这样的有序对 ( U, ∐ )：其中 U 是 A 的子集，∐ 是把 U 分成一些与 ℕ 同等的部分的一个分割。定义 ( U, ∐₁ ) 与 ( V, ∐₂ ) 的大小关系为，如果 U 在分割 ∐₁ 下的每一部分，要么正好是 V 在分割 ∐₂ 下的一部分，要么与 V 不相交。这时就说 ( V, ∐₂ ) 比 ( U, ∐₁ ) 小。确认这是归纳的偏序关系，并且其极大元正是把 A 分成了一些与 ℕ 同等的部分和一个有限集合），把有限集合“吸收”到某个与 ℕ 同等的部分里，于是 A 就被分成了一些与 ℕ 同等的部分的非交和。由于 ℕ ~ ℕ ∐ ℕ，所以 A ~ A ∐ A。
要证明 A ~ A × A，考虑所有这样的有序对 ( U, f )：其中 U 是 A 的子集，f 是一个把 U × U 映到 U 上的一一映射。（这样的有序对存在，因为 A 是无限的所以包含 ℕ，而 ℕ ~ ℕ × ℕ）我们说 ( U, f ) 比 ( V, g ) 小，如果 V 包含 U 并且在 U × U 上 f 与 g 相同。这是一个偏序，它是归纳的因为如果 { ( U_i, f_i ) } 是良序子集，我们就可以定义从 ( ∪ U_i ) × ( ∪ U_i ) 到 ∪ U_i 的一一映射。根据Zorn引理，存在一个极大元 ( W, h )，这时如果 A ∖ W 的浓度大于 W，就可以找到一个 W’ ⊆ A ∖ W 与 W 浓度相同。我们有 ( W’ × W ) ∐ ( W × W’ ) ∐ ( W’ × W’ ) ~ W’ ∐ W’ ~ W’，而由于 ( W’ ∐ W ) × ( W’ ∐ W ) = ( W × W ) ∐ ( W’ × W ) ∐ ( W × W’ ) ∐ ( W’ × W’ )，所以我们可以定义这样一个有序对 ( W’ ∐ W, h’ )： h’ 把 W × W 像 h 一样地映到 W，而把 ( W’ × W ) ∐ ( W × W’ ) ∐ ( W’ × W’ ) 一一对应到 W’。这样就定义了一个从 ( W’ ∐ W ) × ( W’ ∐ W ) 到 W’ ∐ W 的一一对应，并且这样的 ( W’ ∐ W, h’ ) 显然是大于 ( W, h ) 的。这与 ( W, h ) 的极大性矛盾，所以 A ∖ W 的浓度小于 W，于是 W ≤ A ≤ W ∐ W ~ W，即 A 与 W 的浓度相同。（证毕）