大家好，又见面了，我是你们的朋友全栈君。

本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解离散数学，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

• （国外经典教材）离散数学及其应用 第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen ，袁崇义译，机械工业出版社
• 离散数学 第二版，武波等编著，西安电子科技大学出版社，2006年
• 离散数学 第三版，方世昌等编著，西安电子科技大学出版社，2013年
• （经典参考书及其题解）离散数学/离散数学——理论•分析•题解，左孝凌、李为鉴、刘永才编著，上海科学技术文献出版社
• 离散数学习题集：数理逻辑与集合论分册，耿素云；图论分册，耿素云；抽象代数分册， 张立昂。北京大学出版社

2. 特殊函数类

2.1 单射、满射和双射及其性质

根据函数映射的特征，产生了三种特殊的函数类：单射、满射和双射。当然，不是单射也不是满射的函数也有很多。

定义2.1.1 设 $f$ 是从集合 $X$ 到 $Y$ 的函数（每个 $x_i$ 都只对应一个 $f(x_i)$ ）。
（1）任取 $x_1,x_2\in X$ ，如果 $x_1\ne x_2$ ，那么 $f(x_1)\ne f(x_2)$ ，则称 $f$ 是单射函数 injective function ，简称单射或内映射 into mapping 、入射等（即不同的 $x_i$ 对应的 $f(x_i)$ 不同）。
（2）任取 $y\in Y$ ，存在 $x\in X$ ，使得 $f(x)=y$ ，则称 $f$ 为满射函数 surjective function ，简称满射或上映射 onto mapping（即 $f(X)=Y$ ）。
（3）若 $f$ 既是单射又是满射，则称 $f$ 是双射函数 bijective function ，简称双射或一一对应的映射。

