返回：0100 离散数学课程总目录 · 上一章：0102 关系、有序对、闭包、等价关系与序关系 · 下一章：0104 自然数的定义与性质

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第三章。Auto_Tutor 中整理到的资料包括：

资料 内容
3.1 函数 函数、偏函数、全函数、真偏函数、单射、满射、双射、象、原象、特殊函数、函数合成、反函数
集合论习题课 1-3 章 集合论前三章的综合复盘入口
003 习题与答案 习题 11、19、20，重点考察满射与单射、象与原象、反函数、复合函数性质

本章的核心目标：把第二章的“关系”收束成“函数”。函数本质上是单值的二元关系，后续自然数、基数、同构、图论中的映射思想都会反复用到。

2、颜色标注

颜色 含义
粉色 必背、必会证明、后续章节反复使用
蓝色 核心术语和定义
橙色 易错点、边界条件
绿色 理解提示和后续连接

3、章节主线

模块 本章要会什么 后续连接
函数定义 知道函数是单值二元关系，会用 f(x)=y、<x,y>∈f、xfy 互相转换 关系特例
偏函数与全函数 分清 dom f⊆A 和 dom f=A 程序中的部分定义、全定义
单射、满射、双射 会判定、会计数、会写反例 反函数、等势
象与原象 会求 f(A')、f^-1(B') 集合运算、连续性类比
特殊函数 常数函数、恒等函数、特征函数、单调函数、自然映射 商集、偏序、等价类
复合函数 掌握 f∘g 的定义和性质 代数结构、图映射
反函数与单边逆 双射才有反函数；左逆对应单射，右逆对应满射 等势、同构

4、函数的基本概念

4.1 函数是单值关系

函数，也叫映射，是单值的二元关系。也就是说，关系里同一个输入不能对应两个不同输出。

1
2
F 是函数
⇔ 对任意 x∈dom F，若 xFy 且 xFz，则 y=z

函数记号可以互换：

1
F(x)=y ⇔ <x,y>∈F ⇔ xFy

函数首先是关系，其次才是“公式”。 一个函数可以写成有序对集合；不是每个函数都必须有一个漂亮的解析式。

空函数 ∅ 也是函数，因为它没有违反“同一个输入只能对应一个输出”的条件。

4.2 偏函数、全函数、真偏函数

设 F 是函数。

类型 条件 说明
A 到 B 的偏函数 dom F⊆A ∧ ran F⊆B 输入可以只覆盖 A 的一部分
A 到 B 的全函数 dom F=A ∧ ran F⊆B A 中每个元素都必须有像
A 到 B 的真偏函数 dom F⊂A ∧ ran F⊆B 确实少定义了至少一个输入

若 A={a,b}，B={1,2}，则 P(A×B) 有 16 个关系，但偏函数只有下面 9 个：

1
2
3
∅
{<a,1>}, {<a,2>}, {<b,1>}, {<b,2>}
{<a,1>,<b,1>}, {<a,1>,<b,2>}, {<a,2>,<b,1>}, {<a,2>,<b,2>}

其中全函数是最后 4 个，真偏函数是前 5 个。

{<a,1>,<a,2>} 不是函数，因为同一个输入 a 同时对应 1 和 2。

4.3 全函数的个数

若 |A|=n，|B|=m，从 A 到 B 的全函数个数为：

1
|B^A| = m^n

特殊情况：

条件 结果
A=∅ 从 A 到 B 的全函数只有空函数 ∅
A≠∅ 且 B=∅ 从 A 到 B 的全函数不存在
A≠∅ 且 B≠∅ 每个 A 中元素都能独立选择 B 中一个像

5、单射、满射、双射

设 f:A→B 是全函数。

性质 定义 直觉
单射 f(x)=f(y)⇒x=y 不同输入不会撞到同一个输出
满射 ran f=B 目标集每个元素都被命中
双射 既单射又满射 一一对应

等价写法：

1
2
3
f 单射 ⇔ x≠y⇒f(x)≠f(y)
f 满射 ⇔ ∀b∈B，∃a∈A，使 f(a)=b
f 双射 ⇔ ∀b∈B，∃!a∈A，使 f(a)=b

单射看“会不会挤在一起”，满射看“有没有漏掉目标”。 双射就是既不挤也不漏。

5.1 有穷集上的计数

设 |A|=n，|B|=m。

情况 结论
n<m 无满射、无双射；单射个数为 m(m-1)...(m-n+1)
n>m 无单射、无双射；满射个数为 m!S(n,m)
n=m 双射个数为 n!

