关系与函数

集合给了我们谈论对象的语言。关系和函数进一步回答一个问题：对象之间怎样相连，怎样比较，怎样对应。

本章把“对应”拆成两层。第一层是关系，它允许一个元素连向零个、一个或多个元素。第二层是函数，它是更受约束的关系：每个输入必须有且只有一个输出。等价关系、偏序关系、单射、满射、双射都不是额外的名字游戏，而是在说这些连接满足哪些可检查的条件。

---

二元关系

设 $A$ 和 $B$ 是集合。一个从 $A$ 到 $B$ 的二元关系是笛卡尔积 $A \times B$ 的一个子集：

$$R \subseteq A \times B$$

如果 $(a,b) \in R$，常写作 $aRb$，读作“$a$ 与 $b$ 有关系 $R$”。这里的“关系”很宽。它可以表示“学生选了某门课”“整数 $a$ 整除整数 ”“网页 链向网页 ”，也可以表示“两个数模 同余”。

当 $A=B$ 时，我们说 $R$ 是集合 $A$ 上的关系。许多重要关系都属于这一类。例如，在整数集合上，$a \le b$ 是一个关系；在一个课程集合上，“课程 $x$ 是课程 $y$ 的先修课”也是一个关系。

关系的几个基本问题是：

• 哪些元素和自己有关？
• 如果 $x$ 和 $y$ 有关，$y$ 是否也和 $x$ 有关？
• 如果 $x$ 到 $y$、$y$ 到 $z$ 都成立， 到 是否也成立？

后面的定义都围绕这些问题展开。

---

关系矩阵和有向图

如果 $A$ 和 $B$ 都是有限集合，关系可以被写成矩阵。设

$$A=\{a_1,a_2,\ldots,a_m\}, \qquad B=\{b_1,b_2,\ldots,b_n\}$$

关系 $R \subseteq A \times B$ 的矩阵 $M_R$ 是一个 $m \times n$ 的 $0$- 矩阵：

$$(M_R)_{ij} = \begin{cases} 1, & (a_i,b_j)\in R,\\ 0, & (a_i,b_j)\notin R. \end{cases}$$

矩阵适合做计算。有向图适合看结构。若 $R$ 是 $A$ 上的关系，我们把 $A$ 的元素画成点；若 $(x,y)\in R$，就从 $x$ 画一条箭头到 $y$。若 ，箭头就是从 指回自己的自环。

这种双重表示很有用。矩阵让我们能逐格检查；有向图让我们一眼看到自环、双向箭头和路径。

下面的交互把这两种表示放在一起。点击矩阵中的格子，可以立刻看到有向图和性质判断怎样变化。

---

关系的四个基本性质

本节只讨论集合 $A$ 上的关系，也就是 $R \subseteq A \times A$。

自反

关系 $R$ 是自反的，意思是每个元素都和自己有关：

$$\forall x\in A,\ xRx$$

在有向图中，自反意味着每个点都有自环。在矩阵中，自反意味着主对角线上的元素全是 $1$。

对称

关系 $R$ 是对称的，意思是关系可以反向：

$$\forall x,y\in A,\ xRy \Rightarrow yRx$$

对称不是说所有点之间都互相连接，而是说只要出现一条 $x \to y$ 的箭头，就必须同时出现 $y \to x$。

反对称

关系 $R$ 是反对称的，意思是两个不同元素不能互相指向：

$$\forall x,y\in A,\ (xRy \land yRx) \Rightarrow x=y$$

这个定义容易被误读。反对称不是“不是对称”。例如等号 $=$ 在任何集合上既是对称的，也是反对称的：若 $x=y$ 且 $y=x$，那当然只能是同一个元素。

传递

关系 $R$ 是传递的，意思是两步可以合成一步：

$$\forall x,y,z\in A,\ (xRy \land yRz) \Rightarrow xRz$$

在有向图中，如果有 $x \to y$ 和 $y \to z$，传递性要求也有 $x \to z$。注意，传递性只在前两条箭头都存在时提出要求。若其中一条不存在，就没有需要检查的三元组。

下面用整数上的“小于等于”关系练一次。

练习：在集合 $\{1,2,3,4,6,12\}$ 上定义 $aRb$ 当且仅当 $a$ 整除 $b$。判断 $R$ 是否自反、对称、反对称、传递。

---

等价关系与划分

等价关系用来表达“属于同一类”。一个集合 $A$ 上的关系 $R$ 若同时满足自反、对称、传递，就叫作等价关系。

等价关系的三个条件各有作用：

• 自反保证每个元素至少和自己同类。
• 对称保证“同类”不依赖观察方向。
• 传递保证同类关系可以沿链条延伸。

设 $R$ 是 $A$ 上的等价关系。元素 $a$ 的等价类定义为

$$[a]=\{x\in A\mid xRa\}$$

等价类把集合 $A$ 分成若干块。每个元素落在某一块里；两块要么完全相同，要么没有交集。这种把集合拆成不重叠非空子集的方式叫作划分。

反过来，任何划分也能定义一个等价关系：若两个元素落在同一块中，就规定它们等价。于是有一个很重要的对应：

$$\text{等价关系} \quad \longleftrightarrow \quad \text{划分}$$

一个标准例子是模 $n$ 同余。在整数集合上定义

$$a \equiv b \pmod n$$

当且仅当 $n$ 整除 $a-b$。这个关系把所有整数按除以 $n$ 的余数分成 $n$ 个等价类。

下面的交互可以改变模数，观察等价类怎样随余数重新分组。

