二元关系

一、笛卡尔积

1.1 有序对

定义：由两个元素 $x$ 和 $y$ 按一定顺序组成的二元组称为有序对，记作 $\langle x, y \rangle$。

要点：

• 有序对的顺序很重要：$\langle a, b \rangle \neq \langle b, a \rangle$（当 $a \neq b$ 时）
• 两个有序对相等当且仅当对应分量相等：$\langle a, b \rangle = \langle c, d \rangle \Leftrightarrow a = c \land b = d$

1.2 笛卡尔积的定义

定义：设A和B是两个集合，由A中元素为第一分量、B中元素为第二分量的所有有序对组成的集合称为A与B的笛卡尔积，记作 $A \times B$。（两个排列组合）

$A \times B = \{\langle a, b \rangle \mid a \in A \land b \in B\}$

示例：

• $A = \{1, 2\}$，$B = \{a, b\}$
• $A \times B = \{\langle 1, a \rangle, \langle 1, b \rangle, \langle 2, a \rangle, \langle 2, b \rangle\}$

1.3 笛卡尔积的元素个数

公式：若 $|A| = m$，$|B| = n$，则 $|A \times B| = m \times n$

要点：

• $A \times B \neq B \times A$（笛卡尔积不满足交换律）
• $A \times \emptyset = \emptyset$，$\emptyset \times A = \emptyset$

二、二元关系的基本概念

2.1 二元关系的定义

定义：设A和B是两个集合，$A \times B$ 的任意子集R称为从A到B的一个二元关系。

$R \subseteq A \times B$

特殊情况：

• 当 $A = B$ 时，$R \subseteq A \times A$，称R为A上的二元关系

示例：

• $A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$ 是A上的一个二元关系

2.2 特殊关系

示例：设 $A = \{1, 2, 3\}$

• $I_A = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}$

2.3 元素的关系

定义：若 $\langle a, b \rangle \in R$，记作 $aRb$，称"a与b有关系R"；否则记作 $a \not R b$。

三、关系的表示方法

3.1 关系矩阵

定义：设 $A = \{a_1, a_2, \cdots, a_m\}$，$B = \{b_1, b_2, \cdots, b_n\}$，$R$ 是从A到B的关系。关系矩阵 $M_R = (r_{ij})_{m \times n}$，其中：

$r_{ij} = \begin{cases} 1, & \text{若} \langle a_i, b_j \rangle \in R \\ 0, & \text{若} \langle a_i, b_j \rangle \notin R \end{cases}$

示例：设 $A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle\}$

$M_R = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$

3.2 关系图

定义：用图表示关系，集合A中的每个元素对应一个结点，若 $\langle a_i, a_j \rangle \in R$，则画一条从 $a_i$ 指向 $a_j$ 的有向边。

要点：

• 自反关系在关系图中表现为每个结点有自环
• 对称关系在关系图中表现为双向边

四、关系的性质

4.1 自反性

定义：R是集合A上的关系，若对任意 $x \in A$，都有 $\langle x, x \rangle \in R$，则称R是自反的。

$\forall x (x \in A \to \langle x, x \rangle \in R)$

关系矩阵特征：主对角线全为1

关系图特征：每个结点都有自环

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 1, 2 \rangle\}$ 是自反的

4.2 反自反性

定义：R是集合A上的关系，若对任意 $x \in A$，都有 $\langle x, x \rangle \notin R$，则称R是反自反的。

$\forall x (x \in A \to \langle x, x \rangle \notin R)$

关系矩阵特征：主对角线全为0

关系图特征：每个结点都没有自环

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$ 是反自反的

注意：一个关系可以既不是自反的，也不是反自反的。

4.3 对称性

定义：R是集合A上的关系，若对任意 $\langle x, y \rangle \in R$，都有 $\langle y, x \rangle \in R$，则称R是对称的。

$\forall x \forall y (\langle x, y \rangle \in R \to \langle y, x \rangle \in R)$

关系矩阵特征：矩阵关于主对角线对称（$M_R = M_R^T$）

关系图特征：有向边都是双向的

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle\}$ 是对称的

4.4 反对称性

定义：R是集合A上的关系，若对任意 $\langle x, y \rangle \in R$ 且 $x \neq y$，都有 $\langle y, x \rangle \notin R$，则称R是反对称的。

$\forall x \forall y (\langle x, y \rangle \in R \land \langle y, x \rangle \in R \to x = y)$

等价条件：$\langle x, y \rangle \in R$ 且 $x \neq y$，则 $\langle y, x \rangle \notin R$

