数学 / 集合论 · 从 ∈ 到映射与量词 / 映射 f: A → B 与像、原像、复合、逆 待审核 8 / 11
映射 · 像 / 原像 · 复合 / 逆

映射 f:A→Bf: A \to B 与像、原像、复合、逆

设 AA、BB 为集合。映射（mapping）f:A→Bf: A \to B 是一个对应法则，它给 AA 的每一个元素指定 BB 中唯一一个元素 f(x)f(x)，其中 AA 叫定义域，BB 叫陪域。

这个定义里的两个限定词各挡住一种失败：「每一个」不许 AA 中有元素没有去处，「唯一一个」不许一个元素有两个去处。映射与函数是同一个概念，中学习惯把 AA、BB 取为数集时叫函数（见函数系列），此处不限定元素是什么。

要分清陪域 BB 与值域 f(A)={f(x)∣x∈A}f(A) = \{f(x) \mid x \in A\}：后者是 BB 的子集，可以真包含于 BB。f:R→R, f(x)=x2f: \mathbb{R} \to \mathbb{R},\ f(x) = x^2 的陪域是 R\mathbb{R} 而值域只是 [0,+∞)[0, +\infty)，两者不等；把陪域改写成 [0,+∞)[0, +\infty) 得到的是另一个映射，尽管对应法则一字未改。

1 · 像与原像

mapping · f(S)f(S) 像 · f−1(T)f^{-1}(T) 原像

定义 1.1（像与原像） 对 S⊆AS \subseteq A，SS 的像是 f(S)={f(x)∣x∈S}f(S) = \{f(x) \mid x \in S\}。对 T⊆BT \subseteq B，TT 的原像是 f−1(T)={x∈A∣f(x)∈T}f^{-1}(T) = \{x \in A \mid f(x) \in T\}。

两者都把子集送到子集，方向相反。像顺着箭头看落点，原像逆着箭头找来源。原像不要求 ff 可逆，f−1(T)f^{-1}(T) 对任何映射都有定义，且允许为空：TT 与值域不交时它就是空集。

由此定义三个性质。ff 是单射（injective），若不同的源有不同的落点，即 f(x1)=f(x2)⇒x1=x2f(x_1) = f(x_2) \Rightarrow x_1 = x_2。ff 是满射（surjective），若值域铺满陪域，即 f(A)=Bf(A) = B。既单又满叫双射（bijective），此时 AA 与 BB 的元素恰好一一配对，这正是比较基数所用的对应。

图 1-1 · 映射的箭头图，以及子集的像与原像。可改动箭头，观察像与原像随之变化，并读出单射与满射的判定。

2 · 保持性的不对称

preservation · 原像全保持 · 像不保交

把集合运算搬过去时，像与原像的表现并不对称。原像对并、交、补一律取等号；像只保并，交上一般只有包含。

定理 2.1 对任意 T1,T2⊆BT_1, T_2 \subseteq B，原像满足 f−1(T1∪T2)=f−1(T1)∪f−1(T2)f^{-1}(T_1 \cup T_2) = f^{-1}(T_1) \cup f^{-1}(T_2)、f−1(T1∩T2)=f−1(T1)∩f−1(T2)f^{-1}(T_1 \cap T_2) = f^{-1}(T_1) \cap f^{-1}(T_2) 与 f−1(Tc)=f−1(T)cf^{-1}(T^c) = f^{-1}(T)^c。对任意 S1,S2⊆AS_1, S_2 \subseteq A，像满足 f(S1∪S2)=f(S1)∪f(S2)f(S_1 \cup S_2) = f(S_1) \cup f(S_2)，但一般只有 f(S1∩S2)⊆f(S1)∩f(S2)f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)；等号对一切 S1S_1、S2S_2 成立当且仅当 ff 是单射。

证明 只证最后一句。ff 单射时，设 y∈f(S1)∩f(S2)y \in f(S_1) \cap f(S_2)，则有 x1∈S1x_1 \in S_1、x2∈S2x_2 \in S_2 使 f(x1)=f(x2)=yf(x_1) = f(x_2) = y；单射给出 x1=x2x_1 = x_2，这个公共元素落在 S1∩S2S_1 \cap S_2 里，故 y∈f(S1∩S2)y \in f(S_1 \cap S_2)。反之设等号恒成立而 ff 不单射，取 a≠ba \ne b 且 f(a)=f(b)f(a) = f(b)，令 S1={a}S_1 = \{a\}、S2={b}S_2 = \{b\}：左端 f(∅)=∅f(\emptyset) = \emptyset，右端 {f(a)}≠∅\{f(a)\} \ne \emptyset，矛盾。∎

失败的根源是「挤」。原像逆着箭头走，每个源的去处唯一，先运算再回溯与先各自回溯再运算给出同一批元素。像顺着箭头走，多个源可以落到同一点，于是 S1S_1 与 S2S_2 即便不交，它们的像仍可能相交，左端的 f(∅)f(\emptyset) 撑不满右端。单射恰好禁掉「挤」，等号随之恢复。

图 2-1 · 像与原像对并、交、补三种运算的保持性对照。可切换运算并把 ff 调成单射，观察像在交上何时失效、何时恢复等号。

