离散数学 1 第 9 章：函数——单射、满射、双射与集合基数

函数是这门课的收口。它在第 5 章已经埋了伏笔——函数就是一种特殊的关系，只不过每个 x 只能配一个 y；到了本章，前面所有工具（关系的复合、逆、等价类、偏序）都回过头来为它服务。这一章真正要建立的判断力是：给定一个映射，能立刻说出它是否单射、是否满射、能不能取反函数，以及有限集与无限集在"同样多"这件事上为什么表现完全不同。

一、函数的定义

设 f 是从 A 到 B 的二元关系，若满足

1. 处处有定义：dom f = A，即每个 x∈A 都有对应的 y；
2. 单值性：若 ∈f 且 ∈f，则 y = z；

则称 f 为从 A 到 B 的函数，记 f: A→B，y = f(x)。

两条要求各自的作用很实在：单值性排除了"一对多"，处处有定义排除了"开天窗"。用这两个条件去筛，很多式子立刻现形：

• f: ℝ→ℝ，f(x) = x² 是函数。
• x² + y² = 1 不是从 ℝ 到 ℝ 的函数：x=0 时 y 有两个取值 ±1，违反单值性。
• f: ℝ→ℝ，f(x) = 1/x 不是 ℝ 上的函数：x=0 无定义，dom f ≠ ℝ。但它可以是 ℝ{0}→ℝ 的函数。

这也解释了函数与一般关系的唯一区别：关系允许一个 x 对应多个 y，函数不允许；关系可以只定义在部分元素上，函数必须覆盖整个 A。 因此"函数的逆"未必是函数，而"关系的逆"永远存在——这是本章最容易混的一句话。

两个平凡函数要认识：恒等函数 I_A(x) = x，与常函数 f(x) = b（所有 x 都映到同一个 b）。当 |B| > 1 时，常函数既不单射也不满射，是反例库里的常客。

二、单射、满射与双射

名称	定义	否定形式（怎么举反例）
单射	f(x₁) = f(x₂) ⇒ x₁ = x₂	找两个不同的 x 有相同函数值
满射	∀y∈B，∃x∈A，f(x) = y，即 ran f = B	找一个 y∈B 不在值域里
双射	既单射又满射	任一条件不成立即不是

例（都取 f: ℝ→ℝ）：

• f(x) = 2x + 1：双射。
• f(x) = x²：既不单射（f(1)=f(−1)）也不满射（负数没有原像）。
• f(x) = eˣ：单射但不满射（值域是 (0,+∞)）。
• f(x) = x³ − x：满射但不单射。

有限集与无限集在这里分道扬镳：若 |A| = |B| = n 有限，则单射、满射、双射三者等价（鸽巢原理：n 个球放进 n 个盒子，不重复就必然不空）；若 A、B 无限，这个等价关系立刻失效。f: ℕ→ℕ，f(n) = 2n 是单射但不满射，而 ℕ 与偶数集明明"一样多"——这正是基数的入口。

计数结论也一并列清，设 |A| = m、|B| = n：

计数对象	个数	前提
全部函数	n^m	无
单射	n(n−1)…(n−m+1) = n!/(n−m)!	n ≥ m
双射	n!	m = n
满射	Σ_{k=0}^{n} (−1)^k C(n,k)(n−k)^m	n ≤ m

选择题里先比 m 与 n 的大小，能立刻排掉一半选项：n < m 时不可能有单射，m < n 时不可能有满射。

三、函数的复合

设 f: A→B，g: B→C，则复合函数

(g∘f)(x) = g(f(x))，g∘f: A→C

顺序是先 f 后 g，从右往左读，与第 7 章关系的复合约定一致。结合律成立：(h∘g)∘f = h∘(g∘f)；交换律一般不成立，甚至连 g∘f 与 f∘g 都未必同时有定义。

复合保性质，且方向是单向的：

• f、g 都是单射 ⇒ g∘f 是单射。
• f、g 都是满射 ⇒ g∘f 是满射。
• f、g 都是双射 ⇒ g∘f 是双射。

