一，二，三，很多……

选择公理

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

如果 ∀λ∈Λ, 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 的浓度相同。（证毕）

集合可以说是最简单的结构。或者说简直简单得没有结构。对于一个抽象的集合（意思是说，我们只知道它是一个集合，其他什么也不知道）来说，它的每个元都是完全一样的，元和元的相互之间也没有任何关系——当然，要说的话还是有那么一点关系，我们总是能判断两个元是否相等。从这个角度来看，我们关于一个抽象的集合所能知道的唯一信息，就是它的元的“个数”。这是集合这种“结构”的最重要的“不变量”，也是唯一的不变量。

当然我还根本没有说过所谓“个数”是什么。OK，那现在我就这样来定义：所谓个数，就是指集合的不变量。讲这话并不是找打。我们已经定义了集合的“同构”，也就是一一对应（参看前文《映射》）。所谓“不变量”，当然是指“在同构映射下不变的东西”，于是我们就得到下面的定义：

定义。如果两个集合 A 和 B 是同构的（也就是说它们之间存在一一对应），我们就说它们同等。写做 A ~ B。这显然是一个等价关系（参看前文《关系》）。我们把关于这个等价关系的任意等价类称为个数，或者为了区别于我们的直观，换一个词称做浓度。对于任意一个集合 A，它的浓度当然定义为与 A 同等的所有集合做成的等价类。

从我们的直观上来说，“部分”的个数要比“全体”的个数来的“小”。这句话中已经暗示了一个重要的定理。

首先，所谓“部分”当然可以指“子集”。而鉴于现在我们考虑的同等关系，下面的定义应该是恰当的：

定义。如果存在一个从集合 A 到集合 B 的单射 f: A → B（这时 A 和 f ( A ) 同等），我们就说 A 比 B 小。写做 A ≤ B。

而所谓的“小”，当然不只是说说就算了。我们谈论大小的时候在暗默中就假定了一些事，关于这个请参看前文《关系》。这些“暗默中假定的事”确实成立，这就是下面的定理。

定理。≤ 是一个偏序关系。

证明。显然对任意集合 A 都有 A ≤ A。而如果 A ≤ B， B ≤ C，只要考虑映射的合成我们就有 A ≤ C。这个定理最主要的部分在于，如果 A ≤ B 且 B ≤ A，就一定有 A ~ B。或者换句话说，如果既有从 A 到 B 的单射，又有从 B 到 A 的单射，那就一定有 A 和 B 间的一一对应。这个有时被叫做Bernstein定理，证明如下：
假设有单射 f: A → B 和 g: B → A。我们的战略是把 A、 B 分别分割成 A₁ 和 A₂、 B₁ 和 B₂ 两个不相交的部分，使得 f ( A₁ ) = B₁， g ( B₂ ) = A₂。这样一来显然有 A ~ B。
先假设有这样的分割存在，这时因为 B₁ = f ( A₁ ) ⊆ f ( A )，所以 B₂ 应当要包含 B ∖ f ( A )。我们把 B ∖ f ( A ) 记为 C₀。 C₀ 既然被包含在 B₂ 里面， g ( C₀ ) 当然被包含在 A₂ 里，而 f 是单射，所以 f ∘ g ( C₀ ) 也一定被包含在 B₂ 里。依此类推，我们把 f ∘ g ( C₀ ) 记为 C₁， f ∘ g ( C₁ ) 记为 C₂，… ， f ∘ g ( C_k ) 记为 C_{k + 1}，… ，显然 B₂ 应当包含所有 C_k。
我们将证明，把 B₂ 定义为所有 C_k 的合并就可以了。这时令 A₂ = g ( B₂ )， A₁ = A \ A₂， B₁ = B ∖ B₂，剩下我们只要证明 f ( A₁ ) = B₁。由于我们最早已经把 B ∖ f ( A ) 包含在 B₂ 里面了，所以 B₁ = B ∖ B₂ 当然被包含在 f ( A ) 里。 f 是单射，所以 f ( A ) 分成 f ( A₁ ) 和 f ( A₂ ) 两个不相交的部分，而根据 B₂ 的定义我们有 f ( A₂ ) = f ( g ( B₂ ) ) = f ∘ g ( B₂ ) ⊆ B₂，所以当然 f ( A₁ ) = B₁。（证毕）

定理。对任意集合 A、 B、 C，我们有
1) ( A ∐ B ) × C ~ ( A × C ) ∐ ( B × C )
2) A^B × A^C ~ A ^{B ∐ C}
3) ( A × B )^C ~ A^C × B^C
4) ( A^B ) ^C ~ A^{B × C}
5) ℘ ( A ) ~ 2^A
注意 ∐ 和 × 分别代表非交和与笛卡儿积， ℘ ( A ) 代表幂集合（参看前文《集合》），而 A^B 表示从 B 到 A 的所有映射的集合， 2 则表示集合 { 0, 1 }。

