二元关系与函数

本节导读

关系是集合与关系单元的另一半内容，大纲列了四条：关系的概念与表示，逆、合成、性质与闭包，等价关系与偏序关系，函数的定义与性质。上一节最后讲的「集合的势」，也要用这一节的双射来定义。

这一块的题目常常是「给一个具体的关系，判断它有哪些性质、求它的闭包、画哈斯图找特殊元素」，也有「证明某个关系是等价关系」「数一数有多少个单射」这类证明和计数题。学完你应该能对一个给定的关系逐条检查五种性质，熟练求三种闭包，并能在哈斯图上找出极大元、最大元和上确界。

二元关系及其表示

有序对 $\langle x, y \rangle$⟨x,y⟩ 的两个分量有先后之分。笛卡儿积 $A \times B$A×B 是所有 $\langle x, y \rangle$⟨x,y⟩（x 属于 A，y 属于 B）组成的集合，$\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert$∣A×B∣=∣A∣⋅∣B∣。$A \times B$A×B 的任何子集都叫从 A 到 B 的二元关系；A 到 A 的叫 A 上的关系。n 元集合上的关系对应 $A \times A$A×A 的子集，一共有 $2^{n^2}$2n2 个。三个特殊关系：空关系 $\varnothing$∅、全域关系 $E_A = A \times A$EA​=A×A、恒等关系 $I_A = \{\langle x, x \rangle \mid x \in A\}$IA​={⟨x,x⟩∣x∈A}。

有限集上的关系有两种表示法。关系矩阵：第 i 行第 j 列为 1 表示 $x_i$xi​ 与 $x_j$xj​ 有关系。关系图：每个元素画一个点，有关系就画一条从 $x_i$xi​ 指向 $x_j$xj​ 的有向边，$\langle x, x \rangle$⟨x,x⟩ 画成环。

逆与合成

R 的逆 $R^{-1} = \{\langle y, x \rangle \mid \langle x, y \rangle \in R\}$R−1={⟨y,x⟩∣⟨x,y⟩∈R}，关系矩阵是原矩阵的转置。本课把合成记作 $R \circ S = \{\langle x, z \rangle \mid \text{存在 } y \text{ 使 } \langle x, y \rangle \in R \text{ 且 } \langle y, z \rangle \in S\}$R∘S={⟨x,z⟩∣存在 y 使 ⟨x,y⟩∈R 且 ⟨y,z⟩∈S}，即「先 R 后 S」，它的矩阵是两个矩阵的布尔乘积 $M_R \cdot M_S$MR​⋅MS​。有的教材把记号的顺序反过来写，做题时以题目给出的定义为准。例如 $R = \{\langle 1, 2 \rangle, \langle 2, 2 \rangle, \langle 3, 4 \rangle\}$R={⟨1,2⟩,⟨2,2⟩,⟨3,4⟩}，$S = \{\langle 2, 4 \rangle, \langle 4, 1 \rangle\}$S={⟨2,4⟩,⟨4,1⟩}，则 $R \circ S = \{\langle 1, 4 \rangle, \langle 2, 4 \rangle, \langle 3, 1 \rangle\}$R∘S={⟨1,4⟩,⟨2,4⟩,⟨3,1⟩}。合成满足结合律，但一般不满足交换律；$(R \circ S)^{-1} = S^{-1} \circ R^{-1}$(R∘S)−1=S−1∘R−1。

关系的五种性质

性质	定义（对 A 中任意元素）	关系矩阵	关系图
自反	每个 x 都有 $\langle x, x \rangle \in R$⟨x,x⟩∈R	主对角线全是 1	每个点都有环
反自反	每个 x 都没有 $\langle x, x \rangle$⟨x,x⟩	主对角线全是 0	没有环
对称	有 $\langle x, y \rangle$⟨x,y⟩ 就有 $\langle y, x \rangle$⟨y,x⟩	对称矩阵	两点之间的边成对出现
反对称	有 $\langle x, y \rangle$⟨x,y⟩ 和 $\langle y, x \rangle$⟨y,x⟩ 就必有 x = y	对角线外对称位置不同时为 1	两个不同点之间至多一条边
传递	有 $\langle x, y \rangle$⟨x,y⟩、$\langle y, z \rangle$⟨y,z⟩ 就有 $\langle x, z \rangle$⟨x,z⟩	$M^2$M2 为 1 的位置 M 也为 1	有长为 2 的路就有直达的边

