构造运算 ·

A \times B

P(A)

· 划分 ·

A/R

造新集合：笛卡尔积、幂集、划分与商集

并交差补都在已有元素之间取舍，造不出新的对象。本页的四种构造则改变对象的层次：笛卡尔积把两个集合的元素配成有序对，幂集把子集本身当作元素，划分把集合切成块，商集把块当作元素。前两者放大规模，后两者压缩规模。

1 · 笛卡尔积 $A \times B$

product ·

|A \times B| = |A| \cdot |B|

$A \times B$ 是全部有序对 $(a, b)$ 的集合，其中 $a \in A$ 、 $b \in B$ 。有序对讲次序， $(a, 1)$ 与 $(1, a)$ 是不同的对象，故一般 $A \times B \ne B \times A$ ；两者相等只在 $A = B$ ，或有一个是空集时发生。基数是乘法： $|A \times B| = |A| \cdot |B|$ 。

笛卡尔积回答的是「多个量如何联合取值」。单个集合只能谈一个量，要谈一个点的横纵坐标、一次实验的两项结果，就得把取值拼成一个空间：平面 $\mathbb{R} \times \mathbb{R}$ 与二维网格的格点都是这么来的。二元关系 $R \subseteq A \times B$ 、多元函数与函数的图像也都定义在它之上。

图 1-1 · 笛卡尔积的全部有序对，行列交点即一个元素。可改两个集合，观察

|A| \cdot |B|

的变化。

推广到有限多个因子： $A_1 \times \dots \times A_n$ 是全部有序 $n$ 元组的集合，基数仍是连乘。同一集合自乘记作 $A^n$ ，三维空间的点属于 $\mathbb{R}^3$ ，长度 $n$ 的比特串属于 $\{0, 1\}^n$ 。

注 · 严格说 $(A \times B) \times C$ 与 $A \times B \times C$ 不是同一个集合：前者的元素是 $((a, b), c)$ 这样嵌套两层的对，后者是三元组 $(a, b, c)$ 。二者之间有自然双射，实践中一律当作三元组处理，但在需要逐层拆解有序对编码的场合（例如把有序对定义成 Kuratowski 的 $\{\{a\}, \{a, b\}\}$ 时）这个区别是实的。

图 1-2 · 多重笛卡尔积与它的元组形式。可增减因子集合，观察维数增长与每个

a

展开成一张

B \times C

子表。

2 · 幂集 $P(A)$

power set ·

|P(A)| = 2^{|A|}

$P(A)$ 是 $A$ 的全部子集构成的集合，它的元素本身是集合。 $A$ 有限时，构造一个子集等价于对每个元素独立作一次「取或不取」的决定，故 $|P(A)| = 2^{|A|}$ 。两个极端子集 $\emptyset$ 与 $A$ 总在其中， $P(\emptyset) = \{\emptyset\}$ 有一个元素而非零个。

幂集的用处在于把研究对象从元素抬升到子集：概率里的事件是样本空间的子集，拓扑里的开集族是 $P(X)$ 的子集。Cantor 定理给出 $|A| < |P(A)|$ 对一切集合成立（含无限集），所以幂集也是通往更大无穷的阶梯。

图 2-1 · 幂集列出的全部子集，按大小分层铺开。可改基集大小，观察规模随元素个数翻倍。

按大小分层看，第 $k$ 层的子集个数是组合数 $\binom{n}{k}$ ，因为每个 $k$ 元子集恰是「取 $k$ 个」的一种方案。把各层相加即得 $2^n = \sum_{k=0}^{n} \binom{n}{k}$ ，这是二项式定理在 $x = y = 1$ 处的取值。子集只问取哪些、不问次序，与讲次序的排列不同。要看这些子集被算法逐一生成的过程，见枚举全部子集。

3 · 划分与等价关系

partition · 非空 · 互斥 · 完备

集合 $A$ 的一个划分是 $A$ 的一族子集，满足三条：每块非空、两两不相交、并起来等于 $A$ 。等价地说， $A$ 的每个元素恰好落在一块里。「非空」这条常被漏掉，但少了它块数就没有意义——任意添加空块不改变其余两条。

