Relation

关系专题笔记 / Relations Notes#

0. 关系题总策略 / General Strategy for Relation Problems#

0.1 关系的本质 / What a Relation Really Is#

Core idea / 核心思想

关系不是一种神秘的新对象，它就是笛卡尔积中的某些有序对。

A relation is not a mysterious new object. It is simply a chosen subset of a Cartesian product.

若 $R$ 是从 $A$ 到 $B$ 的关系，则：

若 $R$ 是集合 $A$ 上的关系，则：

Notation / 记号

$(a,b)\in R$ 常写作：

The notation $aRb$ means that $a$ is related to $b$ by $R$. Direction matters, so $aRb$ and $bRa$ are usually different statements.

0.2 标准问题 / Standard Questions#

1. 关系在哪两个集合之间？/ What are the domain and codomain?
2. 关系是否在同一个集合上？/ Is it a relation on one set?
3. 有序对的方向是否重要？/ Does direction matter?
4. 要判断的是哪种性质？/ Which property is being tested?
5. 能否用矩阵或图表示？/ Can it be represented by a matrix or a digraph?
6. 题目要的是原关系、闭包、等价类还是偏序结构？/ Does the problem ask for the relation itself, a closure, equivalence classes, or a poset structure?
7. 要证明“所有元素都满足”，还是找一个反例即可？/ Do we need a universal proof or only one counterexample?

0.3 方法表 / Method Checklist#

1. Relations and Their Properties / 关系及其性质#

对应 Rosen 9.1。本节先给出 relation 的基本定义和英文词汇，再整理 relation properties、relation counting、combining relations、composition 和 powers。

1.1 二元关系 / Binary Relation#

Definition / 定义

从集合 $A$ 到集合 $B$ 的二元关系是 $A\times B$ 的一个子集：

A binary relation from $A$ to $B$ is a subset of $A\times B$.

若 $A=B$，则称 $R$ 是 $A$ 上的关系：

Example / 例子

设：

则：

是从 $A$ 到 $B$ 的关系。

Use / 怎么用

看到关系题时，第一步一定要确认底层集合。很多性质依赖底层集合，而不只依赖列出的有序对。

The first step is always to identify the underlying sets. Many properties depend on the whole set, not only on the listed pairs.

关系 $R\subseteq A\times B$ 也可以直接画成从 $A$ 指向 $B$ 的箭头图。若 $(a,b)\in R$，就画一条 arrow from $a$ to $b$。

A relation can be viewed as an arrow diagram: $(a,b)\in R$ means an arrow from $a$ to $b$.

这个图像化理解的好处是：

• 函数 / function = 每个输入点至多一条箭头出去。
• 全关系性质 / totality = 每个输入点至少一条箭头出去。
• 单射 / injective = 每个目标点至多一条箭头进来。
• 满射 / surjective = 每个目标点至少一条箭头进来。

1.2 定义域、陪域、值域 / Domain, Codomain, Range#

Domain / 定义域

若 $R\subseteq A\times B$，则 $A$ 称为关系的定义域 / domain。

The domain is the set of possible first coordinates.

Codomain / 陪域

若 $R\subseteq A\times B$，则 $B$ 称为关系的陪域 / codomain。

The codomain is the set of possible second coordinates.

Range / 值域

关系 $R$ 的值域 / range 是实际被关系连到的 $B$ 中元素：

The range is the set of elements of $B$ that actually appear as outputs or targets.

Warning / 注意

陪域 / codomain 不一定等于值域 / range。陪域是允许出现的目标集合，值域是实际出现的目标集合。

The codomain is allowed targets; the range is actual targets.

Example / 例子

设：

则：

这里 $z$ 在陪域中，但不在值域中。

1.3 像与原像 / Image and Preimage#

Image of an element / 元素的像

对 $a\in A$，$a$ 在关系 $R$ 下的像 / image 是：

如果 $R$ 是函数，$R(a)$ 至多只有一个元素；如果 $R$ 是一般关系，$R(a)$ 可以有多个元素。

Image of a set / 集合的像

对 $S\subseteq A$，$S$ 的像 / image 为：

Preimage / 原像

对 $T\subseteq B$，$T$ 的原像 / preimage 为：

Use / 怎么用

像 / image 是“从左往右能到哪里”；原像 / preimage 是“从右往左看哪些元素能到这里”。

Image asks where elements go; preimage asks which elements can reach a target set.

1.4 集合上关系的例子 / Examples of Relations on a Set#

Equality / 相等关系

在任意集合 $A$ 上：

This is the equality relation.

Less than or equal to / 小于等于

在 $\mathbb{R}$ 上：

Divisibility / 整除

在正整数集 $\mathbb{Z}^+$ 上：

Congruence / 同余

在整数集 $\mathbb{Z}$ 上：

1.5 函数是特殊关系 / Functions as Special Relations#

Definition / 定义

关系 $R\subseteq A\times B$ 是函数，当且仅当每个 $a\in A$ 至多对应一个 $b\in B$。

A relation $R\subseteq A\times B$ is a function if every $a\in A$ is related to at most one element of $B$.

若还要求每个 $a\in A$ 至少对应一个 $b\in B$，则它是全函数 / total function。

Function condition / 函数条件

若 $aRb_1$ 且 $aRb_2$，则必须有：

Example / 例题

设：