证明。考虑这些集合的意义，定理基本是显然的。这里证明 4) 和 5) 做为例子。4) ( A^B ) ^C 的元是从 C 到 A^B 的映射，把它写成 f。于是对于任意的 c∈C， f ( c ) 是 A^B 的元也就是从 B 到 A 的映射，于是 f ( c ) 把 B 中的元 b 映到 A 中的元 f ( c ) ( b )。所以合起来说 f 正好就是把 B × C 的元 ( b, c ) 映到 A 中的元 f ( c ) ( b )。 5) 对 A 的任意一个子集 U，我们定义从 A 到 { 0, 1 } 的映射 f_U 为：如果 x∈U 则 f_U ( x ) = 1，否则 f_U ( x ) = 0。这显然是 ℘ ( A ) 和 2^A 的一个一一对应。（证毕）

定理。把所有自然数的集合记为 ℕ。我们有
1) ℕ ∐ ℕ ~ ℕ
2) ℕ × ℕ ~ ℕ

证明。 1) ℕ = { 奇数 } ∐ { 偶数 }。映射 n |→ 2n 给出了一个从 ℕ 到 { 偶数 } 的全单射，所以 { 偶数 } ~ ℕ。对于 { 奇数 } 也是一样。
2) 像这样列出 ℕ × ℕ 的所有的元： ( 1, 1 ); ( 1, 2 ), ( 2, 1 ); ( 1, 3 ), ( 2, 2 ), ( 3, 1 ); ( 1, 4 ), ( 2, 3 ), ( 3, 2 ), ( 4, 1 ); ……; ( 1, k ), ( 2, k - 1 ), …, ( k - 1, 2 ), ( k, 1 ); ( 1, k + 1 ), …… 把把这序列从头开始往后依次编为 1 号， 2 号， 3 号， … 这就给出了从 ℕ × ℕ 到 ℕ 的一个一一对应。如果你有兴趣，可以试着把这对应用式子写出来。（证毕）

ℕ 的浓度通常称为可数浓度。可数浓度的集合称为可数集合。
推论。有理数集 ℚ 是可数的。这是因为显然 ℕ ≤ ℚ ≤ℕ × ℕ，而前定理的 2) 说 ℕ × ℕ ~ ℕ。

定理。（Cantor的对角线论法） A < ℘ ( A )。

证明。显然 A ≤ ℘ ( A )。所以我们只要证明 A 和 ℘ ( A ) 间不存在一一对应。假设有这样一个对应，对于 A 的每个元 a 都对应了一个 A 的子集 U_a。 a 可能属于 U_a 也可能不属于 U_a。所以我们考虑集合 V := { a∈A | a∉U_a }，这也是 A 的一个子集，所以对应了一个 A 的元 b。但不论 b 属于 V 或不属于 V 都会引发矛盾。这矛盾是由假定 A 和 ℘ ( A ) 间存在一一对应而产生的，所以结论是 A 和 ℘ ( A ) 间不可能存在一一对应。（证毕）

℘ ( ℕ ) 的浓度通常称为连续浓度。由以上定理知它严格大于可数浓度。

定理。实数集 ℝ ~ ℘ ( ℕ )。

证明。我们证明 ℝ ~ 2^ℕ。首先 2^ℕ 的元可以看成是一条由 0、 1 组成的排成一排的序列，在这序列前加上一个“0.”就可以把它看成是一个（十进制）小数。因此 ℝ ≥ 2^ℕ。另一方面，函数 arctan ( x ) / π + 1 / 2 把 ℝ 单射地映到 ( 0, 1 ) 区间，而 ( 0, 1 ) 区间的实数可以用二进制的小数来表示，把这小数表示前的“0.”去掉就可以得到一条由 0、1 组成的排成一排的序列，从而看成 2^ℕ 的元。因此 ℝ ≤ 2^ℕ。（证毕）

定理。ℝ ~ ℝ ∐ ℝ ~ ℝ × ℝ ~ ℝ^ℕ

证明。显然我们只要证明 ℝ^ℕ ~ ℝ。把 ℝ 看成是 2^ℕ，我们有 ( 2^ℕ ) ^ℕ ~ 2^{ℕ × ℕ} ~ 2^ℕ。（证毕）

定理。 ℝ^ℝ ~ 2^ℝ

