映射

本章主线：关系中的唯一对应 → 映射 → 单射、满射与双射 → 复合与逆映射 → 算法中的状态映射。

1 从关系到映射

设 $A,B$ 是两个集合，关系 $R\subseteq A\times B$ 可以把 $A$ 中的元素与 $B$ 中的元素联系起来。

一般的关系没有限制：

• 一个元素可以不与任何元素相关；
• 一个元素可以与多个元素相关。

例如，设 $A=\{1,2,3\}$，$B=\{a,b,c\}$，关系

$$R=\{(1,a),(1,b),(3,c)\}$$

允许元素 $1$ 同时对应 $a,b$，而元素 $2$ 没有对应对象。

映射是一种限制更严格的关系。

---

2 映射的定义

设 $f\subseteq A\times B$。

若对每个 $x\in A$，都存在唯一的 $y\in B$，使得 $(x,y)\in f$，则称 $f$ 是从 $A$ 到 $B$ 的映射，记作

$$f:A\to B.$$

若 $(x,y)\in f$，通常写成 $f(x)=y$。

映射的定义包含两个要求：

1. 每个 $x\in A$ 都必须有对应值；
2. 每个 $x\in A$ 只能有一个对应值。

因此，映射可以概括为：

定义域中的每个元素，恰好对应陪域中的一个元素。

---

3 什么不是映射

设 $A=\{1,2,3\}$，$B=\{a,b,c\}$。

情形一：有元素没有对应值

$$R=\{(1,a),(2,b)\}.$$

元素 $3$ 没有对应值，因此 $R$ 不是从 $A$ 到 $B$ 的映射。

情形二：一个元素有多个对应值

$$R=\{(1,a),(1,b),(2,b),(3,c)\}.$$

元素 $1$ 同时对应 $a,b$，因此 $R$ 不是映射。

情形三：多个元素对应同一个值

$$f=\{(1,a),(2,a),(3,b)\}.$$

这仍然是映射。

映射只要求每个输入有唯一输出，并不要求不同输入得到不同输出。

---

4 定义域、陪域和值域

在映射 $f:A\to B$ 中：

• $A$ 称为定义域；
• $B$ 称为陪域；
• 所有实际输出组成的集合称为值域。

值域记作

$$f(A)=\{f(x)\mid x\in A\}.$$

值域总是陪域的子集：

$$f(A)\subseteq B.$$

例如，设 $f:\{1,2,3\}\to\{a,b,c,d\}$，并定义 $f(1)=a$，$f(2)=a$，$f(3)=c$。

则定义域为 $\{1,2,3\}$，陪域为 $\{a,b,c,d\}$，值域为 $\{a,c\}$。

陪域中可以存在没有被映射到的元素。

---

5 映射的三种表示方法

5.1 有序对集合

$$f=\{(1,a),(2,b),(3,b)\}.$$

5.2 对应规则

$$f(x)=x^2.$$

5.3 箭头图

将定义域与陪域分别画出，并用箭头表示每个元素的对应结果。

判断箭头图是否表示映射时，只需检查定义域中的每个元素是否恰好发出一条箭头。

---

6 映射必须是良定义的

一个映射规则必须保证：对于定义域中的每个元素，输出都存在且唯一。

例如，定义 $f:\mathbb R\to\mathbb R$，并令 $f(x)=1/x$。

当 $x=0$ 时，$1/x$ 没有定义，因此这不是从 $\mathbb R$ 到 $\mathbb R$ 的映射。

若改为

$$f:\mathbb R\setminus\{0\}\to\mathbb R,\qquad f(x)=\frac1x,$$

则映射有定义。

再如，定义 $f:\mathbb R\to\mathbb R$，令 $f(x)$ 为满足 $y^2=x$ 的实数 $y$。

当 $x<0$ 时不存在实数解；当 $x>0$ 时通常有两个实数解。因此该规则既不能保证存在，也不能保证唯一。

定义映射时，需要同时明确：

• 定义域；
• 陪域；
• 对应规则。

---

7 像与原像

7.1 元素的像

若 $f(x)=y$，则称 $y$ 是 $x$ 在映射 $f$ 下的像。

例如，若 $f(x)=x^2$，则 $3$ 的像为 $f(3)=9$。

---

7.2 子集的像

设 $S\subseteq A$，定义 $S$ 在 $f$ 下的像为

$$f(S)=\{f(x)\mid x\in S\}.$$

例如，设 $f(x)=x^2$，$S=\{-2,-1,0,1,2\}$，则