划分把「分类」精确化，也是计数里「总数等于各类之和」这一步的依据。另一条造分类的路子是给出等价关系： $R$ 若自反、对称、传递，则把彼此等价的元素收成一类，全部等价类构成的集合叫商集 $A/R$ 。两条路子给出的是同一批东西。

定理 3.1（划分与等价关系的对应）集合 $A$ 上的等价关系与 $A$ 的划分之间存在双射：等价关系 $R$ 对应它的等价类之族 $A/R$ ，划分 $\mathcal{P}$ 对应关系「 $x$ 与 $y$ 属于同一块」。

证明设 $R$ 是等价关系。自反性给出每个 $x$ 落在 $[x]$ 里，故各类非空且并为 $A$ 。若 $[x] \cap [y] \ne \emptyset$ ，取公共元素 $z$ ，由对称与传递得 $x R y$ ，进而 $[x] = [y]$ ，故不同的类不相交， $A/R$ 是划分。反向设 $\mathcal{P}$ 是划分，定义 $x R y$ 为二者同块：同块是自反的（每个元素落在自己所在的块）、对称的、传递的（同块具有传递性，因为块两两不交，一个元素只属于一块）。两个构造互逆，故是双射。∎

图 3-1 · 校验一组分块是否构成划分。可手动分块，观察违反非空、互斥、完备哪一条时被判非法。

图 4-1 · 等价关系诱导出的商集与各等价类。可换关系，观察归类结果与定理 3.1 的对应。

商集的意义是「只保留某一种差别」。整数按模 $k$ （ $k \ge 1$ ）同余分成 $k$ 个类 $[0], \dots, [k-1]$ ，得到 $\mathbb{Z}/k\mathbb{Z}$ ；时钟只认 $12$ 小时，差 $12$ 的时刻算同一个； $\tfrac{1}{2}$ 与 $\tfrac{2}{4}$ 是同一个有理数，因为有理数本就定义为整数对在「 $ad = bc$ 」这个等价关系下的商集。划分与商集的区别只在谁给依据：划分由人指定块，商集由关系自动诱导，而定理 3.1 保证两种说法信息量相同。

4 · 两种规模的比较

growth ·

2^n

B_n

幂集的规模是 $2^n$ ，划分的总数是 Bell 数 $B_n$ （见枚举全部划分）。两者常被并提为「都是指数级」，而 $B_n$ 的增长是超指数的： $B_n / 2^n \to \infty$ 。

注 · 「 $B_n$ 增长快于 $2^n$ 」是渐近陈述，把它当成逐项成立会错，而出错的区间恰好覆盖这两页 lab 的常用规模。逐项算出来是： $B_0$ 到 $B_4$ 依次为 $1, 1, 2, 5, 15$ ，对应的 $2^n$ 是 $1, 2, 4, 8, 16$ ——前五项里 $B_n$ 一项都没超过 $2^n$ ， $n = 4$ 时还差 $1$ （ $15$ 对 $16$ ）。交叉发生在 $n = 5$ ： $B_5 = 52$ 首次超过 $2^5 = 32$ ，此后越拉越开， $n = 12$ 时是 $4213597$ 对 $4096$ 。所以在 $n \le 4$ 的演示里，划分反而比子集少。

5 · 参考文献

Cartesian product. Wikipedia. 有序对与笛卡尔积的定义，含结合性只在自然双射意义下成立。https://en.wikipedia.org/wiki/Cartesian_product
Power set. Wikipedia. 幂集的基数与 Cantor 定理。https://en.wikipedia.org/wiki/Power_set
Partition of a set. Wikipedia. 划分的三条要求与它和等价关系的对应。https://en.wikipedia.org/wiki/Partition_of_a_set
Equivalence relation. Wikipedia. 等价关系、等价类与商集。https://en.wikipedia.org/wiki/Equivalence_relation
Bell number. Wikipedia. Bell 数的递推、渐近增长与前若干项。https://en.wikipedia.org/wiki/Bell_number