证明。显然 2^ℝ ≤ ℝ^ℝ。另一方面， ℝ^ℝ ≤ ( 2^ℝ ) ^ℝ ~ 2^{ℝ × ℝ} ~ 2^ℝ。（证毕）

ℝ^ℝ 的浓度通常称为函数浓度。由以上可知它严格大于连续浓度。但是如果我们只考虑从 ℝ 到 ℝ 的连续函数的集合 C ( ℝ, ℝ )，这个浓度就是连续浓度了。这是因为 ℚ 在 ℝ 中是稠密的，所以一个连续函数只要在 ℚ 上确定了函数值，通过取极限操作它在整个 ℝ 上的函数值也就唯一确定了。而 ℚ 是可数的，所以 C ( ℝ, ℝ ) ≤ ℝ^ℚ ~ ℝ^ℕ ~ ℝ。反方向的不等式是显然的。

直观和逻辑

直观是绝对必要的。在考虑用人工智能进行数学推理的时候大家往往只注重逻辑，我想这是电脑还没学会数学的主要原因。我并不认为直观是人独有的能力。电脑也可以有直观，只要你好好编程。（不过这好象和数学没有什么关系。）

人的缺点是，往往会轻易相信自己的直观。当严密的逻辑推理导出了比如说关于无穷大的种种所谓“不可思议”的性质时，人们往往会怀疑逻辑出了问题——逻辑，这个行事绝不光明正大的诡辩家，不知道在什么地方偷偷做了什么手脚，然后就把人给骗了。比如说就在那个反证法里。——但这往往是不对的。如果你无法接受一个由严密的逻辑推理得到的结论，通常是因为你的直观出了毛病。比如说初学者往往把无穷大想象成“一个很大很大的数”，这在很多时候有效，但也会出很多毛病。而如果想象成“一个越来越大的数”，情况就会好的多。请发挥你的想象力。

数学的特征

说到数学，我总是喜欢举两个问题作为例子。

第一个问题是，一杯水和一杯酒，体积相同。舀一勺水到酒里，搅拌一下，再舀一勺（掺了水的）酒到水里。现在问是酒里的水多还是水里的酒多？
答案是一样多。不管一勺有多大，也不管有没有搅匀。这是因为这两杯东西在开始和最后的体积都是相同的，所以说有多少水跑到了酒里，就有多少酒跑到了水里去填补失去的水留下的空位。

第二个问题是，甲和乙分别从A和B出发相向而行。第一次相遇时甲走了40米，然后两人继续各自前进，走到对方的出发点后再折回，第二次相遇时甲离开B点20米。假定甲乙行走的速率不变，不考虑转身的时间。问两次相遇的地方相距多远？
答案是40米。这是因为从第一次相遇后到第二次相遇，甲和乙分别走的路程，是他们从开始到第一次相遇时所各自走的路程的两倍（从开始到第一次相遇，甲和乙一起把AB间的路覆盖了一次；而从第一次相遇到第二次相遇，甲和乙一起把AB间的路覆盖了两次）。所以特别地，从第一次相遇后到第二次相遇时甲又走了80米。而这时他离B点20米，所以显然第二次相遇点在第一次相遇点的靠近B点方向的40米处。

这两个问题的共同点是似乎都缺失了一些条件。在第一个问题中，我们不知道两杯液体的体积是多少，也不知道勺子的容积是多少，更不知道是否搅匀。我想这些都是我们在想象这个转移液体的过程时觉得需要知道的条件。同样，在第二个问题中我们不知道AB间的距离也不知道甲和乙的速率。在想象这个相遇过程时，我想这些应该是我们觉得首先要知道的东西吧。当然，你可以把你觉得应该知道的东西设成x、y之类，然后用我们强有力的代数手法去精密地分析各个量之间的关系，然后得出答案。但是得出答案并不等于真正的理解。接下来你要做的是在那一堆代数等式的迷团中，抓出之所以会有这个答案的本质上的原因，也就是上两段中我所叙述的。当然更好的情况是一下子就想到上两段那样的解答，根本不借助代数。总之，数学需要考虑的不是一个对象的一个过程，而是一类对象的一类过程，要在一堆虽然很不相同但到底有些类似的东西中抓到本质。这是数学得以区别于算术的所在。在前一篇文章讲等价关系的时候也提到过，数学中讨论的对象往往是抽象的等价类。我们作直观想象的时候只能把具体的对象浮现于脑际，这时你要么把等价的那些具体的对象同时浮想出来，要么时刻牢记，这个就是那个，白马和黑马都是马。当然，关于具体的东西的精密的分析手段也是绝对必要的，在复杂的问题上，几乎没有人能够一下子就抓住问题的本质。几乎所有重要的概念都是从关于一个个具体的例子的具体的知识储备中升华出来的，而有了这些概念以后那一个个的具体的例子往往都变成显然的了。就像上面的这两个问题，明白了以后会觉得这是多么浅显道理啊！这也是为什么每一代新生的数学家都能在短时间内掌握前辈们在几百年一千年的时间里储备下来的数学知识，而且在此基础上又有新的创造的原因。