$R_1$ 是从 $A$ 到 $B$ 的全函数；$R_2$ 不是函数，因为 $1$ 同时对应 $x$ 和 $y$。

Use / 怎么用

函数题可以翻译成关系题：函数要求“每个输入至多一个输出”；全函数要求“每个输入恰好一个输出”。

1.6 单射、满射、双射 / Injective, Surjective, Bijective#

把函数看成关系时，很多英文词汇都可以用“箭头”理解。

When a function is viewed as a relation, the standard function terms can be understood by arrows.

Total / 全的

关系 $R\subseteq A\times B$ 是 total，若每个 $a\in A$ 至少有一个箭头出去：

Injective / 单射的 / one-to-one

关系 $R\subseteq A\times B$ 是 injective，若每个 $b\in B$ 至多有一个 $a\in A$ 指向它：

Injective 也常叫 one-to-one。

Surjective / 满射的 / onto

关系 $R\subseteq A\times B$ 是 surjective，若每个 $b\in B$ 至少被一个 $a\in A$ 指向：

Surjective 也常叫 onto。

Bijective / 双射的

一个 total function 若同时 injective 和 surjective，则称为 bijective / bijection。

Counting use / 计数用途

若 $A,B$ 有限：

• total injection / 全单射 给出 $|A|\le |B|$。
• surjective function / 满射函数 给出 $|A|\ge |B|$。
• bijection / 双射 给出 $|A|=|B|$。

1.7 常见特殊关系 / Common Special Relations#

设 $R$ 是集合 $A$ 上的关系。

Identity relation / 恒等关系

Identity relation 只包含所有自环，是“相等关系”的集合表示。

Universal relation / 全关系

Universal relation 包含所有可能的有序对。

Empty relation / 空关系

Empty relation 不包含任何有序对。

Inverse relation / 逆关系

若 $R\subseteq A\times B$，则逆关系 / inverse relation 为：

逆关系把每个有序对的方向反过来。

Complement relation / 补关系

若 $R\subseteq A\times B$，则补关系 / complement relation 为：

Complement relation 依赖底层全集 $A\times B$，所以必须先确认 domain 和 codomain。

Restriction / 限制

若 $S\subseteq A$，则 $R$ 在 $S$ 上的限制 / restriction 常写为：

Restriction means we only keep pairs whose coordinates lie in the smaller set.

1.8 关系的基本性质 / Basic Properties of Relations#

设 $R$ 是集合 $A$ 上的关系。

1.9 性质定义表 / Property Table#

1.10 自反与反自反 / Reflexive and Irreflexive#

Reflexive / 自反

Irreflexive / 反自反

Important / 注意

一个非空集合上的关系不可能同时自反和反自反。

On a nonempty set, a relation cannot be both reflexive and irreflexive.

Example / 例子

在 $\mathbb{Z}$ 上，$\le$ 是自反的，因为 $a\le a$。
在 $\mathbb{Z}$ 上，$<$ 是反自反的，因为不存在 $a<a$。

1.11 对称、反对称、非对称 / Symmetric, Antisymmetric, and Asymmetric#

Symmetric / 对称

Antisymmetric / 反对称

Asymmetric / 非对称

Key distinction / 核心区别

反对称不是“没有反向边”。反对称允许 $(a,a)$，也允许单向边 $(a,b)$。它只禁止不同元素之间同时出现 $(a,b)$ 和 $(b,a)$。

Antisymmetric does not mean "no reverse edges at all." It only forbids two-way edges between distinct elements.

非对称更强：如果有 $aRb$，就不能有 $bRa$。因此非对称关系一定反自反。

Asymmetry is stronger: if $aRb$, then $bRa$ is impossible. Hence every asymmetric relation is irreflexive.

1.12 传递 / Transitive#

Definition / 定义

Graph intuition / 图像理解

若存在 $a\to b$ 和 $b\to c$，就必须存在 $a\to c$。

If there is a directed path of length $2$ from $a$ to $c$, then the shortcut edge $a\to c$ must be present.

Important / 注意

传递性不是说“有 $a\to c$ 就必须存在中间点”。它只检查已经存在的两步链。

Transitivity does not say that every edge must come from a two-step path. It says that every existing two-step path must have the corresponding shortcut.

1.13 性质判定例题 / Example: Checking Properties#

设：

Reflexive / 自反

有 $(1,1),(2,2),(3,3)$，所以自反。

Symmetric / 对称

有 $(2,3)$，但没有 $(3,2)$，所以不对称。

Antisymmetric / 反对称

有 $(1,2)$ 和 $(2,1)$，且 $1\ne2$，所以不反对称。

Transitive / 传递

需要逐项检查两步链。例如 $(1,2)$ 与 $(2,3)$ 要求 $(1,3)$，已存在；$(2,1)$ 与 $(1,2)$ 要求 $(2,2)$，已存在。检查所有两步链后可知它是传递的。

Use / 怎么用

有限集合上判断传递性时，不要只看一两个例子。系统做法是列出所有 $aRb$ 和 $bRc$ 的组合，或用矩阵布尔平方检查。

1.14 关系的数量 / Counting Relations#

1.15 所有关系的数量 / Number of All Relations#

Theorem / 定理

若 $|A|=m$，$|B|=n$，则从 $A$ 到 $B$ 的关系共有：

个。