练习：在平面点集上定义 $(x_1,y_1)R(x_2,y_2)$ 当且仅当 。这个关系是不是等价关系？等价类是什么？

---

偏序与 Hasse 图

偏序关系用来表达“可比较的次序”，但它不要求任意两个元素都能比较。集合 $A$ 上的关系 $\preceq$ 若同时满足自反、反对称、传递，就叫作偏序关系。配备了偏序关系的集合写作 $(A,\preceq)$，叫作偏序集。

常见偏序包括：

• 数集上的 $\le$。
• 集合族上的 $\subseteq$。
• 正整数上的整除关系 $a\mid b$。
• 任务集合上的“必须先完成”关系。

偏序里有一个新现象：不可比。若既没有 $a\preceq b$，也没有 $b\preceq a$，就说 $a$ 和 $b$ 不可比。例如在整除偏序中，$4$ 和 $6$ 都整除 $12$，但 且 ，所以 与 不可比。

Hasse 图是有限偏序的简化画法。它遵守三条规则：

• 不画自环，因为自反性默认成立。
• 不画可由传递性推出的边。
• 边默认从下往上读，不再画箭头。

用整除关系在 $\{1,2,3,4,6,12\}$ 上构造 Hasse 图，可以这样做。

偏序中还要区分几类“端点”。最小元是没有比它更小的元素；最大元是没有比它更大的元素。最小元和最大元可以有多个。若某个元素小于等于所有元素，它叫最小元素；若某个元素大于等于所有元素，它叫最大元素。最小元素或最大元素若存在，必定唯一。

练习：在幂集 $\mathcal P(\{a,b\})$ 上用 $\subseteq$ 作偏序。写出所有元素，并判断是否有最小元素和最大元素。

---

函数是特殊关系

函数可以看成一种特殊的二元关系。设 $A$ 和 $B$ 是集合。函数 $f:A\to B$ 是 $A\times B$ 的子集，并且满足：

$$\forall a\in A,\ \exists! b\in B,\ f(a)=b$$

符号 $\exists!$ 表示“存在唯一”。这句话包含两个要求：

• 每个输入 $a$ 至少有一个输出。
• 每个输入 $a$ 至多有一个输出。

第一个要求排除“没有定义”的输入。第二个要求排除“同一个输入指向多个输出”的情况。输出集合 $B$ 叫作陪域。真正被命中的输出组成像集：

$$f(A)=\{f(a)\mid a\in A\}$$

像集一定是 $B$ 的子集，但不一定等于 $B$。

---

单射、满射与双射

设 $f:A\to B$ 是函数。

函数 $f$ 是单射，意思是不同输入不会撞到同一个输出：

$$\forall x,y\in A,\ f(x)=f(y)\Rightarrow x=y$$

等价地说，若 $x\ne y$，则 $f(x)\ne f(y)$。

函数 $f$ 是满射，意思是陪域 $B$ 中的每个元素都被命中：

$$\forall b\in B,\ \exists a\in A,\ f(a)=b$$

函数 $f$ 是双射，意思是它既是单射又是满射。双射建立的是一一对应。

有限集合上，元素个数能帮助我们快速排除不可能的情况。若 $|A|>|B|$，函数 $f:A\to B$ 不可能是单射，因为输入比输出多，必有两个输入落到同一个输出。若 $|A|<|B|$，函数 $$ 不可能是满射，因为输出位置比输入多，至少有一个陪域元素没人命中。

下面的交互把函数、单射、满射、双射、复合放在同一张工作台中。

练习：设 $f:\{1,2,3\}\to\{a,b,c,d\}$，且 $f(1)=a,\ f(2)=b,\ f(3)=b$。判断 是否为单射、满射、双射。

---

复合与反函数

若 $f:A\to B$，$g:B\to C$，就可以先用 $f$ 把 $A$ 中元素送到 $B$，再用 把结果送到 。这个新函数叫作 与 的复合，写作 ：

$$(g\circ f)(a)=g(f(a))$$

复合的顺序要从右向左读。$g\circ f$ 是“先 $f$ 后 $g$”。如果 $f:A\to B$，$g:C\to D$，但 的输出不在 的输入集合中， 就没有定义。

复合满足结合律。若 $f:A\to B$、$g:B\to C$、$h:C\to D$，则

$$h\circ(g\circ f)=(h\circ g)\circ f$$

两边对任意 $a\in A$ 的输出都是 $h(g(f(a)))$。

反函数更严格。函数 $f:A\to B$ 若存在函数 $f^{-1}:B\to A$，满足

$$f^{-1}\circ f=\operatorname{id}_A$$

且

$$f\circ f^{-1}=\operatorname{id}_B$$

就说 $f^{-1}$ 是 $f$ 的反函数。这里 $\operatorname{id}_A$ 是 $A$ 上的恒等函数，即 ${\mathrm{id}}_A(a)=$。

所以，函数可逆当且仅当它是双射。

---

综合练习

练习一：在集合 $A=\{1,2,3\}$ 上，关系

$$R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$$

是不是等价关系？如果是，写出所有等价类；如果不是，指出失败的性质。

练习二：在集合 $\{2,3,4,6,8,12,24\}$ 上用整除关系作偏序。哪些元素是最小元？是否有最小元素？

练习三：设 $f:\mathbb Z\to\mathbb Z$，$f(n)=n+5$。判断 $f$ 是否为双射，并写出反函数。

练习四：设 $g:\mathbb Z\to\mathbb Z$，$g(n)=n^2$。判断 $g$ 是否单射、满射、双射。