数学的方法

在我看来，数学最根本的方法莫过于类比。用我们容易想象的、充分理解的东西去类比不那么容易理解的东西。这个过程分为几个方面。

首先对于我们很了解的东西，我们需要做的是抽出“这东西之所以成为这样的根本原因”，这就是公理化。把那许许多多性质之所以成立的根本原因归结于几条公理，然后在其他我们不甚了解的对象身上发现满足这几条公理的“结构”。举一个例子。我们很熟悉有理数。我们知道有理系数的多项式可以唯一地因式分解。然后我们抽出这其中的原因是因为有理数是一个“域”。后来我们发现，对于素数p，整数除以p的同余等价类也作成了一个域。而在这个域上，显然 1, 2, 3, … , p - 1（的等价类）都满足方程 x^{p -1} - 1 = 0。于是按照有理系数的多项式的类比，我们得出在这个域上有
x^{p - 1} - 1= ( x - 1 ) ( x - 2 ) … ( x - p + 1 )
比较左右两边的常数项，我们得出结论， ( p - 1 ) ! （ p - 1 的阶乘）与 -1 是除以 p 同余等价的。或者换种说法，当 p 是素数的时候， ( p - 1 ) ! + 1 被 p 整除。这就是著名的Wilson定理。也许你曾经见到过用初等数论的方法给出的这个定理的一个很有技巧性的证明，但在这里我们得到它只是用了一件显然的事和一个类比。

在上个世纪，公理化的工作是如此的成功以至于我们几乎把几千年来人类储蓄下的几乎所有数学知识都归结到了几种基本的“结构”上。现在，任何一个经过训练的数学专业的学生，无论他在应用中碰到什么问题，几乎都可以立刻把它归结到一个关于我们已知的某种结构的性质的问题上面来。

公理化完成之后，类比的方法再细分大概可以大致区别为两种：一曰“近似”，二曰“表现”。近似当然是“用离它很近的东西来类比它”，可以说整个数学分析领域贯穿的都是近似的思想。用有限近似无限，用线形近似非线性，用光滑近似不光滑。等等等等。表现，意思是“用我们容易理解的东西来表现我们不容易理解的东西”。（不可交换的）群是不容易理解的，所以有表现论研究怎样把群的元对应到我们比较容易理解的矩阵。连续的几何对象通常是不容易理解的，所以有代数拓扑把几何对象对应到我们比较容易掌握的加群。各种大大小小的同构、同态、同胚、同伦、同调、同位映射更是充斥了数学的各个角落，这些简单的说就是把一个对象保持它的某些结构不变地映射到另一个对象来考虑，或者说用另一个对象来“表现”这个对象。

我举两个例子。我个人认为这两个例子非常精彩，非常好地说明了什么叫做“把不容易理解的东西化成容易理解的东西”。

第一个例子是这样的：一个大圆B套着一个小圆A。我们在A和B之间作圆，要求圆1和A、B相切，圆2和A、B、1相切，圆3和A、B、2相切，依此类推。（图一）这样一直作下去，假设绕了一圈之后回来，圆n正好和A、B、n-1都相切。问题是：假设我们在一开始的时候选择一个不同的位置作圆1（图中红色的圆1），然后依次作下去，这样在绕一圈回来之后最后的那个圆是否仍然能够正好和圆1相切？如果是，那A、B间圆的个数是否仍然正好等于n？
这两个问题的答案都是肯定的。很奇妙吧。但是对于一种特殊情形，A和B是同心圆的情况下，（图二）这件事完全是显然的。那我们有办法把图一的情形化到图二的情形吗？有。我们把平面看成是复数平面，考虑复平面上的一次变换 z |→ ( az + b ) / ( cz + d )。众所周知，这变换把圆映成圆，并且是保角的，所以当然保持相切关系不变。另一方面只要稍做计算就会知道，对于任意两个套着的圆，这变换总可以把它们映成是同心的。于是我们就借助这变换的力量，把奇妙的事化成了显然的事。眼睛一眨，老母鸡变鸭。