If $|A|=m$ and $|B|=n$, then there are $2^{mn}$ relations from $A$ to $B$.

Proof / 证明

$A\times B$ 中共有 $mn$ 个有序对。一个关系就是从这些有序对中任意选择一部分，因此关系数等于幂集大小：

A relation is any subset of $A\times B$, so the number of relations is the number of subsets of a set with $mn$ elements.

1.16 集合上关系的数量 / Relations on One Set#

若 $|A|=n$，则 $A$ 上的关系共有：

个。

因为 $A\times A$ 中有 $n^2$ 个有序对。

1.17 常见性质关系的计数 / Counting Relations with Common Properties#

设 $|A|=n$。

Reflexive relations / 自反关系

自反关系必须包含所有 $(a,a)$，共 $n$ 个。其余 $n^2-n$ 个有序对可选或不选：

Irreflexive relations / 反自反关系

反自反关系不能包含任何 $(a,a)$。其余 $n^2-n$ 个有序对可选或不选：

Symmetric relations / 对称关系

主对角线上的 $n$ 个有序对各自独立；每一对不同元素 $\{a,b\}$ 对应 $(a,b)$ 和 $(b,a)$，要么都选，要么都不选。不同元素无序对有 $\binom n2$ 个，所以：

Reflexive and symmetric relations / 自反且对称关系

主对角线必须全选；不同元素无序对仍各自独立：

Use / 怎么用

计数关系时先数“自由选择的单位”。普通关系的单位是单个有序对；对称关系的单位是一个无序二元组对应的一对方向。

When counting relations, first identify the independent choice units. For arbitrary relations, the units are ordered pairs. For symmetric relations, the units are unordered pairs of distinct elements.

1.18 关系复合与关系幂 / Composition and Powers of Relations#

1.19 关系复合 / Composition of Relations#

Definition / 定义

若：

则复合关系 $S\circ R\subseteq A\times C$ 定义为：

In words, $a$ is related to $c$ by $S\circ R$ if we can go from $a$ to some $b$ using $R$, then from $b$ to $c$ using $S$.

Order warning / 顺序警告

$S\circ R$ 表示先走 $R$，再走 $S$。这和函数复合的读法一致：

1.20 复合例题 / Example of Composition#

设：

则：

因为 $1$ 可经 $x$ 到 $p$，也可经 $y$ 到 $q$；$2$ 可经 $y$ 到 $q$。

1.21 关系幂 / Powers of a Relation#

设 $R$ 是集合 $A$ 上的关系。

Definition / 定义

Path interpretation / 路径解释

$(a,b)\in R^n$ 当且仅当从 $a$ 到 $b$ 存在长度为 $n$ 的有向走路。

$(a,b)\in R^n$ iff there is a directed walk of length $n$ from $a$ to $b$.

Use / 怎么用

关系幂用于把“多步可达”翻译成代数形式。传递闭包就是所有正长度路径的并。

1.22 关系的并、交、差和补 / Union, Intersection, Difference, and Complement#

若 $R_1,R_2$ 都是从 $A$ 到 $B$ 的关系，则可以像集合一样组合它们：

Because relations are sets of ordered pairs, union, intersection, difference, and complement are ordinary set operations on ordered pairs.

Complement / 补关系

补关系必须相对于同一个全集 $A\times B$：

Use / 怎么用

题目若说“关系的 complement”，必须先看清楚 relation from $A$ to $B$ 的 $A,B$ 是什么。

2. n-ary Relations and Their Applications / n 元关系及其应用#

对应 Rosen 9.2。数据库表、selection、projection、join 等内容放在这里。

2.1 n 元关系 / n-ary Relations#

Definition / 定义

$n$ 元关系是笛卡尔积：

的子集。

An $n$-ary relation is a subset of $A_1\times A_2\times\cdots\times A_n$.

数据库表可以看成 $n$ 元关系：每一行是一个 $n$ 元组，每一列对应一个属性。

A database table can be viewed as an $n$-ary relation: each row is an $n$-tuple, and each column is an attribute.

Tuple / 元组

表中的一行称为 tuple / 元组。例如学生表中一行：

就是一个 $4$-tuple。

Attribute / 属性

表中的一列称为 attribute / 属性，例如 name、major、grade。

Primary key / 主键

能唯一确定一行的属性或属性组称为 primary key / 主键。Rosen 的数据库关系题常要求判断某些属性能否唯一标识 tuple。

2.2 选择、投影、连接 / Selection, Projection, and Join#

Selection / 选择

选择操作按条件筛选行。

Selection keeps rows satisfying a condition.

Projection / 投影

投影操作保留某些列，丢弃其他列。关系模型中重复行通常只保留一份。

Projection keeps selected columns and discards the rest. Duplicate rows are usually removed in the relation model.

Join / 连接

连接操作按共同属性把两个关系的行匹配并合并。

Join combines rows from two relations by matching common attributes.

Use / 怎么用

数据库题通常不是让你写 SQL，而是把表操作翻译成集合、元组和关系操作。

Database-style problems usually ask you to translate table operations into set, tuple, and relation operations.

3. Representing Relations / 关系的表示#

对应 Rosen 9.3。重点是 ordered pairs、zero-one matrices、directed graphs，以及如何从表示中判断性质。

3.1 有序对表示 / Ordered Pair Representation#

最直接的表示方法是列出所有属于关系的有序对。