关系矩阵特征：关于主对角线对称的位置上不能同时为1

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$ 是反对称的

注意：对称性和反对称性不是互斥的。$R = \{\langle 1, 1 \rangle\}$ 既是对称的，也是反对称的。

4.5 传递性

定义：R是集合A上的关系，若对任意 $\langle x, y \rangle \in R$ 且 $\langle y, z \rangle \in R$，都有 $\langle x, z \rangle \in R$，则称R是传递的。

$\forall x \forall y \forall z (\langle x, y \rangle \in R \land \langle y, z \rangle \in R \to \langle x, z \rangle \in R)$

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 1, 3 \rangle\}$ 是传递的

反例：$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$ 不是传递的（缺少 $\langle 1, 3 \rangle$）

4.6 性质速查表

五、关系的复合与逆

5.1 关系的复合

定义：设R是从A到B的关系，S是从B到C的关系，R与S的复合关系记作 $R \circ S$，是从A到C的关系：

$R \circ S = \{\langle a, c \rangle \mid \exists b (b \in B \land \langle a, b \rangle \in R \land \langle b, c \rangle \in S)\}$

要点：

• 复合的顺序：先R后S，写作 $R \circ S$
• 若R是A上的关系，则 $R \circ R$ 记作 $R^2$，$R^n = R^{n-1} \circ R$

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$

• $R^2 = R \circ R = \{\langle 1, 3 \rangle\}$

5.2 逆关系

定义：设R是从A到B的关系，R的逆关系 $R^{-1}$ 是从B到A的关系：

$R^{-1} = \{\langle b, a \rangle \mid \langle a, b \rangle \in R\}$

关系矩阵：$M_{R^{-1}} = M_R^T$（转置矩阵）

性质：

• $(R^{-1})^{-1} = R$
• $(R \circ S)^{-1} = S^{-1} \circ R^{-1}$

六、闭包

6.1 自反闭包

定义：包含R的最小自反关系，记作 $r(R)$。

公式：
$r(R) = R \cup I_A$

其中 $I_A$ 是恒等关系。

关系矩阵：$M_{r(R)} = M_R \lor I$（将主对角线全置为1）

6.2 对称闭包

定义：包含R的最小对称关系，记作 $s(R)$。

公式：
$s(R) = R \cup R^{-1}$

关系矩阵：$M_{s(R)} = M_R \lor M_R^T$

6.3 传递闭包

定义：包含R的最小传递关系，记作 $t(R)$。

公式：
$t(R) = R \cup R^2 \cup R^3 \cup \cdots$

若 $|A| = n$，则：
$t(R) = R \cup R^2 \cup \cdots \cup R^n$

示例：$A = \{1, 2, 3\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$

• $R^2 = \{\langle 1, 3 \rangle\}$
• $R^3 = \emptyset$
• $t(R) = R \cup R^2 = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 1, 3 \rangle\}$

6.4 闭包速查表

6.5 闭包的复合性质

三种闭包之间存在以下关系：

$rs(R) = sr(R)$

$rt(R) = tr(R)$

$ts(R) \neq st(R) \quad \text{（一般情况下）}$

要点：自反闭包与对称闭包可交换，自反闭包与传递闭包可交换，但对称闭包与传递闭包一般不可交换。

注：Warshall算法可简化传递闭包的矩阵运算，将在"数据结构"课程中详细讲解。

七、等价关系

7.1 等价关系的定义

定义：集合A上的关系R如果满足自反性、对称性、传递性，则称R为等价关系。

7.2 等价类

定义：设R是A上的等价关系，对任意 $a \in A$，a的等价类记作 $[a]_R$：

$[a]_R = \{x \mid x \in A \land \langle a, x \rangle \in R\}$

性质：

• 等价类非空：$a \in [a]_R$
• 两个等价类要么相等，要么不相交
• 所有等价类的并集等于A

7.3 商集

定义：A上等价关系R的所有等价类组成的集合称为A关于R的商集，记作 $A/R$。

$A/R = \{[a]_R \mid a \in A\}$

7.4 划分与覆盖

覆盖的定义：设 $A$ 为非空集合，$S = \{S_1, S_2, \cdots, S_m\}$，若满足：

1. $S_i \subseteq A$，$S_i \neq \emptyset$（$i = 1, 2, \cdots, m$）
2. $S_1 \cup S_2 \cup \cdots \cup S_m = A$

则称 $S$ 为 $A$ 的一个覆盖。