第二个例子。过圆外一点P，求作这个圆的切线。这个问题的解法大概在任何一种初中几何教科书里都会介绍，但这里描述的是一种（按照初中几何的标准来说）“非标准的”、只使用直尺就可以完成的作法。如图三，过P随便作两条直线交圆于A、B、C、D。AD与BC交于E，AC与BD交于F。然后连接EF交圆于R、S，则PR与PS就是圆的切线。
如果你多画几次，一定会感觉到这件事中间隐藏着什么重大的秘密。那些点神秘地排列在同一条直线上。我们有办法理解它吗？如果你知道一点射影几何，这件事就容易说明的多了。
假设点P是在无穷远的地方。这时过点P的所有直线是一组（朝着某一个方向的）平行线。于是我们看到这件事在一瞬间变得显然了。（图四）

用射影变换，我们可以把图三的情形化成图四的情形。射影变换把直线映成直线，交点映成交点。相切于一点既然是相交于两点的极限情形，射影变换当然也保持相切关系不变。另一方面射影变换虽然不一定把圆映成圆（一般地来说它把圆映成圆锥曲线），但在这个问题中，我们有办法既把点P映成无穷远点，又把那个圆仍然映成圆。（图五）
这样一来我们就又把一件神秘的事化成了一件显然的事。但是——我们真的理解了这些事了吗？诚然对于特殊情形来说它们简单得令人发笑；也诚然我们确实知道有变换把一般情形化成特殊情形；但是这变换岂不是很奇妙吗？现在神秘性从一般的情形转到了这个变换上。为什么会有这个变换？为什么就偏偏正好就在这件神秘的事上有这个神秘的变换呢？我只能说这两个变换并不是那么神秘。一个是复一维射影空间上的一次变换，一个是实二维射影空间上的一次变换，两者都是非常朴素、自然的东西。但是……确实这两件事着实可以让我们的直觉吃上一惊。而我想我们目前为止对这两件事所能作的最好的解释莫过于此了。我们总是用一件事去解释另几件事。——古人认为我们的世界是被驮在一只大乌龟的背上，至于大乌龟又站在什么上面就是另一回事了——如果你追求不懈，坚持要刨根问底，很容易就会陷入哲学的迷思。我想古希腊人就是这样被五个正多面体迷得神魂颠倒的——为什么正好是五个呢？柏拉图在《Timaios》中主张说，正四面体=火，正六面体=土，正八面体=空气，正二十面体=水，而关于正十二面体则记叙说：然而还有一个第五构成体的存在；这是神为了包含万物的目的，在上面画着各种各样的绘图时所使用的。（所以说古希腊人还是不够聪明。你看我们的老祖宗早就在说阴阳五行了……）问题在于，你永远不可能从自己先天的直觉或上帝的启示（我们假定有这种东西）中得到问题的解答，因为先天的直觉本来就不完美，而上帝又是太完美了所以觉得根本没必要解释。能够美妙地解释已知事物的，只有新发现的事物。我们所能做的只有到广大的未知中去探索发现，或者偶尔回眸一瞥。物理学家们或许会渴望找到可以解释万物的终极理论，但是数学，为了追求更广的视角和更深的理解，永远不会停止。

用集合论的语言，一个关于集合 A₁, A₂, … , A_n 中的元的 n 项关系，定义为集合 A₁ × A₂ × … × A_n 的子集 R。对于 a₁∈A₁, a₂∈A₂, … , a_n∈A_n，如果 ( a₁, a₂, … , a_n ) ∈R，我们就说 a₁, a₂, … , a_n满足关系 R。

但是这定义其实也是怎么都好。一个关系，就是数学语言中的一个谓语，我们用它来构成一个句子或者说命题的主干部分。最为常见的关系，大概是要数表示相等的“等于”和表示大小的“大于”、“小于”了吧。几乎每一个数学系的学生都会首先学到这两种关系，或者更精确的说，这两种关系中的逻辑结构。

等价关系

如果一个二项关系~满足以下条件，我们就称其为等价关系：

1. x ~ x。
2. 如果 x ~ y，则 y ~ x。
3. 如果 x ~ y， y ~ z，则 x ~ z。

相等当然是等价关系。对于任意一个对象 x，所有和 x 等价的对象的全体称为 x 的等价类。如果这是定义在某个集合 A 上的等价关系，那么等价类把 A 分成几个互不相交的子集。我们把每个等价类看作是一个单独的对象，由这些等价类为元组成的集合称为集合 A 的（关于 ~ 的）商集合。