The most direct representation is listing all ordered pairs in the relation.

Example / 例子

这种表示适合小集合，但集合较大时不够直观。

3.2 矩阵表示 / Matrix Representation#

设：

关系 $R\subseteq A\times B$ 的矩阵 $M_R$ 定义为：

若 $R$ 是 $A$ 上的关系，则 $M_R$ 是 $n\times n$ 方阵。

Property checks by matrix / 用矩阵判断性质

• 自反 / reflexive: 主对角线全为 $1$。
• 反自反 / irreflexive: 主对角线全为 $0$。
• 对称 / symmetric: $M_R=M_R^T$。
• 反对称 / antisymmetric: 若 $i\ne j$，不能同时有 $m_{ij}=m_{ji}=1$。
• 传递 / transitive: 若布尔积 $M_R\odot M_R$ 中 $(i,j)$ 为 $1$，则 $M_R$ 中 $(i,j)$ 也必须为 $1$。

3.3 有向图表示 / Digraph Representation#

集合 $A$ 上的关系可以看成一个有向图：

• 顶点是 $A$ 中元素 / vertices are elements of $A$.
• 若 $(a,b)\in R$，则画边 $a\to b$ / draw an edge $a\to b$.

Graph checks / 用图判断

• 自反：每个点有自环。
• 对称：每条边都有反向边。
• 反对称：不同点之间没有双向边。
• 传递：每条长度为 $2$ 的路径都有对应捷径边。

Use / 怎么用

矩阵适合计算，图适合理解结构。闭包和传递性常在两种表示之间切换。

Matrices are good for computation; graphs are good for structure. Closure and transitivity often become clearer by switching between the two.

3.4 邻接矩阵与走路计数矩阵 / Adjacency Matrix and Walk Counting Matrix#

关系矩阵也可以用于数 walks / 走路。若 $A_G$ 是有向图 $G$ 的 adjacency matrix / 邻接矩阵，则：

等于从顶点 $i$ 到顶点 $j$ 的长度为 $k$ 的 walk 的数量。

The $(i,j)$ entry of $A_G^k$ counts the number of length-$k$ walks from $i$ to $j$.

Proof idea / 证明思路

长度 $k+m$ 的 walk 可以唯一拆成：先走长度 $k$ 到某个中间点 $r$，再从 $r$ 走长度 $m$ 到终点。因此：

这正是矩阵乘法。

Boolean version / 布尔版本

若把矩阵普通加法和乘法换成布尔或 / or 与布尔与 / and，就不再计算 walk 的数量，而是判断是否存在可达路径。

4. Closures of Relations / 关系闭包#

对应 Rosen 9.4。自反闭包、对称闭包、传递闭包和 Warshall 算法放在同一节。

4.1 闭包的定义 / Definition of Closure#

Definition / 定义

设 $P$ 是某种关系性质。关系 $R$ 关于性质 $P$ 的闭包是包含 $R$ 的、满足 $P$ 的最小关系。

The closure of $R$ with respect to a property $P$ is the smallest relation that contains $R$ and has property $P$.

“最小”指的是按集合包含关系最小，不是有序对个数随便少。

"Smallest" means smallest under set inclusion.

4.2 自反闭包 / Reflexive Closure#

设 $R$ 是 $A$ 上的关系。自反闭包为：

其中：

Matrix view / 矩阵表示

把主对角线全改为 $1$。

Graph view / 图表示

给每个顶点加自环。

4.3 对称闭包 / Symmetric Closure#

对称闭包为：

其中：

Matrix view / 矩阵表示

Graph view / 图表示

每条有向边都补一条反向边。

4.4 传递闭包 / Transitive Closure#

传递闭包记作 $R^+$，表示所有正长度路径的可达关系。

若 $A$ 有 $N$ 个元素，则：

若还要自反传递闭包，则：

Why stop at $N$? / 为什么到 $N$ 为止？

在 $N$ 个顶点的有限图中，若存在一条从 $a$ 到 $b$ 的路径，则存在一条不重复顶点的简单路径，长度至多为 $N-1$；如果考虑自环或走路，超过 $N$ 的信息已经不会产生新的可达性。

In a finite graph with $N$ vertices, reachability can be witnessed by a simple path of length at most $N-1$. Longer walks do not create new reachability information.

若 $G$ 是一个有向图，则 walk relation / 可走关系 $G^*$ 定义为：

positive walk relation / 正长度可走关系 $G^+$ 定义为：

在 relation 语言中，$G^+$ 就是边关系的 transitive closure，$G^*$ 是 reflexive transitive closure。

4.5 闭包例题 / Closure Example#

设：

Reflexive closure / 自反闭包

Symmetric closure / 对称闭包

Transitive closure / 传递闭包

因为 $(1,2)$ 和 $(2,3)$ 给出路径 $1\to2\to3$，需要加入 $(1,3)$：

4.6 Warshall 算法目标 / Goal of Warshall's Algorithm#

Warshall 算法用于从关系矩阵求传递闭包矩阵。

Warshall's algorithm computes the matrix of the transitive closure of a relation.

输入是 $n\times n$ 的 $0$-$1$ 矩阵 $W^{(0)}=M_R$。

4.7 更新公式 / Update Formula#

逐个允许顶点 $1,2,\ldots,k$ 作为中间点：

Meaning / 含义