3 · 复合映射 g∘fg \circ f

composition · A→B→CA \to B \to C

给 f:A→Bf: A \to B 与 g:B→Cg: B \to C，先用 ff 再用 gg 得到复合映射 g∘f:A→Cg \circ f: A \to C，(g∘f)(x)=g(f(x))(g \circ f)(x) = g(f(x))。记号的次序与作用的次序相反，写在左边的 gg 后作用。复合满足结合律，但一般不可交换。

单射与满射沿复合的传递是单向的：ff、gg 都单射则 g∘fg \circ f 单射，都满射则 g∘fg \circ f 满射。反向只能推出一半：g∘fg \circ f 单射只保证 ff 单射，g∘fg \circ f 满射只保证 gg 满射。

图 3-1 · 两个映射接成复合的过程。可改中间集合，观察箭头如何串接以及单射与满射的传递。

反向推不动的那一半可以穷举干净。取 ∣A∣=2|A| = 2、∣B∣=3|B| = 3、∣C∣=2|C| = 2，ff 有 99 个、gg 有 88 个，共 7272 对。其中 g∘fg \circ f 单射的有 2424 对，而这 2424 对里 gg 不单射的是全部 2424 对，比例是 100%100\%，因为 ∣B∣>∣C∣|B| > |C| 使 gg 根本不可能单射。对称地，g∘fg \circ f 满射的 2424 对里，ff 不满射的也是全部 2424 对。所以「g∘fg \circ f 单射 ⇒g\Rightarrow g 单射」不是偶尔失效，而是在这组尺寸下无一例成立。

4 · 逆映射 f−1f^{-1}

inverse · f−1f^{-1} 存在   ⟺  \iff ff 双射

把 ff 的箭头整体反向，得到 BB 到 AA 的一个对应。它能否成为映射，由定义里那两个限定词分别裁决：ff 不单射时某个落点反向后一对多，违反「唯一」；ff 不满射时某个 BB 中元素反向后无来源，违反「每一个」。

定理 4.1 反向对应是映射 f−1:B→Af^{-1}: B \to A 当且仅当 ff 是双射，且此时 f−1∘f=idAf^{-1} \circ f = \mathrm{id}_A、f∘f−1=idBf \circ f^{-1} = \mathrm{id}_B。

图 4-1 · 逆映射存在的充要条件。可把映射调成非单或非满，观察逆映射在哪一条上失效。

警示 · 记号 f−1f^{-1} 承担两个不同的意思，不要混用。定义 1.1 的 f−1(T)f^{-1}(T) 是原像，作用在子集上、返回子集，对任何映射都有定义。本节的 f−1f^{-1} 是逆映射，作用在元素上、返回元素，只在 ff 双射时存在。二者在双射情形下相容——此时 f−1({y})f^{-1}(\{y\}) 恰是单元素集 {f−1(y)}\{f^{-1}(y)\}——但非双射时只有前者有意义。

5 · 映射的计数

counting · nmn^m · 下降阶乘 · S(m,n)⋅n!S(m,n) \cdot n!

设 m=∣A∣m = |A|、n=∣B∣n = |B| 均有限。定义一个映射就是给 AA 的每个元素独立挑一个去处，故映射共 nmn^m 个。加上单射约束后去处不得重复，可选数逐个递减，得下降阶乘 n(n−1)⋯(n−m+1)n(n-1)\cdots(n-m+1)；m>nm > n 时它为 00，这就是鸽巢原理。满射数是 S(m,n)⋅n!S(m, n) \cdot n!，其中第二类 Stirling 数 S(m,n)S(m, n) 先把 mm 个源分成 nn 个非空组（见枚举划分），n!n! 再把这些组配到 BB 的具体元素上。双射只在 m=nm = n 时存在，恰 n!n! 个，是单射与满射两条曲线在 m=nm = n 处的交点。

图 5-1 · 映射总数与单射、满射各自的数目。可改两个集合的大小，对照三个公式与鸽巢原理生效的位置。

三条公式都用穷举核过。m=5m = 5、n=3n = 3 时全体映射 243243 个，单射 00 个（m>nm > n），满射穷举得 150150 个，与 S(5,3)⋅3!=25×6=150S(5, 3) \cdot 3! = 25 \times 6 = 150 相符；m=3m = 3、n=4n = 4 时全体 6464 个，单射穷举 2424 个与 4×3×24 \times 3 \times 2 相符，满射 00 个；m=2m = 2、n=5n = 5 时单射 2020 个与 5×45 \times 4 相符。

6 · 参考文献

  1. Function (mathematics). Wikipedia. 映射的定义、陪域与值域的区别。https://en.wikipedia.org/wiki/Function_(mathematics)
  2. Image (mathematics). Wikipedia. 像与原像的定义，及各自对集合运算的保持性。https://en.wikipedia.org/wiki/Image_(mathematics)
  3. Bijection, injection and surjection. Wikipedia. 三种性质的定义与沿复合的传递方向。https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection
  4. Twelvefold way. Wikipedia. 按单 / 满 / 双与可区分性分类的映射计数总表。https://en.wikipedia.org/wiki/Twelvefold_way