“明白了商集合，就是数学初段。”（XX语）这话很有道理。商集合体现了数学的一个重要特征，那就是一个对象的表示不一定是唯一的。比如说我定义如果两个自然数除以6的余数相同，就称它们同余。同余是一个等价关系。在这个等价关系下，我说“1”怎么怎么样和说“7”怎么怎么样是一个意思，因为我们已经把1和7看成是一样的东西了。我想每个小学生在听到“1 = 0.9999999…”的时候心灵都会受到一定的冲击。在我看来，这个时候对他们解释实数、极限之类，或者小数的分数表示之类，或者小数的加减法之类，都是没有说到点子上。在这件事上我们的心灵受到的冲击是来自于一种原始的直观我们认为在我们的十进制记数系统下每个数的表示都是唯一的，但其实不是的。在我看来正是这种不唯一性让我们感到焦虑不安。在那一瞬间我们开始怀疑自己本能的感觉：我们甚至不知道两个东西是不是相等。

在我上面举的两个例子中，情况还稍微有点不同。比如我们可以规定说，总是用0，1，2，3，4，5来表示除以6的6个同余等价类。我们遇到说7怎么怎么样的时候都自动的把7换成1。对于小数也是一样。我们遇到说0.2199999…怎么怎么样的时候都自动把它换成0.22。我想大多数的普通人都是这么处理的。但是在真正的数学中，这样的“规定”很多时候都不现实而且没有意义，甚至会让论证变的复杂。你要做的是习惯于面对“表示不是唯一的”这样的状况。这种状况的最典型的例子出现在要定义一个商集合到另一个集合的映射的时候。请不要把商集合单纯的理解成“等价类们的集合”，虽然我们确实是这么定义的。除非在很特殊的情况下，等价类通常都是抽象的虚无飘渺很难把握的概念。请把一个集合的商集合理解成，“还是那个集合，只不过把其中的一些元看成是一样的”。所以说一个集合 A 的商集合的元，通常写成 [ a ] 的形式，其中 a 是集合 A 的元而中括号 [ ] 提醒我们现在正在讨论的是另一种等价关系。在不至于引起误解的时候，甚至连中括号都省略。这样你该很容易明白了，要定义集合 A 的一个商集合到另一个集合B的映射，等于说是定义一个从 A 到 B 的映射，满足“等价的两个元的像是相等的”这个条件。这个条件通常被称为well-defined，映射能够正当地被定义的意思。

等价类的一个元有时被称为这个等价类的代表元。如果从每个等价类中都选出一个代表元，这些代表元组成的集合被称为代表系。选取一个代表系的过程相当于上一段开头所说的“规定”的过程。

顺序关系

如果一个二项关系 ≤ 满足以下条件，我们就称其为偏序关系：

1. x ≤ x。
2. 如果 x ≤ y 且 y ≤ x，则 x = y。
3. 如果 x ≤ y， y ≤ z，则 x ≤ z。

偏序关系是数的大小关系的类似，这种类似的唯一不足之处在于，偏序关系并不保证任意的两个元总可以比较大小。补上这个不足之后的关系称为全序关系。

如果在某个集合上定义了一个偏序关系，我们有时会说这是一个偏序集合或这个集合具有偏序结构。有“结构”就有“保持结构不变的映射”。所以对于两个偏序集合 A、 B，一个从 A 到 B 的保序映射 f 定义为从 A 到 B 的满足以下条件的映射：
对于 A 中任意两个元 x、 y，如果 x ≤ y，则（在 B 中）有 f ( x ) ≤ f ( y )。

具有非全序的偏序结构的一个典型例子是一个集合 A 的幂集合 ℘ ( A ) （ A 的所有子集组成的集合）上由包含关系 ⊆ 定义的偏序关系。对于任意的映射 f: A → B，我们可以定义 f: ℘ ( A ) → ℘ ( B ) 和 f^-1: ℘ ( B ) → ℘ ( A ) 分别把 A 的子集 U 映到 f ( U ) 和把 B 的子集 V 映到 f^-1 ( V )。（参看前一篇《映射》。）显然这两个映射都是保序映射。但是如果我们还另外在幂集合上考虑 ∩、 ∪ 两项运算，这运算在幂集合上定义了另一种结构（这结构有时叫做“布尔代数”，把布尔代数和包含关系放在一起考虑的结构则称为“lattice”），这时 f^-1 仍然是保持这种结构不变的，但 f 就不是了。（仍然参看前一篇《映射》。） f: ℘ ( A ) → ℘ ( B ) 和 f^-1: ℘ ( B ) → ℘ ( A ) 有时被称为是由 f: A → B 诱导的映射，由于 f^-1 是从 ℘ ( B ) 到 ℘ ( A )，所以称为反变，相应的 f 是从 ℘ ( A ) 到 ℘ ( B ) 所以称为共变。诱导、共变、反变云云，都是范畴论的概念，这里就不多说了。