从 $i$ 到 $j$ 的路径若只允许使用前 $k$ 个顶点作为中间点，则它要么不经过第 $k$ 个点，要么可以拆成：

4.8 证明思路 / Proof Idea#

Proof / 证明

考虑所有从 $i$ 到 $j$ 且中间点只来自 $\{1,\ldots,k\}$ 的路径。

若路径不经过 $k$，则它已经在 $W^{(k-1)}$ 中被记录。

若路径经过 $k$，则可以把第一次到达 $k$ 前后的路径分成两段：从 $i$ 到 $k$，以及从 $k$ 到 $j$。这两段的中间点都只来自 $\{1,\ldots,k-1\}$，所以由：

记录。

两种情况取逻辑或，得到更新式。

4.9 手算模板 / Hand Calculation Template#

1. 写出初始矩阵 $W^{(0)}=M_R$。
2. 对 $k=1,2,\ldots,n$ 逐轮更新。
3. 第 $k$ 轮只关心所有满足 $i\to k$ 且 $k\to j$ 的位置，把 $i\to j$ 置为 $1$。
4. 最终 $W^{(n)}$ 就是传递闭包矩阵。

Use / 怎么用

手算时不要机械枚举所有 $i,j$。更快的方法是：第 $k$ 轮找“能到 $k$ 的行”和“$k$ 能到的列”，这些交叉位置都改成 $1$。

When doing it by hand, find the rows that can reach $k$ and the columns reachable from $k$; set their intersections to $1$.

5. Equivalence Relations / 等价关系#

对应 Rosen 9.5。重点是 equivalence classes、partitions 和 quotient set。

5.1 定义 / Definition#

关系 $R$ 是集合 $A$ 上的等价关系，当且仅当它满足：

1. 自反 / reflexive.
2. 对称 / symmetric.
3. 传递 / transitive.

An equivalence relation captures the idea of "being the same in some relevant sense."

它可以理解为“像等号一样”的关系，用来表示某种意义下的 sameness / 相同或 equivalence / 等价。

5.2 标准例子 / Standard Examples#

Congruence modulo $m$ / 模 $m$ 同余

在 $\mathbb{Z}$ 上：

这是等价关系。

Same length / 字符串同长度

在所有字符串集合上：

这是等价关系。

Same connected component / 同一连通分量

在无向图顶点集上：

这是等价关系。

5.3 等价类 / Equivalence Classes#

Definition / 定义

若 $R$ 是 $A$ 上的等价关系，则 $a$ 的等价类为：

有些教材也写成：

对于等价关系，由于对称性，这两种写法等价。

Use / 怎么用

等价类就是“和 $a$ 等价的所有元素组成的集合”。找等价类时，通常先找判定标准：同余的余数、字符串长度、连通分量编号等。

5.4 等价关系与划分 / Equivalence Relations and Partitions#

Theorem / 定理

集合 $A$ 上的每个等价关系都决定 $A$ 的一个划分；反过来，$A$ 的每个划分都定义一个等价关系。

Every equivalence relation on $A$ determines a partition of $A$, and every partition of $A$ defines an equivalence relation.

Proof / 证明

先设 $R$ 是等价关系。

自反性说明每个元素 $a$ 都属于自己的等价类 $[a]$，所以所有等价类覆盖 $A$。

若两个等价类有交集，设：

则 $zRa$ 且 $zRb$。由对称性得 $aRz$，再由传递性和 $zRb$ 得 $aRb$。接下来可证 $[a]=[b]$：若 $x\in[a]$，则 $xRa$，又 $aRb$，所以 $xRb$，即 $x\in[b]$；反向同理。因此两个等价类要么相等，要么不相交。

所以等价类构成 $A$ 的划分。

反过来，若给定 $A$ 的一个划分，定义：

同一个元素必在同一块中，所以自反；同块关系不分顺序，所以对称；若 $a,b$ 同块且 $b,c$ 同块，则 $a,c$ 同块，所以传递。因此 $R$ 是等价关系。

5.5 模同余例题 / Example: Congruence Classes#

在 $\mathbb{Z}$ 上定义：

Equivalence classes / 等价类

共有四个等价类：

这些等价类按除以 $4$ 的余数划分整数集。

Use / 怎么用

题目问商集 / quotient set 时，答案通常是所有等价类构成的集合：

5.6 由函数产生的等价关系 / Equivalence Relation Induced by a Function#

任意 total function / 全函数 都会自然诱导一个 equivalence relation / 等价关系。

设 $f:A\to B$ 是 total function，定义：

则 $\equiv_f$ 是 $A$ 上的等价关系。

Proof / 证明

因为相等关系 $=$ 自反、对称、传递：

• 自反：$f(a)=f(a)$，所以 $a\equiv_f a$。
• 对称：若 $f(a)=f(a')$，则 $f(a')=f(a)$。
• 传递：若 $f(a)=f(a')$ 且 $f(a')=f(a'')$，则 $f(a)=f(a'')$。

Use / 怎么用

这说明很多等价关系本质上是在问“某个不变量是否相同”。例如：

• $a\equiv b\pmod m$ 等价于“余数函数的值相同”。
• 两个字符串长度相同，等价于“length function 的值相同”。
• 图中同一连通分量，等价于“component label 的值相同”。

5.7 强连通关系 / Strong Connectivity Relation#