其中 S(n,m) 是第二类 Stirling 数，也可用容斥写满射个数：

1
满射个数 = Σ_{k=0}^m (-1)^k C(m,k)(m-k)^n

5.2 例 3.3：三个典型函数

设 A,B 是非空有穷集。

  1. 若 f:A→B，定义 g:A→A×B：
1
g(a)=<a,f(a)>

则 g 一定是单射。若 |B|=1，g 是双射；若 |B|>1，g 不是满射。

  1. 定义投影函数 f:A×B→A：
1
f(<a,b>)=a

则 f 一定是满射。若 |B|=1，f 是双射；若 |B|>1，f 不是单射。

  1. 定义交换函数 f:A×B→B×A：
1
f(<a,b>)=<b,a>

则 f 是单射、满射、双射。

6、象与原象

设 f:A→B，A'⊆A，B'⊆B。

概念 定义
A’ 的象 `f(A’)={y
B’ 的原象 `f^-1(B’)={x

基本结论：

1
2
f(A)=ran f
f^-1(B)=dom f=A

例：f:R→R，f(x)=x^2。

集合 象或原象
A1=[0,+∞) f(A1)=[0,+∞)
A2=[1,3) f(A2)=[1,9)
A3=R f(A3)=[0,+∞)
B1=(1,4) f^-1(B1)=(-2,-1)∪(1,2)
B2=[0,1] f^-1(B2)=[-1,1]
B3=R f^-1(B3)=R

原象符号 f^-1(B') 不要求 f 有反函数。 它只是表示一批输入的集合；只有写成点到点的 f^-1:B→A 时，才要求 f 是双射。

7、特殊函数

函数 定义 说明
常数函数 ∃b∈B，∀x∈A，f(x)=b 所有输入都映到同一个值
恒等函数 I_A:A→A，I_A(x)=x 什么都不改变
特征函数 χ_A:E→{0,1}，χ_A(x)=1⇔x∈A 把集合成员关系编码成 0/1
单调增函数 x≤_A y⇒f(x)≤_B f(y) 保序
单调减函数 x≤_A y⇒f(y)≤_B f(x) 反序
自然映射 f:A→A/R，f(x)=[x]_R 把元素映到它所在的等价类

若 ∅⊂A⊂E，特征函数 χ_A:E→{0,1} 是满射。

设 R 为 A 上的等价关系，自然映射：

1
2
f:A→A/R
f(x)=[x]_R

当 R=I_A 时，自然映射是单射；一般情况下，它会把同一个等价类中的元素压到同一个类上。

8、复合函数

设：

1
2
g:A→B
f:B→C

则复合函数 f∘g:A→C 定义为：

1
(f∘g)(x)=f(g(x))

f∘g 的顺序是先做 g，再做 f。这和第二章的关系合成顺序保持一致。

重要性质：

条件 结论
f,g 均为满射 f∘g 是满射
f,g 均为单射 f∘g 是单射
f,g 均为双射 f∘g 是双射
f∘g 为满射 f 是满射
f∘g 为单射 g 是单射
f∘g 为双射 g 是单射，f 是满射

恒等函数在复合中像“单位元”：

1
f = f∘I_A = I_B∘f

若 f:R→R、g:R→R 都按 ≤ 单调增，则 f∘g 也是单调增；若二者都单调减，则 f∘g 单调增。

9、反函数与单边逆

若 f:A→B 是双射，则：

1
f^-1:B→A

也是双射，称为 f 的反函数。

更一般地，设 f:A→B，g:B→A：

名称 条件 对应性质
左逆 g∘f=I_A f 是单射
右逆 f∘g=I_B f 是满射
左逆且右逆 左右逆都存在 f 是双射，且左右逆相等

定理 3.10：

1
2
3
4
设 f:A→B，且 A≠∅
(1) f 存在左逆 ⇔ f 是单射
(2) f 存在右逆 ⇔ f 是满射
(3) f 存在左逆、右逆 ⇔ f 是双射 ⇔ f 的左逆和右逆相等

另一个常用判定：

1
2
A^-1 为函数 ⇔ A 为单根的
R 为函数 ⇔ R^-1 为单根的

这里“单根”就是单射的关系版说法。

10、习题与答案

习题 11：满射诱导单射

题目：设 f:A→B，定义 g:B→P(A)：

1
g(b)={x|x∈A∧f(x)=b}

证明：当 f 为满射时，g 为单射。

证明：

1
2
3
4
5
6
7
任取 b1,b2∈B，且假设 g(b1)=g(b2)。
因为 f 是满射，所以存在 x∈A，使 f(x)=b1。
于是 x∈g(b1)。
又因为 g(b1)=g(b2)，所以 x∈g(b2)。
由 g 的定义，f(x)=b2。
因此 b1=f(x)=b2。
所以 g 是单射。

若 f 不是满射，g 不一定单射。例如 A={1,2,3}，B={a,b,c,d,e}，f(1)=f(2)=a，f(3)=b，则 g(c)=g(d)=g(e)=∅，所以 g 不是单射。

习题 19：象、原象与反函数

题目：设 f:N→N：

1
2
3
4
f(x)=
  x+1,  x=0,1,2,3
  0,    x=4
  x,    x≥5

设 g:N→N：

1
2
3
g(x)=
  x/2,  x 为偶数
  3,    x 为奇数

19.1 求 f(A1) 和 f^-1(B1)

设：

1
2
A1={0,1,2}
B1={0,1,5,6}

答案：

1
2
f(A1)={1,2,3}
f^-1(B1)={0,4,5,6}

解释：

1
2
f(0)=1, f(1)=2, f(2)=3
f(4)=0, f(0)=1, f(5)=5, f(6)=6

19.2 求 g(A2) 和 g^-1(B2)

设：

1
2
A2={x|x∈N∧x 为偶数}
B2={3}

答案：

1
2
3
g(A2)=N
g^-1(B2)={x|x 为奇数}∪{6}
       ={2k+1|k∈N}∪{6}

解释：偶数可以写成 2n，所以 g(2n)=n，覆盖整个 N；而所有奇数都被 g 映到 3，此外 g(6)=3。

19.3 f 与 g 都有反函数吗？

f 有反函数，因为 f 是双射。其反函数为：

1
2
3
4
f^-1(x)=
  4,    x=0
  x-1,  x=1,2,3,4
  x,    x≥5

g 没有反函数，因为 g 不是双射。比如：

1
2
3
g(1)=3
g(3)=3
g(6)=3

同一个值 3 有多个原象，所以 g 不是单射。

习题 20：由复合函数性质反推

题目：设 g:A→B，f:B→C。

20.1 若 f∘g 单射且 g 满射，证明 f 单射

证明：

1
2
3
4
5
任取 b1,b2∈B，且 f(b1)=f(b2)。
因为 g 是满射，所以存在 a1,a2∈A，使 g(a1)=b1，g(a2)=b2。
于是：
(f∘g)(a1)=f(g(a1))=f(b1)
(f∘g)(a2)=f(g(a2))=f(b2)

由 f(b1)=f(b2) 得：

1
(f∘g)(a1)=(f∘g)(a2)

因为 f∘g 是单射，所以 a1=a2。由函数定义：

1
b1=g(a1)=g(a2)=b2

所以 f 是单射。

20.2 若 f∘g 满射且 f 单射，证明 g 满射

证明：

1
2
3
4
任取 b∈B。
令 c=f(b)∈C。
因为 f∘g 是满射，所以存在 a∈A，使：
(f∘g)(a)=c

也就是：

1
f(g(a))=f(b)

因为 f 是单射，所以：

1
g(a)=b

因此任意 b∈B 都属于 ran g，所以 g 是满射。

这两问是复合函数证明题的标准套路：要证明 f 单射，就从 f(b1)=f(b2) 出发；要证明 g 满射，就任取目标元素 b∈B，再借 f∘g 的满射性把它拉回去。

11、复盘清单

  1. 函数是单值二元关系；f(x)=y 等价于 <x,y>∈f。
  2. 偏函数只要求 dom f⊆A，全函数要求 dom f=A。
  3. 单射不撞，满射不漏，双射既不撞也不漏。
  4. f^-1(B') 作为原象不要求反函数存在；f^-1:B→A 作为反函数要求 f 双射。
  5. f∘g 是先 g 后 f。
  6. 复合函数“正向保性质”：两个单射复合仍单射，两个满射复合仍满射。
  7. 复合函数“反向只保一边”：f∘g 单射推出 g 单射；f∘g 满射推出 f 满射。
  8. 左逆对应单射，右逆对应满射，左右逆同时存在对应双射。

12、下一步

第四章进入自然数的定义与性质。复习第三章时，优先把 函数 = 单值关系、单射/满射/双射、原象与反函数的区别、复合函数的顺序 四件事稳住。