对于一个定义了偏序关系的集合，显然在它的任意子集上也同样定义了偏序关系。这个子集上的偏序关系有时被说成是“子集继承的偏序结构”。如果一个子集继承的偏序结构在这个子集上正好是一个全序，则把这个子集叫做全序子集。

我们说 a 是一个偏序集合中的极大元，如果这集合中再没有比 a 更大的元了。极小元也是同样地定义。极大/极小元可能不存在，也可能有好几个。但是显然当这顺序是全序的时候，极大/极小元如果存在就只有一个，称为最大/最小元。

在公理化集合论的叙述中，集合 A 到集合 B 的映射被定义为集合 A × B 中满足下列条件的子集 F：
“对于 A 中每一个元 a，都唯一存在一个 B 中的元 b，使得 ( a, b ) 是 F 中的元。”
但是这种技术上的定义怎么都好。所谓 A 到 B 的映射就是说对于 A 中每一个元 a，都指定了 B 中的一个元 b 和 a 对应。如果我们把映射记为 f: A → B，那么这个对应通常写成 f ( a ) = b 或者 a^f = b（我们有时会想要把 f 写在 a 的右边，那么就是这样写）。这时我们说 b 是 a 的（关于映射 f 的）像。至于映射的技术上的定义的唯一用处，只是在于说明从 A 到 B 的所有映射组成了一个集合。这个集合有时记为 B^A。

虽然我前面说过，数学中所要讨论的问题——命题，从本质上来说，就是关于某个元是否属于某个集合的问题；但这并不是说数学就是关于各种性质的集合和各种集合的性质的学科。数学，是关于结构和结构保持的映射的学科（MacLane语）。这话的意思是说映射是比集合更基本更重要的概念。说“数学的一切奥秘都隐藏在映射中”（我的话），这话我想一点也不为过。在我看来，数学的一切神秘力量都起因于我们对这个世界的真理的认识的先天的不平等性。我们对有些东西知道的多一些，有的少一些；大概在上帝看来费马大定理和 1 + 1 = 2 是一样显然的，但是在我们看来费马大定理一点也不显然。而数学所做的，一言以蔽之就是把不那么容易理解的东西，“保持它的某些结构不变”，“映射”到我们容易理解的东西上面。我们充分地理解容易理解的东西，然后通过这个映射，（因为它是保持了“某些结构”不变的，）来推测出不容易理解的东西的性质。可以说每发现这样一个映射，我们对这个世界的了解都切实地大大前进了一步。

至于什么是“结构”什么又叫做“保持结构不变”的映射，虽然这在Bourbaki里是有严格的定义的（本来“结构”的概念就是由Bourbaki提出来的；这和同时期法国的“结构主义”哲学究竟有还是没有关联，就不是我所知道的了），但是我们尽可以把结构直观地理解成“集合的元的相互之间的关系”，而说把这个集合映到那个集合的一个映射“保持结构不变”，意思自然是说如果在这个集合里的一些元满足一些关系，那么这些元被映射映到那个集合里去的“像”之间，也同样满足这些关系。

假设有映射 f: A → B 和 g: B → C，我们显然可以定义一个映射 g ∘ f: A → C，把任意元 a∈A 映到 g ( f ( a ) ) ∈C。这叫做映射的“合成”或者“乘法”。有时我们会希望把这乘法写成 fg 的样子，这时我们就说 fg 把任意元 a∈A 映到 ( a^f ) ^g∈C。

命题。映射的合成满足结合律。也就是说假设有映射 f: A → B ，g: B → C，h: C → D，则 h ∘ ( g ∘ f ) = ( h ∘ g ) ∘ f

证明是显然的。这只是把一件显然的事用记号表达出来。逻辑推理虽然只是把一些显然的事连接起来，但是连接的多了就会累了。但是如果把推理变成记号的演算，就不显得那么累。这也算是“把不容易理解的东西化成容易理解的东西”的一例吧。

定义。假设有映射 f: A → B，对于 A 的子集 U，把 f ( U ) ⊆ B 定义为 f ( U ) := { x∈B | ∃u∈U s.t. f ( u ) = x }。和对于 A 的元的说法一样，我们把 f ( U ) 也称为 U 的像。

如果你完全不明白这堆符号的意思，请看前一篇末尾处的记号表。这个定义直译过来就是说， f ( U ) 是由 B 中满足这样条件的元 x 所组成的集合：存在一个 U 中的元 u，使得 u 的像正好是 x。我们喜欢用这样的记号而不是用“把 U 的元通过映射 f 映到 B 得到的所有像的集合”这样的句子来表示，我觉得很大程度上是因为记号的笔画比较少，在黑板上写起来比较容易。但是在电脑上写起来就正好反过来了。不过为了让这文章“看起来像数学”，我还是喜欢时不时用记号。真的，对我们来说，记号更为明确而且通常比文字更易懂。只要在纸上写过几遍，我想你也一定马上会习惯的。