两个容易误会的地方：「不自反」不等于「反自反」，一个关系可以两者都不是；对称和反对称可以同时成立，比如恒等关系和空关系。

关系的闭包

在 R 上添加最少的有序对，使它具有某种性质，得到的关系叫闭包。三种闭包的公式（A 有 n 个元素）：

$r(R) = R \cup I_A, \qquad s(R) = R \cup R^{-1}, \qquad t(R) = R \cup R^2 \cup \cdots \cup R^n$r(R)=R∪IA​,s(R)=R∪R−1,t(R)=R∪R2∪⋯∪Rn

传递闭包可以理解为「有路就连边」：从 x 出发沿 R 的边走若干步能到 y，就把 $\langle x, y \rangle$⟨x,y⟩ 加进来。比如 $A = \{1, 2, 3\}$A={1,2,3} 上的 $R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle\}$R={⟨1,2⟩,⟨2,3⟩,⟨3,1⟩} 构成一个圈，每个点都能走到每个点（包括自己），所以 $t(R) = A \times A$t(R)=A×A，共 9 个有序对。手工求传递闭包时，n 较大可以用 Warshall 算法逐列更新关系矩阵。

等价关系与划分

自反、对称、传递的关系叫等价关系。与 x 等价的所有元素组成 x 的等价类 $[x]_R$[x]R​；所有等价类组成的集合叫商集 $A/R$A/R。商集就是 A 的一个划分（若干非空、两两不交、并起来等于 A 的子集）；反过来，每个划分也确定一个等价关系：同在一块的元素彼此等价。所以 A 上等价关系的个数等于 A 的划分个数。例如 $\{a, b, c\}${a,b,c} 的划分有 5 种：三个元素各成一块；a、b 同块 c 单独，或 a、c 同块，或 b、c 同块；三个都在一块。它上面就有 5 个等价关系。

整数上的「模 3 同余」是典型的等价关系，三个等价类是余数为 0、1、2 的整数。

偏序关系与哈斯图

自反、反对称、传递的关系叫偏序关系，记作 $\preccurlyeq$≼。若 $x \preccurlyeq y$x≼y 且 $x \neq y$x=y、中间没有别的元素，就说 y 覆盖 x。哈斯图只画覆盖关系：被覆盖的元素画在下面，不画环，不画箭头，也不画能由传递性推出的边。比如整除关系下的 $\{1, 2, 3, 6\}${1,2,3,6}：

      6
     / \
    2   3
     \ /
      1

在偏序集的子集 B 中找特殊元素：

元素	含义	是否唯一
最大元 / 最小元	B 中比所有元素都大 / 都小的元素	有则唯一
极大元 / 极小元	B 中没有比它更大 / 更小的元素	可能有多个
上界 / 下界	A 中比 B 的所有元素都大 / 都小的元素	可能有多个，也可能没有
上确界 / 下确界	最小的上界 / 最大的下界	有则唯一

任意两个元素都可比的偏序叫全序（线序）。

函数

从 A 到 B 的函数 f 是一种特殊关系：A 中每个元素恰好对应 B 中一个元素。A 有 m 个元素、B 有 n 个元素时，函数共有 $n^m$nm 个。三类重要函数：单射（不同元素的像不同）、满射（B 中每个元素都有原像）、双射（既单又满）。单射要求 $m \le n$m≤n，个数是 $n(n - 1) \cdots (n - m + 1)$n(n−1)⋯(n−m+1)；双射要求 $m = n$m=n，个数是 $n!$n!；满射的个数要用第 13 节的容斥原理来算。例如从 2 元集到 3 元集的单射有 $3 \times 2 = 6$3×2=6 个。

常见的特殊函数有常函数、恒等函数、集合的特征函数（属于集合取 1，否则取 0）、从 A 到商集 $A/R$A/R 的自然映射（把 x 映成 $[x]_R$[x]R​）。只有双射才有反函数。