$$f(S)=\{0,1,4\}.$$

集合中重复得到的值只记录一次。

---

7.3 子集的原像

设 $T\subseteq B$，定义 $T$ 在 $f$ 下的原像为

$$f^{-1}(T)=\{x\in A\mid f(x)\in T\}.$$

例如，设 $f(x)=x^2$，定义域为整数集合，且 $T=\{1,4\}$，则

$$f^{-1}(T)=\{-2,-1,1,2\}.$$

这里的 $f^{-1}(T)$ 表示集合的原像，并不要求 $f$ 存在逆映射。

---

8 单射

8.1 定义

若不同输入一定得到不同输出，则称 $f:A\to B$ 为单射。

形式化地，

$$f(x_1)=f(x_2)\Longrightarrow x_1=x_2.$$

其逆否形式为

$$x_1\ne x_2\Longrightarrow f(x_1)\ne f(x_2).$$

单射也称一一映射。

---

8.2 判断单射

设 $f:\mathbb Z\to\mathbb Z$，$f(x)=2x+1$。

若 $f(x_1)=f(x_2)$，则 $2x_1+1=2x_2+1$，从而 $x_1=x_2$。

因此，该映射是单射。

设 $f:\mathbb Z\to\mathbb Z$，$f(x)=x^2$。

因为 $f(1)=f(-1)=1$，但 $1\ne-1$，所以该映射不是单射。

---

8.3 单射与信息损失

单射不会把两个不同输入压缩成同一个输出，因此可以从输出唯一确定原输入。

在算法中，离散化通常希望保留不同值之间的区别，因此使用的排名映射应当是单射。

---

9 满射

9.1 定义

若陪域中的每个元素都能被某个定义域元素映射到，则称 $f:A\to B$ 为满射。

形式化地，

$$\forall y\in B,\quad \exists x\in A,\ f(x)=y.$$

等价地，

$$f(A)=B.$$

---

9.2 判断满射

设 $f:\mathbb R\to\mathbb R$，$f(x)=x^3$。

对任意 $y\in\mathbb R$，取 $x=\sqrt[3]{y}$，则 $f(x)=y$。

因此，该映射是满射。

设 $f:\mathbb R\to\mathbb R$，$f(x)=x^2$。

负数不可能成为输出，因此该映射不是满射。

但若将陪域改为 $[0,+\infty)$，则 $f:\mathbb R\to[0,+\infty)$ 是满射。

因此，满射性依赖于陪域。

---

10 双射

若映射同时是单射和满射，则称其为双射。

双射满足：

• 每个定义域元素对应唯一的陪域元素；
• 每个陪域元素恰好对应一个定义域元素。

双射建立了两个集合之间的一一对应。

对于有限集合，若存在双射 $f:A\to B$，则 $|A|=|B|$。

反过来，若有限集合 $A,B$ 满足 $|A|=|B|$，则可以在它们之间建立双射。

---

11 逆映射

若 $f:A\to B$ 是双射，则对每个 $y\in B$，存在唯一的 $x\in A$ 使得 $f(x)=y$。

因此可以定义映射 $f^{-1}:B\to A$：

$$f^{-1}(y)=x\Longleftrightarrow f(x)=y.$$

该映射称为 $f$ 的逆映射。

逆映射满足

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

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

只有双射才能在整个陪域上定义逆映射。

---

12 恒等映射

集合 $A$ 上的恒等映射记作 $\operatorname{id}_A:A\to A$，定义为

$$\operatorname{id}_A(x)=x.$$

恒等映射不改变任何元素。

它既是单射，也是满射，因此是双射。

恒等映射在映射复合中的作用类似于数值运算中的单位元。

---

13 映射的复合

设有映射 $f:A\to B$ 与 $g:B\to C$。

先对 $x\in A$ 应用 $f$，再对结果应用 $g$，得到复合映射 $g\circ f:A\to C$：

$$(g\circ f)(x)=g(f(x)).$$

复合顺序从右向左读取。

例如，设 $f(x)=x+1$，$g(x)=x^2$，则

$$(g\circ f)(x)=(x+1)^2,$$

而

$$(f\circ g)(x)=x^2+1.$$

通常 $g\circ f\ne f\circ g$。

---

14 复合映射的结合律

设 $f:A\to B$，$g:B\to C$，$h:C\to D$。

对任意 $x\in A$，

$$\begin{aligned} ((h\circ g)\circ f)(x) &=(h\circ g)(f(x))\\ &=h(g(f(x)))\\ &=h((g\circ f)(x))\\ &=(h\circ(g\circ f))(x). \end{aligned}$$