划分的定义：设 $A$ 为非空集合，$S = \{S_1, S_2, \cdots, S_m\}$，若满足：

1. $S_i \subseteq A$，$S_i \neq \emptyset$（$i = 1, 2, \cdots, m$）
2. $S_1 \cup S_2 \cup \cdots \cup S_m = A$
3. 当 $i \neq j$ 时，$S_i \cap S_j = \emptyset$

则称 $S$ 为 $A$ 的一个划分（分划）。

划分与覆盖的区别：

划分是覆盖的特例：划分一定是覆盖，但覆盖不一定是划分。

7.5 最大划分与最小划分

最小划分（划分块数最少）：集合A的全部元素组成一个分块。

$S_{\min} = \{A\}$

最大划分（划分块数最多）：每个元素构成一个分块。

$S_{\max} = \{\{a\} \mid a \in A\}$

示例：设 $A = \{1, 2, 3\}$

• 最小划分：$\{\{1, 2, 3\}\}$
• 最大划分：$\{\{1\}, \{2\}, \{3\}\}$
• 其他划分：$\{\{1\}, \{2, 3\}\}$、$\{\{2\}, \{1, 3\}\}$、$\{\{3\}, \{1, 2\}\}$

定理：A上的等价关系与A的划分一一对应。每个等价关系确定一个划分（商集），每个划分确定一个等价关系。

7.5 等价关系示例

例题：设 $A = \{1, 2, 3, 4, 5, 6\}$，$R = \{\langle x, y \rangle \mid x \equiv y \pmod{3}\}$（模3同余关系）

验证R是等价关系：

• 自反性：$x \equiv x \pmod{3}$，成立
• 对称性：若 $x \equiv y \pmod{3}$，则 $y \equiv x \pmod{3}$，成立
• 传递性：若 $x \equiv y \pmod{3}$ 且 $y \equiv z \pmod{3}$，则 $x \equiv z \pmod{3}$，成立

等价类：

• $[1]_R = \{1, 4\}$
• $[2]_R = \{2, 5\}$
• $[3]_R = \{3, 6\}$

商集：$A/R = \{\{1, 4\}, \{2, 5\}, \{3, 6\}\}$

八、偏序关系

8.1 偏序关系的定义

定义：集合A上的关系R如果满足自反性、反对称性、传递性，则称R为偏序关系，记作 $\preceq$。

常见偏序关系：

• 实数集上的 $\leq$（小于等于）
• 集合的 $\subseteq$（包含关系）
• 正整数集上的 $|$（整除关系）

8.2 全序关系

定义：设 $\preceq$ 是A上的偏序关系，若对任意 $a, b \in A$，都有 $a \preceq b$ 或 $b \preceq a$，则称 $\preceq$ 是全序关系。

示例：实数集上的 $\leq$ 是全序关系；集合的 $\subseteq$ 一般不是全序关系。

8.3 哈斯图

定义：偏序关系的简化关系图称为哈斯图（Hasse Diagram）。

画法规则：

1. 去掉所有自环（自反性）
2. 去掉所有传递可以推出的边（传递性）
3. 去掉箭头，约定方向从下到上（反对称性）

示例：设 $A = \{1, 2, 3, 4, 6, 12\}$，R为整除关系

哈斯图如下：

1
2
3
4
5
6
7

  12
 / \
4   6
|   |
2   3
 \ /
  1

8.4 偏序集中的特殊元素

定义：设 $\langle A, \preceq \rangle$ 是偏序集，$B \subseteq A$。

要点：

• 极大元/极小元可能不唯一
• 最大元/最小元如果存在则唯一
• 最大元一定是极大元，反之不一定

8.5 寻找特殊元素的方法

在哈斯图中：

• 极小元：最底层的元素（没有向下的边）
• 极大元：最顶层的元素（没有向上的边）
• 最小元：比所有其他元素都小的唯一元素
• 最大元：比所有其他元素都大的唯一元素

示例：设 $B = \{2, 3, 4, 6\}$，整除关系

• 极小元：2, 3
• 极大元：4, 6
• 没有最小元和最大元

8.6 特殊元素的易混淆问题

注意：一个元素可以既是极大元又是极小元（当该元素与集合中其他元素都无关系时）。

8.7 链与反链

链的定义：偏序集 $\langle A, \preceq \rangle$ 的子集 $B \subseteq A$，若 $B$ 中每两个元素都有关系（即 $B$ 是全序的），则称 $B$ 为一条链。