易错提醒

• ❌ 「不是自反的」就是「反自反的」。✅ 两者不同，可能都不成立。因为只要对角线上有 1 也有 0，就既不自反也不反自反。

• ❌ 对称与反对称互相排斥。✅ 恒等关系、空关系既对称又反对称。因为它们没有两个不同元素之间的有序对。

• ❌ 传递闭包只加长度为 2 的路。✅ 要一直加到 $R^n$Rn，或者反复「有路就连」直到不再变化。因为长度为 3 的路可能在加一次之后才出现。

• ❌ 极大元一定是最大元。✅ 最大元要与 B 中所有元素都可比且最大，极大元只要求「没有更大的」。因为偏序里有些元素彼此不可比。

• ❌ 哈斯图里把传递推出的边也画上。✅ 只画覆盖关系。因为哈斯图的作用就是去掉可以推出的边，让结构一目了然。

例题精讲

例题 1（正误判断）

$A = \{1, 2, 3\}$A={1,2,3} 上的关系 $R = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 1, 2 \rangle, \langle 2, 3 \rangle\}$R={⟨1,1⟩,⟨2,2⟩,⟨3,3⟩,⟨1,2⟩,⟨2,3⟩}，判断它是否自反、对称、反对称、传递。

答案：自反（三个环都在）；不对称（有 $\langle 1, 2 \rangle$⟨1,2⟩ 没有 $\langle 2, 1 \rangle$⟨2,1⟩）；反对称（不同元素间没有成对的有序对）；不传递（有 $\langle 1, 2 \rangle$⟨1,2⟩、$\langle 2, 3 \rangle$⟨2,3⟩，却没有 $\langle 1, 3 \rangle$⟨1,3⟩）。

点评：说某性质不成立时，像括号里那样点出具体的有序对，就是最好的理由。

例题 2（填空）

整除关系下的偏序集 $B = \{2, 3, 6, 12, 24, 36\}$B={2,3,6,12,24,36}，求 B 的极小元、极大元、最大元，以及子集 $\{2, 3\}${2,3} 在 B 中的上确界。

答案：极小元 2 和 3；极大元 24 和 36；没有最大元（24 与 36 互不整除）；$\{2, 3\}${2,3} 的上界是 6、12、24、36，其中最小的是 6，所以上确界是 6。

例题 3（证明推导）

设 R 是 A 上自反且传递的关系，证明 $R \circ R = R$R∘R=R。

答题要点示范：先证 $R \circ R \subseteq R$R∘R⊆R：任取 $\langle x, z \rangle \in R \circ R$⟨x,z⟩∈R∘R，存在 y 使 $\langle x, y \rangle \in R$⟨x,y⟩∈R、$\langle y, z \rangle \in R$⟨y,z⟩∈R，由传递性得 $\langle x, z \rangle \in R$⟨x,z⟩∈R。再证 $R \subseteq R \circ R$R⊆R∘R：任取 $\langle x, y \rangle \in R$⟨x,y⟩∈R，由自反性 $\langle y, y \rangle \in R$⟨y,y⟩∈R，于是 $\langle x, y \rangle \in R \circ R$⟨x,y⟩∈R∘R。两边互相包含，所以相等。

点评：证明两个关系相等，标准写法就是「互相包含」，每个方向都从「任取一个有序对」开始。

本节小结

• n 元集合上的关系有 $2^{n^2}$2n2 个；关系矩阵与关系图是两种等价的表示。
• 合成按题目定义的顺序算，本课的 $R \circ S$R∘S 是先 R 后 S；逆关系的矩阵是转置。
• 五种性质对照矩阵和图逐条检查；闭包：自反加 $I_A$IA​，对称加逆，传递有路就连。
• 等价关系与划分一一对应；偏序关系用哈斯图表示，极大元可以有多个，最大元有则唯一。
• 函数计数：一共 $n^m$nm 个，单射 $n(n-1)\cdots(n-m+1)$n(n−1)⋯(n−m+1) 个，双射 $n!$n! 个。