反向不成立，值得记住两个反例：g∘f 是单射只能推出 f 单射（g 可能把 B 的其他元素也压到同一处）；g∘f 是满射只能推出 g 满射（f 的像可能没覆盖 B，但 g 能从 B 的其他部分取到值）。

四、反函数存在的条件

f: A→B 的反函数 f⁻¹: B→A 存在，当且仅当 f 是双射。

理由分两半：满射保证 B 中每个 y 都有原像（f⁻¹ 处处有定义），单射保证原像唯一（f⁻¹ 单值）。缺一条，f⁻¹ 就退化成关系而不是函数。

双射时 f⁻¹ 满足 f⁻¹(y) = x ⇔ f(x) = y，并且

• (f⁻¹)⁻¹ = f
• (g∘f)⁻¹ = f⁻¹∘g⁻¹（顺序反转）
• f⁻¹∘f = I_A，f∘f⁻¹ = I_B

把 f⁻¹ 看成关系，它总是 f 的逆关系；能不能当函数用，取决于 f 是否双射。"逆关系存在"与"反函数存在"是两件事，这是判分点。

五、特征函数

设 A⊆U，A 的特征函数 χ_A: U→{0,1} 定义为

χ_A(x) = 1（x∈A）；χ_A(x) = 0（x∉A）

它的价值在于把集合运算翻译成算术运算：

集合运算	特征函数表达
交 A∩B	χ_A · χ_B
并 A∪B	χ_A + χ_B − χ_A·χ_B
补 ~A	1 − χ_A
差 A−B	χ_A · (1 − χ_B)
对称差 A⊕B	χ_A + χ_B − 2·χ_A·χ_B

于是"证明集合恒等式"多了一条路：两边都算特征函数，验证代数式相等即可。反过来也成立——两个集合相等，当且仅当它们的特征函数处处相等，这把集合等式问题完全转成了函数等式问题。工程上这就是位向量表示集合的原理：用一个二进制串表示子集，交并补变成按位与、按位或、按位取反，一次算 64 个元素。

六、集合基数简介

两个集合等势（基数相同），记 |A| = |B|，当且仅当存在 A 到 B 的双射。有限集的基数就是元素个数；无限集没有"个数"可数，只能靠双射来比较。

• 可数集：与 ℕ 等势的集合。|ℕ| = |ℤ| = |ℚ| = ℵ₀。有理数可数这件事反直觉——但可以用对角线方式把所有分数排成一列，逐一编号。
• 不可数集：ℝ 不可数，|ℝ| = ℵ（连续统）。Cantor 的对角线论证：假设 (0,1) 能排成一列，构造一个数，使它的第 n 位与第 n 个数的第 n 位不同，这个数就不在表中，矛盾。
• Cantor 定理：对任意集合 A，|P(A)| = 2^{|A|} > |A|。取幂集永远能造出更大的基数，所以不存在"最大的基数"。

一条常用结论：可数多个可数集的并仍可数（按对角线枚举），这正是"ℤ 可数、ℚ 可数"的统一证法。

易错点

1. f(x)=1/x 不是 ℝ 上的函数，因为 dom f ≠ ℝ；"处处有定义"是定义的硬条件。
2. 单射的反面不是"满射"，两者互不蕴含；四个组合都有例子。
3. 有限集上单射、满射、双射等价，无限集上不等价，别把鸽巢原理的结论乱推广。
4. 反函数存在要求双射；逆关系 R⁻¹ 则总是存在，两者不能混说。
5. (g∘f)⁻¹ = f⁻¹∘g⁻¹，顺序必须反转；复合本身也是先 f 后 g。

这一章在整门课里的位置

本章把第 5 章"关系是笛卡尔积的子集"推进到"函数是特殊的关系"，把第 7 章的逆关系与复合直接继承过来，把第 8 章的等价类思想用在"等势"上——基数就是一种把集合按"能否双射"分类的等价关系。至此数理逻辑与集合论的主线闭合：逻辑给语言，集合给对象，关系给结构，函数给映射。

本文是《离散数学 1：数理逻辑与集合论》第 9 章的知识点摘要。完整板书与例题见 课程页；上一章 偏序关系。下一步建议看 离散数学 2：图论。