反链的定义：偏序集 $\langle A, \preceq \rangle$ 的子集 $B \subseteq A$，若 $B$ 中每两个元素都没有关系（即任意两个不同元素不可比较），则称 $B$ 为一个反链。

要点：

• 单个元素的子集，既是链又是反链（约定，不能证明）
• 在哈斯图中，链是某条链上的点集，反链是若干个没有关系的点的集合
• 存在既非链也非反链的偏序集，例如 $\{2, 3, 4\}$ 上的整除关系

8.8 良序关系

定义：偏序集 $\langle A, \preceq \rangle$，若 $A$ 的每个非空子集都存在最小元素，则称 $\langle A, \preceq \rangle$ 为良序集，$\preceq$ 为良序关系。

性质：

• 良序集一定是全序集（线序集）
• 有限的全序集一定是良序集
• 无限的全序集不一定是良序集

反例：正实数集上的 $\leq$ 关系是全序但不是良序，因为开区间子集没有最小元素。

概念层次：

$\text{良序} \subseteq \text{线序（全序）} \subseteq \text{偏序} \subseteq \text{关系} \subseteq A \times A$

九、函数

9.1 函数的定义

定义：函数（映射）$f$ 是集合 $X$ 到集合 $Y$ 的一个关系，对于每一个 $x \in X$，有唯一的 $y \in Y$，使得 $\langle x, y \rangle \in f$，称关系 $f$ 为函数，记作：

$f: X \to Y \quad \text{或} \quad X \xrightarrow{f} Y$

其中 $y$ 记为 $f(x)$。

函数与关系的区别：

关系层次：函数 $\subset$ 关系 $\subset$ 笛卡尔乘积

9.2 函数相等

定义：函数 $f: X \to Y$，$g: A \to B$，若满足：

1. $X = A$ 且 $Y = B$
2. 对所有 $x \in X$，有 $f(x) = g(x)$

则称两个函数相等，记作 $f = g$。

9.3 满射、单射、双射

满射（Surjection）：$\forall y \in Y$，$\exists x \in X$，使得 $f(x) = y$。

即 $Y$ 中每个元素都有原像，值域等于 $Y$。

单射（Injection，也称入射）：$\forall x_1, x_2 \in X$，$x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$。

即不同的自变量映射到不同的函数值，等价于：$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$。

双射（Bijection，也称一一对应）：既是单射又是满射。

即 $X$ 与 $Y$ 的元素一一对应。

思考：

1. 存在既不是单射也不是满射的函数（例如常函数）
2. 两个有限集合之间存在双射，则两个集合的基数一定相等
3. 两个基数相等的有限集合之间一定可以定义一个双射
4. 两个基数为 $n$ 的集合之间，可以定义 $n!$ 个不同的双射

9.4 逆函数

问题：函数的逆关系一定是函数吗？

回答：只有双射才有逆函数。

定义：双射函数 $f: X \to Y$ 的逆函数 $f^{-1}: Y \to X$ 满足：

$f^{-1} = \{\langle y, x \rangle \mid \langle x, y \rangle \in f\}$

性质：

$(f^{-1})^{-1} = f$

即反函数就是逆函数。

9.5 复合函数

定义：函数 $f: X \to Y$，$g: W \to Z$，若 $f(X) \subseteq W$，则 $g$ 与 $f$ 的复合函数为：

$g \circ f = \{\langle x, z \rangle \mid x \in X \wedge z \in Z \wedge (\exists y)(y \in Y \wedge y = f(x) \wedge z = g(y))\}$

即 $(g \circ f)(x) = g(f(x))$，称函数 $g$ 在函数 $f$ 的左边可复合。

与复合关系的比较：

复合函数的性质：

1. 两个函数的复合是一个函数
2. 不是任何两个函数都可以复合（需要有公共集合）
3. 函数的复合是可结合的：$(f \circ g) \circ h = f \circ (g \circ h)$
4. 若 $g$ 和 $f$ 是满射（单射、双射），则 $g \circ f$ 也是满射（单射、双射）
5. $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$

9.6 特殊函数

常函数：$f: X \to Y$，$\exists y_0 \in Y$，对所有 $x \in X$ 有 $f(x) = y_0$。

常函数是满射（当 $|Y| = 1$ 时），一般既不是单射也不是满射。

恒等函数：$I_A: A \to A$，$I_A = \{\langle a, a \rangle \mid a \in A\}$

恒等函数的性质：