在有向图中常用 strong connectivity relation / 强连通关系：

也就是说，$u$ 能到 $v$，且 $v$ 也能到 $u$。

在有向图中，strong connectivity relation 是等价关系；它的等价类就是 strongly connected components / 强连通分量。

6. Partial Orderings / 偏序#

对应 Rosen 9.6。偏序、全序、Hasse 图、极大/极小、上下界、格、链、反链和拓扑排序都放在这里。

6.1 定义 / Definition#

关系 $R$ 是集合 $A$ 上的偏序，当且仅当它满足：

1. 自反 / reflexive.
2. 反对称 / antisymmetric.
3. 传递 / transitive.

偏序通常记作 $\preceq$。

A partial order captures an ordering in which not every two elements need to be comparable.

若 $R$ 是 $A$ 上的偏序，则 $(A,R)$ 称为偏序集 / partially ordered set, poset。

6.2 strict partial order 与 weak partial order#

partial ordering 通常指自反、反对称、传递的关系。进一步区分时，可把偏序分成 strict partial order / 严格偏序 和 weak partial order / 弱偏序。

Strict partial order / 严格偏序

严格偏序满足：

1. irreflexive / 反自反。
2. transitive / 传递。

等价地，也可说它满足 transitive + asymmetric。

典型例子：

Weak partial order / 弱偏序

弱偏序满足：

1. reflexive / 自反。
2. antisymmetric / 反对称。
3. transitive / 传递。

这就是本章 partial ordering 的主要定义。

典型例子：

Connection / 联系

若 $<$ 是严格偏序，则加入所有自环得到弱偏序：

若 $\le$ 是弱偏序，则去掉相等部分得到严格偏序：

6.3 标准例子 / Standard Examples#

Subset order / 子集偏序

Divisibility order / 整除偏序

Prerequisite order / 先修关系

若课程 $a$ 必须在课程 $b$ 前完成，可写作：

当依赖图没有环时，这给出偏序。

若 $G$ 是 DAG / directed acyclic graph，则：

定义了一个 weak partial order。

若只允许 positive-length walk，则得到 strict partial order：

这个观点常用于 prerequisite graph / 先修关系图 和 scheduling / 调度问题。

6.4 偏序证明模板 / Template for Proving a Partial Order#

要证明 $\preceq$ 是偏序，依次证明：

Reflexive / 自反

任取 $a\in A$，证明：

Antisymmetric / 反对称

任取 $a,b\in A$，假设：

推出：

Transitive / 传递

任取 $a,b,c\in A$，假设：

推出：

6.5 整除关系例题 / Example: Divisibility#

在 $\mathbb{Z}^+$ 上定义：

Proof / 证明

自反：对任意 $a\in\mathbb{Z}^+$，有 $a\mid a$，因为 $a=1\cdot a$。

反对称：若 $a\mid b$ 且 $b\mid a$，则存在正整数 $m,n$ 使：

代入得：

因为 $a>0$，所以 $nm=1$。正整数中只有 $n=m=1$，于是 $a=b$。

传递：若 $a\mid b$ 且 $b\mid c$，则存在正整数 $m,n$ 使：

所以：

因此 $a\mid c$。

所以整除关系是偏序。

6.6 可比较与全序 / Comparable and Total Order#

设 $(P,\preceq)$ 是偏序集，$S\subseteq P$。

Comparable / 可比较

元素 $a,b$ 可比较，当且仅当：

Incomparable / 不可比较

若二者都不成立，则 $a,b$ 不可比较。

Total order / 全序

若 $P$ 中任意两个元素都可比较，则 $\preceq$ 是全序 / total order 或 linear order。

Example / 例子

$(\mathbb{Z},\le)$ 是全序。
$(\mathcal{P}(\{1,2\}),\subseteq)$ 不是全序，因为 $\{1\}$ 和 $\{2\}$ 不可比较。

Linear extension / 线性扩张

若一个全序 $\le_L$ 保留偏序 $\preceq$ 中所有原有比较关系，即：

则称 $\le_L$ 是 $\preceq$ 的 linear extension / 线性扩张。

拓扑排序就是有限偏序或 DAG 的一种 linear extension。

Lexicographic order / 字典序

Rosen 偏序部分常出现 lexicographic order / 字典序。对有序对 $(a_1,a_2)$ 和 $(b_1,b_2)$，字典序先比较第一坐标，第一坐标相同再比较第二坐标：

当且仅当：

字典序通常是 total order / 全序，只要每个坐标上的原顺序是全序。

6.7 极大、最大、极小、最小 / Maximal, Maximum, Minimal, Minimum#

Maximal element / 极大元

$m\in S$ 是极大元，若不存在 $s\in S$ 使：

也就是说，在 $S$ 中没有比它更大的可比较元素。

Maximum element / 最大元

$M\in S$ 是最大元，若对所有 $s\in S$：

Minimal element / 极小元

$m\in S$ 是极小元，若不存在 $s\in S$ 使：

Minimum element / 最小元

$m\in S$ 是最小元，若对所有 $s\in S$：

Key distinction / 核心区别

最大元一定是极大元，但极大元不一定是最大元。最大元若存在则唯一；极大元可以有多个。

A maximum element is always maximal, but a maximal element need not be maximum. A maximum, if it exists, is unique; maximal elements may be multiple.