【例1】判断下列函数的类型。
（1）$s:\mathbb{N}\to \mathbb{N},s(x)=x+2$
（2）$f:\mathbb{N}\to \mathbb{N},f(x)=x\mathrm{m}\mathrm{o}\mathrm{d}10$
（3）$f:\mathbb{N}\to \mathbb{N},f(x)=\{\begin{array}{l}x-1\mathtt{i}\mathtt{f}\mathtt{i}\mathtt{s}\mathtt{o}\mathtt{d}\mathtt{d}(\mathtt{x})\\ x+1\mathtt{i}\mathtt{f}\mathtt{i}\mathtt{s}\mathtt{e}\mathtt{v}\mathtt{e}\mathtt{n}(\mathtt{x})\end{array}$
（4）$h:\mathbb{R}\to \mathbb{R},h(x)=x^3+2x^2$
（5）$a,b\in R$ 且 $a\ne b$ ，$g:[0,1]\to [a,b],g(x)=(b-a)x+a$
（6） f : N → ρ ( N ) , f ( x ) = { x } f: \N \to \rho(\N), f(x) = \{x\} f:N→ρ(N),f(x)={
x}
解：
（1）$s$ 是单射而非满射，因为 $0,1$ 没有原像。
（2）$f$ 既非单射也非满射。
（3）$f$ 是双射。
（4）$h$ 是满射而非单射。
（5）$g$ 是双射。
（6）$f$ 是单射而非满射。因为 $\rho (\mathbb{N})$ 中 $\mathbb{N}$ 上的每个元素在函数 $f$ 下都有一个唯一的像，但 $\rho (\mathbb{N})$ 中有些元素没有原像，例如 { 0 , 1 } \{0, 1\} {
0,1} 。【离散数学】集合论 第四章 函数与集合(6) 三歧性定理、两集合基数判等定理（基数的比较）、Cantor定理这篇文章的 Cantor 定理中证明了任意函数 $g:M\to \rho (M)$ 均不是满射。

【例2】$f:[0,1]\to [a,b],a<b,f(x)=(b-a)x+a$ ，证明 $f$ 为双射。
证明：
（1）对任意 $x_1,x_2\in [0,1],x_1\ne x_2$ ，易知 $f(x_1)=(b-a)x_1+a\ne (b-a)x_2+a=f(x_2)$ 。故 $f$ 是单射函数。
（2）显然，对任意 $y\in [a,b]$ ，均存在 $x=\frac{y-a}{b-a}\in [0,1]$ ，故 $f$ 是满射函数。
（3）由(1)、(2)可知，$f$ 是双射函数。

定理2.1.1 设 $X$ 和 $Y$ 是有限集合，$f$ 是从集合 $X$ 到 $Y$ 的函数。
（1）若 $f$ 是单射，则必有 $|X|\le |Y|$ 。
（2）若 $f$ 是满射，则必有 $|X|\ge |Y|$ 。
（3）若 $f$ 是双射，则必有 $|X|=|Y|$ 。
证明 ：
（1）因为 $f$ 是单射，所以 $|f(x)|=|X|$ 。又因为 $f(x)\subseteq Y$ ，所以有 $|f(x)|\le |Y|$ ，故有 $|X|\le |Y|$ 。
（2）假设 $|X|<|Y|$ ，因为 $|f(x)|\le |X|$（函数定义，对每个 $x\in X$ ，都有唯一的一个 $y\in Y$ 满足 $⟨x,y⟩\in f$ ），所以有 $|f(x)|<|Y|$，即 $f(X)\subset Y$ ，这与 $f$ 是满射矛盾。
（3）可由(1)和(2)直接得出。

定理2.1.2 设 $X$ 和 $Y$ 是有限集合，$f$ 是从集合 $X$ 到 $Y$ 的函数。若 $|X|=|Y|$ ，则 $f$ 是单射，当且仅当 $f$ 是满射。
证明：

• 必要性。若 $f$ 是单射函数，则有 $|f(X)|=|X|$ 。又因为 $|X|=|Y|$ ，所以有 $|f(x)|=|Y|$ 。因为 $Y$ 是有限的，且根据函数的定义 $f(X)\subseteq Y$ ，故 $f(X)=Y$ ，因此 $f$ 是一个满射函数。
• 充分性。若 $f$ 是满射函数，假设 $f$ 不是单射函数，则存在 $a,b\in X,a\ne b$ 且 $f(a)=f(b)$ 。所以有 $|X|>|f(x)|$ ，而 $|X|=|Y|$ ，因此有 $|Y|>|f(x)|$ 。因为 $Y$ 是有限的，故 $f(x)\subset Y$ 。这与 $f$ 是满射函数矛盾。

2.2 常函数、恒等函数、置换/排列

定义2.2.1 对于函数 $f:X\to Y$ ，若存在元素 $c\in Y$ ，对于任意 $x\in X$ 都有 $f(x)=c$ ，则称 $f$ 为常函数 constant function 。

定义2.2.2 对于函数 $f:X\to X$ ，若对于任意 $x\in X$ 都有 $f(x)=x$ ，则称 $f$ 为 $X$ 上的恒等函数 identity function 。恒等函数是双射函数。

定义2.2.3 对于函数 $f:X\to X$ ，若 $f$ 是双射的，则称 $f$ 是集合 $X$ 上的一个置换 permutation 或排列。显然，$X$ 上的恒等函数是 $X$ 上的一个置换，亦称为恒等置换或幺置换。当 $X$ 是有限集合且 $|X|=n$ 时，称 $X$ 上的置换是 $n$ 次置换；当 $X$ 是无限集合时，称 $X$ 上的置换是无限次置换。

集合 $X$ 上的 $n$ 次置换通常写成：
$$P=\left(\begin{array}{cccc}{x}_1& x_2& \dots & x_n\\ f(x_1)& f(x_2)& \dots & f(x_n)\end{array}\right)$$ 特别的，置换的复合是可结合的（见【离散数学】集合论 第四章 函数与集合(4) 复合函数与逆函数定理4.4.2），即置换在复合运算下具有可结合性。又因为置换是双射函数，而双射函数的复合运算是双射函数（见【离散数学】集合论 第四章 函数与集合(4) 复合函数与逆函数定理4.4.3），所以置换的复合也是置换，即置换在复合运算下具有封闭性。例如（此处运算顺序先左后右）：
$$P_2\diamond P_3=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)\diamond \left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)=\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)=P_4$$

在后文的抽象代数部分，我们会系统学习置换的性质。

【例3】设 $X$ 是有限集合，且有 $|X|=n$ ，则 $X$ 上有多少个不同的置换？
解：$X$ 上的置换数等于 $X$ 中元素的不同排列数 $n!$ 。

【例4】设 A = { 1 , 2 , 3 } A = \{1, 2, 3\} A={
1,2,3} ，给出 $A$ 上的所有置换。
解：
$$\begin{gathered} P_1=\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right),P_2=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right),P_3=\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right) \\ {P}_4=\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right),P_5=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right),P_6=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right) \end{gathered}$$