• 设 $f$ 是 $X$ 到 $Y$ 的函数：$f = f \circ I_X = I_Y \circ f$
• 设 $f$ 是 $X$ 到 $Y$ 的双射函数：$f^{-1} \circ f = I_X$，$f \circ f^{-1} = I_Y$

符号辨析：

本节小结

• 笛卡尔积：$A \times B$ 由所有有序对组成，$|A \times B| = |A| \times |B|$
• 二元关系：$A \times B$ 的子集，三种特殊关系（空关系、全域关系、恒等关系）
• 关系的表示：关系矩阵和关系图
• 五个性质：自反、反自反、对称、反对称、传递
• 关系的复合：$R \circ S$，先R后S
• 逆关系：$R^{-1}$，交换有序对的分量
• 闭包：自反闭包 $r(R) = R \cup I_A$，对称闭包 $s(R) = R \cup R^{-1}$，传递闭包 $t(R) = R \cup R^2 \cup \cdots$
• 闭包复合性质：$rs(R) = sr(R)$，$rt(R) = tr(R)$，$ts(R) \neq st(R)$
• 等价关系：自反+对称+传递，产生等价类和划分
• 偏序关系：自反+反对称+传递，可用哈斯图表示
• 链与反链：链中每两个元素都有关系，反链中每两个元素都无关系
• 良序关系：每个非空子集都有最小元素的偏序关系，良序 $\subseteq$ 全序 $\subseteq$ 偏序
• 覆盖：非空子集的并集等于A，每个元素至少属于一个分块
• 划分：非空子集的并集等于A且两两不相交，每个元素属于且仅属于一个分块
• 最大划分：每个元素构成一个分块；最小划分：全部元素组成一个分块
• 特殊元素：极大元、极小元、最大元、最小元、上界、下界、上确界、下确界
• 函数：特殊的二元关系，每个 $x$ 对应唯一的 $y$
• 满射：值域等于陪域；单射：不同自变量映射到不同函数值；双射：一一对应
• 逆函数：只有双射才有逆函数，$(f^{-1})^{-1} = f$
• 复合函数：$(g \circ f)(x) = g(f(x))$，$(g \circ f)^{-1} = f^{-1} \circ g^{-1}$
• 特殊函数：常函数、恒等函数 $I_A$，$f = f \circ I_X = I_Y \circ f$

练习题

练习1：关系性质综合判断

题目：设 $A = \{1, 2, 3\}$，判断以下关系的性质（自反/反自反/对称/反对称/传递）：

(1) $R_1 = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 1, 2 \rangle\}$

(2) $R_2 = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\}$

(3) $R_3 = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 1 \rangle, \langle 2, 2 \rangle\}$

(4) $R_4 = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle\}$

解：

分析：

• $R_1$：有 $\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle$，自反成立；有 $\langle 1,2 \rangle$ 但无 $\langle 2,1 \rangle$，不对称但反对称成立；传递性检查：$\langle 1,2 \rangle, \langle 2,2 \rangle \Rightarrow \langle 1,2 \rangle$ ✓，传递成立。
• $R_2$：无自环，反自反成立；$\langle 1,2 \rangle$ 但无 $\langle 2,1 \rangle$，反对称成立；$\langle 1,2 \rangle, \langle 2,3 \rangle$ 但无 $\langle 1,3 \rangle$，传递不成立。
• $R_3$：缺 $\langle 3,3 \rangle$，不自反；有 $\langle 1,1 \rangle$，不反自反；$\langle 1,2 \rangle$ 和 $\langle 2,1 \rangle$ 都有，对称成立；$\langle 1,2 \rangle$ 和 $\langle 2,1 \rangle$ 同时存在但 $1 \neq 2$，反对称不成立；$\langle 1,2 \rangle, \langle 2,1 \rangle \Rightarrow \langle 1,1 \rangle$ ✓，$\langle 2,1 \rangle, \langle 1,2 \rangle \Rightarrow \langle 2,2 \rangle$ ✓，传递成立。
• $R_4$：缺 $\langle 3,3 \rangle$，不自反；有 $\langle 1,1 \rangle$，不反自反；$\langle 1,1 \rangle$ 和 $\langle 2,2 \rangle$ 都是对称的；没有 $\langle 1,2 \rangle$ 和 $\langle 2,1 \rangle$ 同时出现，反对称成立；传递显然成立。

练习2：等价关系验证

