整个现代数学，可以看作建立在集合这个最朴素的概念之上：把一些东西"圈在一起"，就是一个集合。代数几何更是把"集合 + 结构"的思想推到了极致——簇是多项式零点的集合，环是带运算的集合，概形则是带层结构的拓扑空间。本章为后续打下"语言"基础。
集合是数学的"砖"，关系是"水泥"，映射是"建筑结构"。我们要把这三件事都说清楚。
1. 集合的基本运算
集合的并、交、差、补
设 $A$、$B$ 是某全集 $U$ 的子集。
- 并集：$A\cup B = \{x: x\in A \text{ 或 } x\in B\}$
- 交集：$A\cap B = \{x: x\in A \text{ 且 } x\in B\}$
- 差集：$A\setminus B = \{x: x\in A \text{ 且 } x\notin B\}$
- 补集：$A^c = U\setminus A$
- 对称差：$A\triangle B = (A\setminus B)\cup(B\setminus A)$
当 $A\cap B = \varnothing$ 时称 $A$、$B$ 不相交（disjoint）。
De Morgan 律
$$ (A\cup B)^c = A^c\cap B^c,\qquad (A\cap B)^c = A^c\cup B^c $$
"否定一个 或 等于 两个的否定 与"——这是逻辑学和编程里都极其常用的恒等式。可推广到任意（无穷）族 $\{A_\alpha\}$：$\left(\bigcup A_\alpha\right)^c = \bigcap A_\alpha^c$。
图解 1：四种集合运算的 Venn 图
2. 笛卡尔积与有序对
笛卡尔积（Cartesian Product）
$$A\times B = \{(a,b): a\in A,\, b\in B\}$$
元素是有序对，即 $(a,b)\ne(b,a)$（除非 $a=b$）。一般地，$A_1\times\cdots\times A_n = \{(a_1,\ldots,a_n): a_i\in A_i\}$，$n$ 元组（$n$-tuple）的集合。
常用记号：$A^n = \underbrace{A\times A\times\cdots\times A}_{n\text{ 个}}$。例：$\mathbb{R}^2 = \mathbb{R}\times\mathbb{R}$ 是平面，$\mathbb{R}^3$ 是空间。
例 1：$\{1,2\}\times\{a,b,c\}$
$= \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$，共 $2\times 3 = 6$ 个元素。一般 $|A\times B| = |A|\cdot |B|$。
3. 关系（Relation）
关系
$X$ 上的二元关系 $R$ 是 $X\times X$ 的一个子集。若 $(x,y)\in R$，常写成 $x\,R\,y$，读作"$x$ 与 $y$ 满足关系 $R$"。
关系的三大基本性质（设 $R\subseteq X\times X$）：
- 自反（reflexive）：对一切 $x\in X$，$x\,R\,x$。
- 对称（symmetric）：$x\,R\,y \Rightarrow y\,R\,x$。
- 传递（transitive）：$x\,R\,y$ 且 $y\,R\,z \Rightarrow x\,R\,z$。
例 2：常见关系
- "$=$" 是自反、对称、传递的（等价关系）。
- "$\le$" 是自反、传递的，但不对称（"反对称"——偏序关系）。
- "$<$" 不自反、不对称、传递的（严格偏序）。
- "是 X 的朋友"——对称（通常），但不传递（朋友的朋友未必是你的朋友）。
4. 等价关系与商集
等价关系
同时满足自反、对称、传递的关系称为等价关系，常用符号 "$\sim$" 表示。
$x$ 的等价类：$[x] = \{y\in X : y\sim x\}$。
所有等价类的集合记作 $X/\!\sim$，称为 $X$ 关于 $\sim$ 的商集（quotient set）。从 $X$ 到 $X/\!\sim$ 把 $x$ 映到 $[x]$ 的映射叫商映射 $\pi: X\to X/\!\sim$。
等价类的不交分割定理
等价关系把 $X$ 分成若干互不相交的等价类，并集恰好为 $X$。反之，集合 $X$ 的任一不交分割（partition）都唯一对应一个等价关系（"同块"即等价）。
简言之：等价关系 $\Leftrightarrow$ 不交分割。
图解 2：等价关系把集合切成"色块"——商集就是色块的集合
例 3：更多等价关系
- 整数模 $n$：$a\sim b \iff n\mid (a-b)$。商集 $\mathbb{Z}/n\mathbb{Z}$，是数论与抽象代数的核心。
- 有理数构造：$\mathbb{Q} := (\mathbb{Z}\times\mathbb{Z}_{\ne 0})/\sim$，其中 $(a,b)\sim(c,d) \iff ad=bc$。等价类 $[(a,b)]$ 就是 $\tfrac a b$。
- 同伦等价（拓扑学）：两条路径若可以连续形变到对方则等价。
- 同构：两个代数结构若存在保运算的双射则等价。代数学里"同构的看作一样"——这就是不断在用等价类。
5. 映射的类型：单射、满射、双射
三种映射
设 $f: X\to Y$。
- 单射（injective / 一对一）：$f(x_1)=f(x_2) \Rightarrow x_1=x_2$。等价：不同元素映到不同像。
- 满射（surjective / 到上）：对任意 $y\in Y$，存在 $x\in X$ 使 $f(x)=y$。等价：$f(X)=Y$。
- 双射（bijective / 一一对应）：既单又满。此时存在唯一的逆映射 $f^{-1}: Y\to X$。
图解 3：单射 / 满射 / 双射
例 4：判断映射类型
- $f: \mathbb{R}\to\mathbb{R}$，$f(x)=x^2$：不单（$f(1)=f(-1)$）、不满（负数无原像）。
- $f: \mathbb{R}_{\ge 0}\to \mathbb{R}_{\ge 0}$，$f(x)=x^2$：双射，逆是 $\sqrt{\cdot}$。
- $\exp: \mathbb{R}\to (0,\infty)$，$\exp(x)=e^x$：双射，逆是 $\ln$。
- 商映射 $\pi: X\to X/\!\sim$ 总是满射（除非 $X$ 为空）。
6. 选择公理与 Zorn 引理（简介）
偏序、链、上界、极大元
$(P,\le)$ 称偏序集：$\le$ 满足自反、反对称、传递。
- 链：$P$ 的全序子集（任意两元素可比较）。
- 上界：$\sup S$ 的近亲——$u\in P$ 是 $S\subseteq P$ 的上界 $\iff$ $\forall s\in S,\, s\le u$。
- 极大元：$m\in P$ 满足"不存在 $x\in P$ 使 $m \lt x$"（注意"极大" $\ne$ "最大"——可能多个，可能不可比）。
Zorn 引理
若偏序集 $P$ 中每个链都有上界，则 $P$ 至少有一个极大元。
它在 ZFC 体系下与选择公理（Axiom of Choice, AC）和良序定理等价。它的"用法"：当你想要找一个"最大可能的对象"——比如"任意向量空间都有基"、"任意非零环都有极大理想"、"任意域都有代数闭包"——通常都是用 Zorn 引理对所有"部分构造"组成的偏序集求极大元。
例 5：Zorn 的用法骨架
断言：每个非零环 $R$ 至少有一个极大理想。
证明骨架：考虑 $P = \{R\text{ 的真理想}\}$，按包含关系 $\subseteq$ 偏序。设 $\{I_\alpha\}$ 是任一链，则 $I = \bigcup I_\alpha$ 仍是真理想（$1\notin I$，否则某个 $I_\alpha$ 已含 $1$ 不真），故 $I$ 是上界。由 Zorn，$P$ 有极大元 $\mathfrak{m}$——这就是要找的极大理想。$\square$
这种"链有上界 ⟹ 取极大"的论证模板，将在抽象代数与代数几何中反复出现。
7. 现实世界：微信群与社交关系
"在同一个群" = 等价关系吗？
定义关系：$a\sim b \iff a$ 与 $b$ 在某个共同微信群里。
- 自反 ✓（每人和自己同群——自己一人的"群"或任何群）
- 对称 ✓（同群关系无方向）
- 传递 ✗（你和 A 同 1 群，A 和 B 同 2 群，但你和 B 未必同群）
所以这不是等价关系。但若改为"$a\sim b \iff$ 存在群链 $G_1, G_2,\ldots,G_k$ 使 $a\in G_1, b\in G_k$ 且相邻群有共同成员"，就变成了"传递闭包"——一个等价关系。等价类对应"社交连通分量"，商集就是用户被划分成的"社交圈"。
同样的思想：电网中"哪些节点能互相供电"= 等价关系；图论中"连通分量"= 等价类；操作系统中"进程组"= 商集。等价关系是社会与工程网络的基本组织原理。
8. 练习
练习 1（De Morgan）
证明：$(A\cup B\cup C)^c = A^c\cap B^c\cap C^c$。
提示
$x\in (A\cup B\cup C)^c \iff x otin A\cup B\cup C \iff x otin A \text{ 且 } x otin B \text{ 且 } x otin C \iff x\in A^c\cap B^c\cap C^c$。
练习 2（笛卡尔积计数）
设 $|A|=m$、$|B|=n$。$A\times B$ 有多少元素？$A\times A$ 的子集中"对角线" $\Delta = \{(a,a):a\in A\}$ 有多少元素？
提示
$|A\times B| = mn$；$|\Delta| = m$。$\Delta$ 是一个特殊的关系——它就是"等于"关系。
练习 3（验证等价关系）
在 $\mathbb{Z}\times\mathbb{Z}$ 上定义 $(a,b)\sim(c,d) \iff a+d = b+c$。证明这是等价关系，并说明商集是什么。
提示
验证三性：自反 $a+b=b+a$ ✓；对称 $a+d=b+c \Leftrightarrow c+b=d+a$ ✓；传递 $(a,b)\sim(c,d)$ 与 $(c,d)\sim(e,f)$ 相加得 $a+d+c+f = b+c+d+e$，约去 $c+d$ 得 $a+f=b+e$，即 $(a,b)\sim(e,f)$ ✓。
等价类 $[(a,b)]$ 由 $a-b$ 这个差决定，商集双射于 $\mathbb{Z}$——这正是从自然数对 $(a,b)$ 构造整数 $a-b$ 的方法（Grothendieck 群构造的雏形）。
练习 4（映射类型）
设 $f: X\to Y$、$g: Y\to Z$。证明：
- 若 $f, g$ 都单 ⟹ $g\circ f$ 单。
- 若 $g\circ f$ 单 ⟹ $f$ 单（但不一定 $g$ 单）。
提示
(1)：$g(f(x_1))=g(f(x_2)) \Rightarrow f(x_1)=f(x_2) \Rightarrow x_1=x_2$。
(2)：$f(x_1)=f(x_2)\Rightarrow g(f(x_1))=g(f(x_2))\Rightarrow x_1=x_2$。$g$ 不必单：例如 $X=\{1\}$、$Y=\{1,2\}$、$Z=\{1\}$，$f(1)=1$、$g(1)=g(2)=1$。
练习 5（等价关系数量）
3 元素集合 $\{a,b,c\}$ 上一共有几种不同的等价关系？
提示
等价关系 ↔ 不交分割。3 元素的分割数（Bell 数 $B_3$）= 5：$\{\{a,b,c\}\}$、$\{\{a\},\{b,c\}\}$、$\{\{b\},\{a,c\}\}$、$\{\{c\},\{a,b\}\}$、$\{\{a\},\{b\},\{c\}\}$。