构造运算 · × P(A) 划分 A/R

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

并交差补是「在已有元素间取舍」；这一页的四种运算造出结构更复杂的新集合：笛卡尔积 $A \times B$ 把两个集合配成有序对、幂集 P(A) 收集一个集合的全部子集、划分把集合切成互不相交的块、商集 A/R 按等价关系把元素归类。下面各框都可直接输入自然数集合。

一句话记住它们各自在研究什么问题：

笛卡尔积 $A \times B$ → 研究「如何配对」（多个量联合取值）
幂集 P(A) → 研究「如何选择」（枚举所有子集）
划分 partition → 研究「如何分组」（切成不重不漏的类）
商集 A/R → 研究「如何归类」（按等价关系自动分组）

1 · 笛卡尔积 A × B：所有有序对 (a, b)

product · A × B · |A×B| = |A|·|B|

$A \times B$ 是「从 A 取一个、从 B 取一个」拼成的有序对 (a, b) 的全体。有序对讲次序： $(a, 1) \ne (1, a)$ ，故一般 $A \times B \ne B \times A$ 。它的大小是乘法： $|A \times B| = |A| \cdot |B|$ ——平面直角坐标 $ℝ \times ℝ$ 、二维网格的格点，都是笛卡尔积。

不止两个：笛卡尔积可推广到任意有限个集合—— $A_1 \times A_2 \times \dots \times A_n$ 是所有有序 n 元组 $(a_1, a_2, \dots , a_n)$ 的全体，大小仍是连乘 $|A_1| \cdot |A_2| \cdot \dots \cdot |A_n|$ 。同一集合自乘记作 $A^n = A \times A \times \dots \times A$ ——三维空间的点 $ℝ^3$ 、长度 n 的比特串 {0,1}ⁿ 都是这么来的。严格说 $(A \times B) \times C$ 与「直接的」三元组 $A \times B \times C$ 在底层编码上并不相等，但二者之间有自然双射，实践中都当作三元组处理。下面展开第三个集合 C，即可在 $A \times B$ 之外看 $A \times B \times C$ ：每个 a 展开成一张 $B \times C$ 子表。

为什么需要它：单个集合只能谈「一个量」；要谈多个量联合取值（一个点的横纵坐标、一次实验的多项结果），就得把它们的取值拼成一个空间。笛卡尔积正是这个「联合取值空间」——二元关系 $R \subseteq A \times B$ 、多元函数、乃至函数的图像都定义在它之上。它解决的是：如何用集合刻画「若干坐标 / 参数的全部组合」。

2 · 幂集 P(A)：A 的所有子集

power set ·

P(A)

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

P(A)（幂集）是 A 全部子集构成的集合——它的元素本身都是集合。对每个元素独立决定「选 / 不选」，共 2^|A| 种，故 |P(A)| = 2^|A|。它总包含两个「极端」子集：空集 $\emptyset$ 和 A 自己。

为什么需要它：很多问题的对象不是「A 的元素」，而是「A 的某个子集」——满足某条件的元素集合、概率里的事件（样本空间的子集）、拓扑里的开集族 $\subseteq P(X)$ 。幂集把「A 的一切可能子集」打包成一个可研究的空间；它还严格大于 A（|A| < |P(A)|，Cantor 定理），是通往更大无穷的阶梯。

本页把 P(A) 的全部子集按大小分层铺开；要看它们被算法逐一生成的过程——用整数的位、逐元素递归、迭代翻倍或 Gray code 等不同次序点亮同一批子集——见枚举全部子集：四种算法。

幂集与组合的关系：组合数 C(n, k) 数的是「取 k 个」的方案，每种方案恰是一个 k 元子集——也就是上面大小 k 那一层的子集个数。幂集把 k 从 0 到 n 的子集全收进来，故 $|P(A)| = 2^n = C(n,0) + C(n,1) + \dots + C(n,n)$ （二项式定理）。注意组合是无序子集，与讲次序的排列不同：幂集只问「选哪些」，不问顺序。

3 · 划分：把集合切成互不相交、并起来是全集的块

partition · 互斥 + 完备

对全集 U 的一个划分，是把它拆成若干非空、两两不相交、并起来恰好是 U 的块。每个元素不重不漏地落进唯一一块。下面输入 U 和各块 $B_1 / B_2 / B_3$ （留空的块忽略），看它是否构成合法划分——输个重复或漏掉的元素，就能看到它为什么不合法。

为什么需要它：面对一个庞杂的集合，常要按某个标准把它分类，使每个元素恰好属于一类——按奇偶、按余数、按某属性归堆。划分把「分类」精确化为「非空、互斥、完备」三条，是分而治之与计数（总数 = 各类之和）的基础。

本页只校验你给出的分块是否合法。要反过来枚举一个集合的全部划分（共 Bell 数 $B_n$ 个，增长比幂集的 ${2^n}$ 还猛），见枚举全部划分：三种算法——逐元素递归、restricted growth string 与含最小元素的块。

4 · 商集 A/R：按等价关系归入等价类

quotient · A/R · 等价类

给集合 A 一个等价关系 R（满足自反、对称、传递），它把彼此「等价」的元素归成一个等价类。所有等价类构成的集合就是商集 A/R。经典例子是同余：a ~ b 当且仅当 $a \equiv b (\mod k)$ ，于是 A 被切成若干个类 $[0], [1], \dots , [k-1]$ 。等价关系与划分是一回事：商集正是它诱导的划分。

为什么需要它：有时我们只在意某种差别、忽略其余差别——时钟只认 12 小时（差 12 的时刻算同一个）、分数 1/2 与 2/4 是「同一个」有理数。商集把「视为相同」的元素并成一个，得到一个更简洁的新集合——只保留我们在意的差别（如 ℤ/12ℤ、由整数对造出有理数）。与划分的区别只在谁给依据：划分是你手动指定块，商集由等价关系 R 自动诱导。

写进代码：笛卡尔积 $A \times B$ 就是数据库的 CROSS JOIN、嵌套循环的两层遍历；划分 / 商集就是 GROUP BY 与并查集的连通分量——把集合按等价关系切成互不相交的块。

5 · 相关链接

Cartesian product — × — 有序对、n 元组与 $A^n$ ，以及它与关系 / 函数图像的联系。(en.wikipedia.org)
Power set — P(A) — 幂集、2^|A|，以及 Cantor 定理 |A| < |P(A)|。(en.wikipedia.org)
Equivalence relation & quotient — 等价关系、等价类与商集，以及它和划分的一一对应。(en.wikipedia.org)