题目：设集合 $T = \{1, 2, 3, 4\}$，$R = \{\langle 1,1 \rangle, \langle 1,4 \rangle, \langle 4,1 \rangle, \langle 4,4 \rangle, \langle 2,2 \rangle, \langle 2,3 \rangle, \langle 3,2 \rangle, \langle 3,3 \rangle\}$。验证 $R$ 是 $T$ 上的等价关系。

证明：

自反性：$\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 4,4 \rangle \in R$，每个结点都有自回路，自反性成立。

对称性：$\langle 1,4 \rangle \in R$ 且 $\langle 4,1 \rangle \in R$ ✓；$\langle 2,3 \rangle \in R$ 且 $\langle 3,2 \rangle \in R$ ✓；其余为自反对称。对称性成立。

传递性：逐个检查——$\langle 1,4 \rangle, \langle 4,1 \rangle \in R$，有 $\langle 1,1 \rangle \in R$ ✓；$\langle 4,1 \rangle, \langle 1,4 \rangle \in R$，有 $\langle 4,4 \rangle \in R$ ✓；$\langle 2,3 \rangle, \langle 3,2 \rangle \in R$，有 $\langle 2,2 \rangle \in R$ ✓；$\langle 3,2 \rangle, \langle 2,3 \rangle \in R$，有 $\langle 3,3 \rangle \in R$ ✓。传递性成立。

因此 $R$ 是 $T$ 上的等价关系。

等价类：$[1]_R = [4]_R = \{1, 4\}$，$[2]_R = [3]_R = \{2, 3\}$

商集：$T/R = \{\{1, 4\}, \{2, 3\}\}$

练习3：整数集上的等价关系

题目：设 $I$ 为整数集，$R = \{\langle a, b \rangle \mid a \equiv b \pmod{k}\}$（$k$ 为正整数）。证明 $R$ 是等价关系。

证明：设任意 $a, b, c \in I$。

(1) 自反性：因为 $a - a = 0 = k \cdot 0$，所以 $\langle a, a \rangle \in R$。

(2) 对称性：若 $a \equiv b \pmod{k}$，则 $a - b = kt$（$t$ 为整数），则 $b - a = k(-t)$，所以 $b \equiv a \pmod{k}$，即 $\langle b, a \rangle \in R$。

(3) 传递性：若 $a \equiv b \pmod{k}$，$b \equiv c \pmod{k}$，则 $a - b = ks_1$，$b - c = ks_2$（$s_1, s_2$ 为整数），$a - c = (a - b) + (b - c) = k(s_1 + s_2)$，所以 $a \equiv c \pmod{k}$，即 $\langle a, c \rangle \in R$。

因此 $R$ 是等价关系。

练习4：偏序关系与哈斯图

题目：设 $A$ 是正整数 $m = 12$ 的因子的集合，$|$ 为整除关系。求 $\text{COV}(A)$（盖住关系），并画出哈斯图。

解：$m = 12$ 的因子集合 $A = \{1, 2, 3, 4, 6, 12\}$。

整除关系 $|$ 包含：$\langle 1,2 \rangle, \langle 1,3 \rangle, \langle 1,4 \rangle, \langle 1,6 \rangle, \langle 1,12 \rangle, \langle 2,4 \rangle, \langle 2,6 \rangle, \langle 2,12 \rangle, \langle 3,6 \rangle, \langle 3,12 \rangle, \langle 4,12 \rangle, \langle 6,12 \rangle$ 及所有自反对。

盖住关系 $\text{COV}(A)$：$x | y$ 且 $x \neq y$，且不存在 $z$ 使 $x | z$ 且 $z | y$。

$\text{COV}(A) = \{\langle 1,2 \rangle, \langle 1,3 \rangle, \langle 2,4 \rangle, \langle 2,6 \rangle, \langle 3,6 \rangle, \langle 4,12 \rangle, \langle 6,12 \rangle\}$

哈斯图：

1
2
3
4
5
6
7

  12
 / \
4   6
|   |
2   3
 \ /
  1

练习5：特殊元素判断

题目：在练习4的偏序集 $\langle A, | \rangle$ 中，设 $B = \{2, 3, 4, 6\}$，求 $B$ 的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。

解：

• 极小元：2, 3（$B$ 中没有比它们更小的元素）
• 极大元：4, 6（$B$ 中没有比它们更大的元素）
• 最小元：不存在（2 和 3 不可比较）
• 最大元：不存在（4 和 6 不可比较）
• 上界：12（$12$ 能被 2, 3, 4, 6 整除）
• 下界：1（1 能整除 2, 3, 4, 6）
• 上确界：12（最小的上界）
• 下确界：1（最大的下界）

关键术语速查