定义。假设有映射 f: A → B，对于 B 的子集 V，把 f^-1 ( V ) ⊆ A 定义为 f^-1 ( V ) := { x∈A | f ( x ) ∈V }。我们把 f^-1 ( V ) 称为 V 的原像或者逆像。直观说来就是， f^-1 ( V ) 是 A 中所有被 f 映到 V 的元的集合。

命题。假设有映射 f: A → B。
对于 B 的子集 R、 S，我们有
f^-1 ( R ∪ S ) = f^-1 ( R ) ∪ f^-1 ( S )，
f^-1 ( R ∩ S ) = f^-1 ( R ) ∩ f^-1 ( S )；
对于 A 的子集 P、 Q，我们有
f ( P ∪ Q ) = f ( P ) ∪ f ( Q )，
f ( P ∩ Q ) ⊆ f ( P ) ∩ f ( Q )。

证明是容易的。如果你从没有尝试过，请试着证明它。这个命题唯一不那么美好的部分是最后一条 f ( P ∩ Q ) ⊆ f ( P ) ∩ f ( Q ) 中的包含关系不能改成等于。这起因于 A 中两个不同的元的像可能会相等。从这个命题也可以看出一些端倪，一般来说，原像的性质常常比像的性质要好。

定义。对于映射 f: A → B，如果 f ( A ) = B，则说 f 是一个全射；如果 A 中两个不同的元的像总是不同，则说 f 是一个单射。如果一个映射既是全射也是单射，则称之为全单射或一一对应。

虽然从定义中完全看不出来，但是在很多情况下全射的概念和单射的概念是有一定的对称性的。这从下面这个命题中可以看出一些迹象：

命题。假设有映射 f: A → B。则
f 是单射的充分必要条件是：
对于任意两个映射 g₁, g₂: L → A，只要 f ∘ g₁ = f ∘ g₂，就有 g₁ = g₂；
f 是全射的充分必要条件是：
对于任意两个映射 h₁, h₂: B → R，只要 h₁ ∘ f = h₂ ∘ f，就有 h₁ = h₂。

这是一个从范畴论的观点来看的命题。范畴论是一门充分强调映射（或者更广泛的说，保持某种“结构”的映射）在数学中的基础地位的理论，它的口号是所有概念都用映射之间的相互关系（而不是元与集合之间或集合与集合之间的相互关系）来表达。现在大家都说范畴论是和集合论一样基础的理论。至于这个命题本身的证明是容易的。如果你没有试过，请尝试。（我还没有定义什么叫做两个映射相等，不过把两个映射相等理解成它们“把同样的元映到同样的像”，应该是没有任何异议的）

定义。对于任意集合 A，存在一个恒等映射 id_A: A → A，把每个元映到其自身。显然对于任意的映射 f: A → B，我们有 f ∘ id_A = id_B ∘ f = f

这定义看起来似乎完全是没事找事。但是从范畴论的观点来看，我们与其说“一个集合 A”，还不如说“一个恒等映射 id_A”。因此从强调映射的角度来看，这也不完全是吃饱了撑的。更重要的是我们需要恒等映射来定义同构的概念：

定义。我们说一个从 A 到 B 的映射（或者更广泛的说，保持某种结构不变的映射） f 是一个同构，当且仅当存在一个从 B 到 A 的（同样保持这种结构不变的）映射 g，满足 g ∘ f = id_A， f ∘ g = id_B。这时我们把 g 叫做 f 的逆。显然逆如果存在，一定是唯一的。

一个从 A 到 B 的（保持某种结构不变的）映射是一个同构，意味着我们把 A 的元对应到 B 中来讨论的对应过程中（仅就所保持的这种结构而言）没有任何信息的丢失或者增加。因此这当然是十分重要的概念。

同构当然是全单射。而仅就单纯的集合之间的映射而言，全单射显然也一定是一个同构（也就是说全单射一定有逆映射）。但是如果我们考虑了某种结构，一个保持这种结构的全单射是否是一个同构，就是另一个问题了。这是因为对于一个保持某种结构的全单射，虽然存在它的一个忽视结构的集合论意义上的逆，但这个逆是否一定也会保持这种结构，这和要考虑的结构有关。比如保持群结构的全单射一定是同构，但是保持偏序结构的全单射就不一定。