关系与函数

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

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

二元关系

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

R \subseteq A \times B

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

关系本身只记录哪些有序对被选中。它不要求每个左边元素都出现，也不要求一个左边元素只能对应一个右边元素。函数会在后面加入这些额外限制。

二元关系是笛卡尔积子集的中文示意图 — 从有序对集合、网格和箭头图三个角度看同一个二元关系。

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

关系的几个基本问题是：

哪些元素和自己有关？
如果 $x$ 和 $y$ 有关， $y$ 是否也和 $x$ 有关？
如果 $x$ 到 $y$ 、 $y$ 到 $z$ 都成立， $x$ 到 $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$ - $1$ 矩阵：

(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$ 。若 $(x,x)\in R$ ，箭头就是从 $x$ 指回自己的自环。

关系矩阵和有向图表示同一个关系的中文示意图 — 矩阵中的一个 1 对应有向图中的一条箭头。

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

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

关系的四个基本性质

本节只讨论集合 $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$ 。注意，传递性只在前两条箭头都存在时提出要求。若其中一条不存在，就没有需要检查的三元组。

自反对称反对称传递四种关系性质的中文示意图 — 四个性质分别检查自环、反向箭头、双向箭头和两步路径。

判断关系性质时，不要只看一个漂亮的例子。定义里的量词通常是“对所有元素”。只要找到一个违反条件的元素组，性质就失败。

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

先判断自反性。任意整数 $x$ 都满足 $x \le x$ ，所以 $\le$ 在整数集合上是自反的。

再判断对称性。 $2 \le 5$ 成立，但 $5 \le 2$ 不成立，所以 $\le$ 不是对称的。

接着判断反对称性。若 $x \le y$ 且 $y \le x$ ，整数的大小关系迫使 $x=y$ ，所以 $\le$ 是反对称的。

最后判断传递性。若 $x \le y$ 且 $y \le z$ ，则 $x \le z$ ，所以 $\le$ 是传递的。

练习：在集合 $\{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{划分}

模三同余把整数分成三个等价类的中文示意图 — 模 3 同余把整数按余数分成三个等价类。

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

a \equiv b \pmod n

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

自反性来自 $a-a=0$ 。因为 $n$ 整除 $0$ ，所以 $a \equiv a \pmod n$ 。

对称性来自符号反向。若 $a \equiv b \pmod n$ ，则 $n\mid(a-b)$ ，所以 $n\mid(b-a)$ ，于是 $b \equiv a \pmod n$ 。

传递性来自差的相加。若 $a \equiv b \pmod n$ 且 $b \equiv c \pmod n$ ，则 $n\mid(a-b)$ 且 $n\mid(b-c)$ ，所以 $n\mid(a-c)$ 。

三个条件都成立，因此模 $n$ 同余是整数集合上的等价关系。

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

遇到“分类”“同余”“同构前的粗略相同”“拥有同一个不变量”这类问题时，可以先问：这里是否有一个等价关系？如果有，真正的对象常常不是单个元素，而是等价类。

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

偏序与 Hasse 图

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

常见偏序包括：

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

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

整除偏序和 Hasse 图的中文示意图 — Hasse 图只保留覆盖关系，并把“较大”的元素画在上方。

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

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

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

先列出所有整除关系。例如 $1$ 整除所有元素， $2$ 整除 $4,6,12$ ， $3$ 整除 $6,12$ ， $4$ 和 $6$ 都整除 $12$ 。

删去自环，例如 $1\mid 1$ 、 $2\mid 2$ 这些边不画。

再删去传递边。例如 $1\mid 4$ 可以由 $1\mid 2$ 和 $2\mid 4$ 推出，所以 Hasse 图不画 $1$ 到 $4$ 的边。

最后按层摆放元素。 $1$ 在底部， $2$ 和 $3$ 在其上， $4$ 和 $6$ 再往上， $12$ 在顶部。

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

“最小元”和“最小元素”不是同一个说法。最小元只要求没有元素严格在它下面；最小元素要求它能和所有元素比较，并且小于等于所有元素。

练习：在幂集 $\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:A\to B$ 不可能是满射，因为输出位置比输入多，至少有一个陪域元素没人命中。

满射必须相对于指定的陪域判断。同一个公式，若换了陪域，满射性可能改变。例如 $f:\mathbb R\to\mathbb R,\ f(x)=x^2$ 不是满射；若写成 $f:\mathbb R\to[0,\infty),\ f(x)=x^2$ ，它就是满射。

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

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

复合与反函数

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

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

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

复合满足结合律。若 $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$ 上的恒等函数，即 $\operatorname{id}_A(a)=a$ 。

若 $f$ 有反函数，先说明 $f$ 是单射。假设 $f(x)=f(y)$ ，两边同时作用 $f^{-1}$ ，得到 $f^{-1}(f(x))=f^{-1}(f(y))$ ，所以 $x=y$ 。

再说明 $f$ 是满射。任取 $b\in B$ ，令 $a=f^{-1}(b)$ 。由 $f(f^{-1}(b))=b$ 可知 $b$ 被 $a$ 命中。

因此，有反函数的函数必须是双射。反过来，若 $f$ 是双射，每个 $b\in B$ 恰好来自一个 $a\in A$ ，把这个唯一的 $a$ 定义为 $f^{-1}(b)$ ，就得到反函数。

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

处理函数题时，先确认“是不是函数”，再问“是否单射或满射”，最后再谈“是否有反函数”。这个顺序能避免把关系、函数和可逆函数混在一起。

综合练习

练习一：在集合 $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$ 是否单射、满射、双射。