6.8 上界、下界、最小上界、最大下界 / Bounds, LUB, and GLB#

Upper bound / 上界

$u\in P$ 是 $S$ 的上界，若对所有 $s\in S$：

Lower bound / 下界

$\ell\in P$ 是 $S$ 的下界，若对所有 $s\in S$：

Least upper bound / 最小上界

$S$ 的最小上界是所有上界中的最小者，记作：

或 join。

Greatest lower bound / 最大下界

$S$ 的最大下界是所有下界中的最大者，记作：

或 meet。

6.9 格 / Lattice#

Definition / 定义

若偏序集中任意两个元素都有最小上界和最大下界，则称该偏序集为格 / lattice。

A poset is a lattice if every pair of elements has both a least upper bound and a greatest lower bound.

Examples / 例子

在 $(\mathcal{P}(A),\subseteq)$ 中：

在正整数的整除偏序中：

6.10 链、反链和 Dilworth 型结论 / Chains, Antichains, and Dilworth-Type Results#

Chain / 链

偏序集中的 chain / 链 是一个子集，其中任意两个元素都可比较。

A chain is a subset in which every two elements are comparable.

Antichain / 反链

偏序集中的 antichain / 反链 是一个子集，其中任意两个不同元素都不可比较。

An antichain is a subset in which no two distinct elements are comparable.

在 DAG scheduling / DAG 调度中：

• chain 表示一串必须依次完成的任务。
• antichain 表示一批彼此没有先后依赖、原则上可并行的任务。
• critical path / 关键路径 是最长依赖链，决定无限处理器下的最短并行时间。

Dilworth-type statement / Dilworth 型结论

一个常用的 Dilworth-type statement / Dilworth 型结论是：若一个 DAG 有 $n$ 个顶点，则对任意 $t>0$，它要么有长度大于 $t$ 的 chain，要么有大小至少 $n/t$ 的 antichain。

取 $t=\sqrt n$，可得：

这类结论常用于证明“要么有很长的依赖链，要么有很大的可并行集合”。

6.11 Hasse 图的画法 / How to Draw a Hasse Diagram#

Hasse 图是偏序的简化图。

A Hasse diagram is a simplified diagram of a finite poset.

画法：

1. 去掉所有自环 / remove all loops.
2. 去掉由传递性推出的边 / remove transitive edges.
3. 若 $a\prec b$，把 $b$ 画在 $a$ 上方 / draw larger elements higher.
4. 边默认向上，不再画箭头 / edges are understood to point upward.

6.12 覆盖关系 / Cover Relation#

若 $a\prec b$，且不存在 $c$ 使：

则称 $b$ 覆盖 $a$，记作 $a\lessdot b$。

Hasse 图只画覆盖关系。

The Hasse diagram draws only cover relations.

6.13 整除偏序 Hasse 图例题 / Example: Divisibility Poset#

设：

按整除关系排序。

覆盖关系为：

不画 $1\to6$，因为 $1\mid2$ 且 $2\mid6$，它由传递性推出。

Structure / 结构

• 最小元 / minimum: $1$.
• 最大元 / maximum: $6$.
• $2$ 与 $3$ 不可比较 / $2$ and $3$ are incomparable.

6.14 子集偏序例题 / Example: Subset Poset#

设：

元素为：

覆盖关系为：

这是一个菱形结构。

6.15 拓扑排序 / Topological Sorting#

拓扑排序是把偏序或 DAG 中的元素排成一个线性序，使得所有依赖关系都被保留。

A topological ordering is a linear ordering of a poset or DAG that respects all precedence constraints.

若 $a\preceq b$，则在线性序中 $a$ 必须出现在 $b$ 之前或相同位置对应的元素本身。

6.16 定理 / Theorem#

Theorem / 定理

每个有限偏序都可以扩展成一个全序。等价地，每个有限 DAG 都有拓扑排序。

Every finite partial order can be extended to a total order. Equivalently, every finite DAG has a topological ordering.

Proof / 证明

对有限 DAG 证明。若图非空，则一定存在入度为 $0$ 的顶点；否则从任意顶点不断沿入边往前走，因为顶点有限，最终会重复顶点，从而形成有向环，矛盾。

取一个入度为 $0$ 的顶点作为排序第一个元素，删除它和从它出发的边。剩余图仍是 DAG，对剩余图归纳即可。

6.17 算法模板 / Algorithm Template#

1. 计算每个顶点的入度。
2. 选一个入度为 $0$ 的顶点输出。
3. 删除该顶点及其出边。
4. 更新入度，重复直到所有顶点输出。
5. 若过程中没有入度为 $0$ 的顶点但仍有顶点未输出，则存在环，不是 DAG。

Use / 怎么用

课程先修、任务调度、编译依赖、项目构建顺序都可以抽象成拓扑排序。

7. 常见证明模板 / Common Proof Templates#

7.1 证明等价关系 / Proving an Equivalence Relation#

要证明 $R$ 是等价关系：

Reflexive / 自反

任取 $a\in A$，证明 $aRa$。

Symmetric / 对称

任取 $a,b\in A$，假设 $aRb$，证明 $bRa$。

Transitive / 传递

任取 $a,b,c\in A$，假设 $aRb$ 且 $bRc$，证明 $aRc$。

Then / 然后

若题目继续问等价类，就找 $[a]$ 的描述；若问划分，就列出所有不同等价类。