因此，

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

映射复合满足结合律，但通常不满足交换律。

---

15 单射、满射在复合下的性质

设 $f:A\to B$，$g:B\to C$。

若 $f,g$ 都是单射，则 $g\circ f$ 是单射。

若 $f,g$ 都是满射，则 $g\circ f$ 是满射。

若 $f,g$ 都是双射，则 $g\circ f$ 是双射，并且

$$(g\circ f)^{-1}=f^{-1}\circ g^{-1}.$$

逆映射的复合顺序与原映射相反。

---

16 映射与算法

16.1 坐标压缩

设原始值集合为

$$S=\{100,500,1000\}.$$

将其按大小映射为

$$100\mapsto1,\qquad500\mapsto2,\qquad1000\mapsto3.$$

这建立了从原值到排名的单射，并保留大小顺序：

$$x<y\Longrightarrow f(x)<f(y).$$

坐标压缩的核心不是改变数值，而是在保留必要关系的前提下更换表示。

---

16.2 哈希

哈希函数通常把较大的对象集合映射到有限范围：

$$h:U\to\{0,1,\dots,m-1\}.$$

当 $|U|>m$ 时，哈希函数不可能是单射，必然存在不同对象映射到同一位置，这称为哈希冲突。

---

16.3 状态转移

状态转移可以看作映射：

$$T:S\to S.$$

它把当前状态映射到下一状态。

若转移由动作决定，也可以写成

$$T:S\times A\to S,$$

其中 $S$ 是状态集合，$A$ 是动作集合。

---

16.4 父亲数组

并查集中的父亲指针定义了一个映射：

$$\operatorname{fa}:V\to V.$$

反复应用该映射：

$$x,\operatorname{fa}(x),\operatorname{fa}^2(x),\dots$$

最终到达满足 $\operatorname{fa}(r)=r$ 的根节点。

find 可以理解为不断复合父亲映射，直到到达不动点。

---

16.5 函数图

对于有限集合上的映射 $f:A\to A$，从每个顶点 $x$ 向 $f(x)$ 连一条有向边。

由于每个顶点恰好有一个出边，所得图称为函数图。

函数图中的每个弱连通分量都由一个有向环和若干指向环的有向树组成。

---

17 映射与关系的区别

一般关系允许一个输入：

• 没有输出；
• 有一个输出；
• 有多个输出。

映射要求每个输入恰好有一个输出。

因此，映射是二元关系的一种特殊形式。

$$\boxed{\text{映射}=\text{满足存在性与唯一性的二元关系}}$$

---

19 与后续内容的联系

• 映射建立在 关系 之上；
• 有限集合到自身的映射产生函数图，双射则进一步形成置换；
• 映射复合满足结合律，所有自映射在复合下构成幺半群，参见 代数运算结构；
• 线性代数中的线性映射，是映射概念在向量空间上的进一步发展。

---

20 本章思考题

1. 判断下列关系是否为从 $A=\{1,2,3\}$ 到 $B=\{a,b,c\}$ 的映射：

   $$R_1=\{(1,a),(2,b),(3,c)\},$$

   $$R_2=\{(1,a),(1,b),(2,c),(3,a)\},$$

   $$R_3=\{(1,a),(2,b)\}.$$

2. 设 $f:\mathbb Z\to\mathbb Z$，$f(x)=3x-2$。判断它是否为单射、满射和双射。

3. 设 $f:\mathbb R\to\mathbb R$，$f(x)=x^2$。判断它是否为单射和满射。

4. 将上题的定义域改为 $[0,+\infty)$，陪域改为 $[0,+\infty)$，重新判断。

5. 设 $f(x)=2x+1$，$g(x)=x^2$，分别计算 $(g\circ f)(x)$ 与 $(f\circ g)(x)$。

6. 证明单射的复合仍为单射。

7. 证明满射的复合仍为满射。

8. 说明为什么只有双射才能定义整个陪域上的逆映射。

9. 设 $A=\{1,2,3,4\}$，映射 $f:A\to A$ 满足 $f(1)=2$，$f(2)=3$，$f(3)=2$，$f(4)=3$。画出对应的函数图，并找出其中的环。

10. 解释坐标压缩为什么通常要求保序。

11. 若集合 $U$ 有 $1000$ 个元素，而哈希值范围只有 $100$ 个位置，说明为什么一定发生冲突。

12. 思考快速幂为何可以理解为映射或运算的重复复合。