§1
集合刻画"有哪些对象"，关系刻画"对象之间怎样关联"。父子、整除、同余、小于等于、程序模块的依赖——它们都是集合上的二元关系。本章建立关系的性质分类，引出两条最重要的主线：等价关系把集合切成互不相交的类，偏序关系给集合排出层次并用哈斯图画出来。
一、二元关系及其表示
定义. 集合 $A$ 到 $B$ 的二元关系是笛卡尔积的子集 $R\subseteq A\times B$。若 $(a,b)\in R$ 记作 $aRb$。当 $B=A$ 时称 $R$ 为 $A$ 上的关系。
若 $\lvert A\rvert=n$，则 $A\times A$ 有 $n^{2}$ 个元素，故 $A$ 上共有 $2^{n^{2}}$ 个不同关系。
三种常用表示：
- 集合列举：$R=\{(1,2),(2,3),(1,3)\}$；
- 关系矩阵：$n\times n$ 的 $0$–$1$ 矩阵 $M$，$m_{ij}=1$ 当且仅当 $a_{i}Ra_{j}$；
- 有向图：顶点为元素，$a_{i}Ra_{j}$ 画一条弧 $a_{i}\to a_{j}$。
例如 $A=\{1,2,3\}$ 上的"小于"关系 $R=\{(1,2),(1,3),(2,3)\}$ 的矩阵为
$$M=\begin{bmatrix}0&1&1\\0&0&1\\0&0&0\end{bmatrix}.$$
二、关系的基本性质
设 $R$ 是 $A$ 上的关系：
| 性质 | 定义 | 矩阵特征 |
|---|---|---|
| 自反性 | 对一切 $a$，$aRa$ | 主对角线全为 $1$ |
| 反自反性 | 对一切 $a$，$(a,a)\notin R$ | 主对角线全为 $0$ |
| 对称性 | $aRb\Rightarrow bRa$ | $M$ 为对称矩阵 |
| 反对称性 | $aRb$ 且 $bRa\Rightarrow a=b$ | 非对角处不同时为 $1$ |
| 传递性 | $aRb$ 且 $bRc\Rightarrow aRc$ | $M^{2}$ 的 $1$ 位置被 $M$ 覆盖 |
注意反对称不是对称的否定：恒等关系 $\{(a,a)\}$ 既对称又反对称。
三、等价关系与划分
定义. 同时满足自反、对称、传递的关系称为等价关系，常记作 $\sim$。
元素 $a$ 的等价类为 $[a]=\{x\in A\mid x\sim a\}$。
定理（等价关系与划分一一对应）. 若 $\sim$ 是 $A$ 上的等价关系，则全体等价类构成 $A$ 的一个划分：它们非空、两两不交、并集为 $A$；反之，$A$ 的任一划分都诱导出唯一的等价关系（同块者等价）。
证明要点：由自反性 $a\in[a]$ 保证非空且覆盖 $A$。若 $[a]\cap[b]\ne\varnothing$，取 $c$ 在其中，则 $a\sim c$ 且 $c\sim b$，由对称与传递得 $a\sim b$，进而对任意 $x\in[a]$ 有 $x\sim b$，即 $[a]\subseteq[b]$；反向同理，故 $[a]=[b]$。所以两类要么相同要么不交。
全体等价类的集合称为商集，记 $A/\!\sim$。
四、偏序关系与哈斯图
定义. 同时满足自反、反对称、传递的关系称为偏序，记作 $\preceq$；序对 $(A,\preceq)$ 称为偏序集。若任意两元素都可比（$a\preceq b$ 或 $b\preceq a$），称为全序（链）。
典型例子：数集上的 $\le$（全序）、集合族上的 $\subseteq$、正整数上的整除关系 $\mid$（均为偏序，后两者一般不是全序）。
哈斯图. 为简化偏序的有向图，做三步约简：
1. 略去自反环（自反性已知）；
2. 略去由传递性可推出的边（只保留覆盖关系：$a\prec b$ 且中间无第三元素）；
3. 把较大元画在上方，从而略去箭头方向。
极值元概念.
| 名称 | 定义 | 唯一性 |
|---|---|---|
| 极小元 | 没有元素严格小于它 | 可有多个 |
| 极大元 | 没有元素严格大于它 | 可有多个 |
| 最小元 | 小于等于所有元素 | 至多一个 |
| 最大元 | 大于等于所有元素 | 至多一个 |
在哈斯图中，极小元是没有向下连线的点，极大元是没有向上连线的点。
五、关系的闭包
给定关系 $R$，包含 $R$ 且具有某性质的最小关系称为该性质的闭包。
- 自反闭包 $r(R)=R\cup\Delta$，其中 $\Delta=\{(a,a)\mid a\in A\}$；
- 对称闭包 $s(R)=R\cup R^{-1}$，$R^{-1}=\{(b,a)\mid (a,b)\in R\}$；
- 传递闭包 $t(R)=R\cup R^{2}\cup R^{3}\cup\cdots$，有限集上只需并到 $R^{n}$。
其中 $R^{k}$ 表示复合 $k$ 次，含义是"沿 $R$ 走 $k$ 步可达"。传递闭包即"可达性关系"，是图论中 Warshall 算法要计算的对象。
六、例题与解答
例题1（模 $m$ 同余是等价关系）
设 $m$ 为正整数，在 $\mathbb{Z}$ 上定义 $a\sim b$ 当且仅当 $m\mid(a-b)$。证明 $\sim$ 是等价关系，并求 $m=3$ 时的商集。
解：
自反. $a-a=0=m\cdot0$，故 $m\mid(a-a)$，$a\sim a$。
对称. 若 $a-b=mk$，则 $b-a=m(-k)$，故 $b\sim a$。
传递. 若 $a-b=mk$，$b-c=ml$，则 $a-c=(a-b)+(b-c)=m(k+l)$，故 $a\sim c$。
三性质齐备，$\sim$ 是等价关系。$m=3$ 时按余数分为三类：
$$[0]=\{\dots,-3,0,3,6,\dots\},\quad [1]=\{\dots,-2,1,4,7,\dots\},\quad [2]=\{\dots,-1,2,5,8,\dots\},$$
商集 $\mathbb{Z}/\!\sim\ =\{[0],[1],[2]\}$，它们两两不交且并为 $\mathbb{Z}$，正体现"等价类即划分"。✓
例题2（整除偏序的哈斯图）
设 $A=\{1,2,3,4,6,12\}$（$12$ 的全部正因子），偏序为整除关系。写出覆盖关系，描述哈斯图，指出最大元与最小元。
解： 先列全部覆盖对（$a\prec b$ 且无中间元素）：
$$1\prec2,\quad 1\prec3,\quad 2\prec4,\quad 2\prec6,\quad 3\prec6,\quad 4\prec12,\quad 6\prec12.$$
注意 $1\prec4$ 虽然成立，但可由 $1\prec2\prec4$ 传递得到，哈斯图中不画。
图形分四层：底层 $1$；第二层 $2,3$；第三层 $4,6$；顶层 $12$。$2$ 与 $3$ 之间无连线（互不整除，不可比），$4$ 与 $6$ 同理。
$1$ 整除所有元素，故为最小元（也是唯一极小元）；所有元素整除 $12$，故 $12$ 为最大元。✓
若改取 $B=\{2,3,4,6,9\}$，则极小元为 $2,3$（各两个），极大元为 $4,6,9$，此时既无最小元也无最大元——可见极值元可以不唯一。
练习
1. 判断 $\mathbb{Z}$ 上的"小于"关系 $<$ 具有哪些性质，并写出 $A=\{1,2,3\}$ 上 $R=\{(1,2),(2,3)\}$ 的传递闭包。
2. 证明：若 $\sim$ 是等价关系，则 $a\sim b$ 当且仅当 $[a]=[b]$。
3. 画出 $\{1,2,3,4,6,8,12,24\}$ 在整除关系下的哈斯图层次并指出最大元与最小元；再举例说明一个偏序集可以有多个极大元却没有最大元。
参考答案.
1. 反自反（$a 2. 若 $a\sim b$，任取 $x\in[a]$ 有 $x\sim a\sim b$，故 $x\in[b]$，反向同理，得 $[a]=[b]$；反之若 $[a]=[b]$，由自反 $a\in[a]=[b]$，即 $a\sim b$。 3. 层次为 $1$；$2,3$；$4,6$；$8,12$；$24$，覆盖边如 $1\prec2,1\prec3,2\prec4,2\prec6,3\prec6,4\prec8,4\prec12,6\prec12,8\prec24,12\prec24$，最小元 $1$、最大元 $24$。反例：$\{2,3\}$ 上的整除关系，两元素互不可比、各自都是极大元，但不存在大于等于两者的元素，故无最大元。
本章小结
- 二元关系是 $A\times B$ 的子集，可用列举、$0$–$1$ 矩阵或有向图表示。
- 自反、对称、反对称、传递是分类关系的四把标尺，反对称不等于不对称。
- 等价关系（自反 + 对称 + 传递）与集合划分一一对应，等价类构成商集。
- 偏序（自反 + 反对称 + 传递）用哈斯图表示：去环、去传递边、以高度代替箭头。
- 极小、极大元可多个；最小、最大元至多一个，可能不存在。
- 闭包是"补足性质的最小扩张"，传递闭包即可达性关系。
本章互动演示见页面底部交互图（整除偏序哈斯图 hasseDiagram）。
互动演示
拖动下方控件观察动态过程。