7.2 证明不是等价关系 / Proving Not an Equivalence Relation#

只需找一个性质失败。

To show a relation is not an equivalence relation, one failed property is enough.

常见反例格式：

• 不自反：找 $a\in A$ 使 $(a,a)\notin R$。
• 不对称：找 $a,b$ 使 $aRb$ 但 $\neg bRa$。
• 不传递：找 $a,b,c$ 使 $aRb$ 且 $bRc$，但 $\neg aRc$。

7.3 证明偏序 / Proving a Partial Order#

要证明 $R$ 是偏序：

1. 证明自反。
2. 证明反对称。
3. 证明传递。

最容易漏的是反对称。反对称必须从 $aRb$ 和 $bRa$ 推出 $a=b$，不能只说“看起来没有对称边”。

The most commonly missed part is antisymmetry. You must prove that $aRb$ and $bRa$ force $a=b$.

7.4 证明不是偏序 / Proving Not a Partial Order#

只需找一个性质失败：

• 不自反：缺少某个 $(a,a)$。
• 不反对称：存在 $a\ne b$ 且 $aRb,bRa$。
• 不传递：存在 $aRb,bRc$ 但没有 $aRc$。

7.5 求闭包 / Finding Closures#

Reflexive closure / 自反闭包

加缺少的所有 $(a,a)$。

Symmetric closure / 对称闭包

对每个 $(a,b)$ 加 $(b,a)$。

Transitive closure / 传递闭包

可以用三种方法：

1. 路径法：图中所有可达对。
2. 幂法：$R^+=R\cup R^2\cup\cdots\cup R^N$。
3. Warshall：矩阵动态更新。

7.6 找 Hasse 图 / Drawing a Hasse Diagram#

1. 先确认是偏序。
2. 列出所有比较关系。
3. 去掉自反边。
4. 去掉传递边。
5. 小的在下，大的在上。
6. 只保留覆盖边。

8. 易错点 / Common Pitfalls#

8.1 反对称不是不对称 / Antisymmetric Is Not Asymmetric#

反对称允许自环；非对称不允许自环。

Antisymmetric relations may have loops; asymmetric relations cannot have loops.

例如 $\le$ 是反对称的，但不是非对称的，因为 $a\le a$。

8.2 对称和反对称可以同时成立 / Symmetric and Antisymmetric Can Both Hold#

相等关系 $=$ 同时对称和反对称。

Equality is both symmetric and antisymmetric.

原因是：若 $a=b$，则反向当然成立；若 $aRb$ 且 $bRa$，也只能说明 $a=b$。

8.3 空关系的性质 / Properties of the Empty Relation#

在非空集合 $A$ 上，空关系 $\varnothing$：

• 不是自反 / not reflexive.
• 是反自反 / irreflexive.
• 是对称 / symmetric.
• 是反对称 / antisymmetric.
• 是传递 / transitive.

后面三个成立是因为没有反例，属于 vacuous truth / 空真。

8.4 传递性要检查所有两步链 / Transitivity Requires All Two-Step Chains#

只检查一个链不够。只要存在一个：

就不传递。

8.5 最大元和极大元不要混 / Do Not Confuse Maximum and Maximal#

最大元要和所有元素比较；极大元只要求没有比它更大的元素。

A maximum must dominate every element. A maximal element merely has no larger comparable element.

8.6 闭包不是随便补边 / Closure Is Not Arbitrary Edge Adding#

闭包要满足两个条件：

1. 包含原关系。
2. 在满足目标性质的关系中最小。

如果多加了不必要的边，就不是闭包。

9. 综合例题 / Mixed Examples#

9.1 判断关系性质 / Checking Relation Properties#

设：

Question / 问题

判断 $R$ 是否为等价关系或偏序。

Solution / 解法

自反：所有 $(a,a)$ 都在 $R$ 中，所以自反。

对称：$(1,2)$ 与 $(2,1)$ 同时存在，$(3,4)$ 与 $(4,3)$ 同时存在，所以对称。

传递：关系把 $A$ 分成 $\{1,2\}$ 和 $\{3,4\}$ 两组，组内所有元素互相关联，包括自环，因此传递。

所以 $R$ 是等价关系。

但它不是偏序，因为 $(1,2)$ 和 $(2,1)$ 都存在，而 $1\ne2$，违反反对称。

等价类为：

9.2 求传递闭包 / Finding a Transitive Closure#

设：

Solution / 解法

路径可达对包括：

长度 $1$：

长度 $2$：

长度 $3$：

所以：

9.3 偏序中的上下界 / Bounds in a Poset#

在正整数整除偏序中，考虑：

Upper bounds / 上界

上界是同时被 $6$ 和 $10$ 整除的正整数，即 $30$ 的倍数：

最小上界为：

Lower bounds / 下界

下界是同时整除 $6$ 和 $10$ 的正整数：

最大下界为：

10. 公式索引 / Formula Index#

10.1 关系数量 / Number of Relations#

若 $|A|=m, |B|=n$：

若 $|A|=n$：

10.2 特殊关系计数 / Counting Special Relations#

若 $|A|=n$：

10.3 闭包 / Closures#

10.4 Warshall 更新式 / Warshall Update#

10.5 关系类型 / Relation Types#

11. 中英术语表 / Bilingual Glossary#