大家好，又见面了，我是你们的朋友全栈君。
本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解离散数学，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：
- （国外经典教材）离散数学及其应用 第七版
Discrete Mathematics and Its Applications 7th，作者是Kenneth H.Rosen，袁崇义译，机械工业出版社- 离散数学 第二版，武波等编著，西安电子科技大学出版社，2006年
- 离散数学 第三版，方世昌等编著，西安电子科技大学出版社，2013年
- （经典参考书及其题解）离散数学/离散数学——理论•分析•题解，左孝凌、李为鉴、刘永才编著，上海科学技术文献出版社
- 离散数学习题集：数理逻辑与集合论分册，耿素云；图论分册，耿素云；抽象代数分册， 张立昂。北京大学出版社
2. 特殊函数类
2.1 单射、满射和双射及其性质
根据函数映射的特征，产生了三种特殊的函数类：单射、满射和双射。当然，不是单射也不是满射的函数也有很多。
定义2.1.1 设 f f f 是从集合 X X X 到 Y Y Y 的函数（每个 x i x_i xi 都只对应一个 f ( x i ) f(x_i) f(xi) ）。
（1）任取 x 1 , x 2 ∈ X x_1, x_2\in X x1,x2∈X ，如果 x 1 ≠ x 2 x_1 \ne x_2 x1=x2 ，那么 f ( x 1 ) ≠ f ( x 2 ) f(x_1) \ne f(x_2) f(x1)=f(x2) ，则称 f f f 是单射函数 injective function ，简称单射或内映射 into mapping 、入射等（即不同的 x i x_i xi 对应的 f ( x i ) f(x_i) f(xi) 不同）。
（2）任取 y ∈ Y y \in Y y∈Y ，存在 x ∈ X x \in X x∈X ，使得 f ( x ) = y f(x) = y f(x)=y ，则称 f f f 为满射函数 surjective function ，简称满射或上映射 onto mapping（即 f ( X ) = Y f(X) = Y f(X)=Y ）。
（3）若 f f f 既是单射又是满射，则称 f f f 是双射函数 bijective function ，简称双射或一一对应的映射。
【例1】判断下列函数的类型。
（1） s : N → N , s ( x ) = x + 2 s: \N \to \N, s(x) = x+2 s:N→N,s(x)=x+2
（2） f : N → N , f ( x ) = x m o d 10 f: \N \to \N, f(x) = x \bmod 10 f:N→N,f(x)=xmod10
（3） f : N → N , f ( x ) = { x − 1 i f i s o d d ( x ) x + 1 i f i s e v e n ( x ) f:\N \to \N, f(x) = \begin{cases} x – 1 \quad \mathtt{if\ isodd(x)} \\ x + 1\quad \mathtt{if\ iseven(x)} \end{cases} f:N→N,f(x)={
x−1if isodd(x)x+1if iseven(x)
（4） h : R → R , h ( x ) = x 3 + 2 x 2 h: \R \to \R, h(x) = x^3 + 2x^2 h:R→R,h(x)=x3+2x2
（5） a , b ∈ R a, b \in R a,b∈R 且 a ≠ b a \ne b a=b ， g : [ 0 , 1 ] → [ a , b ] , g ( x ) = ( b − a ) x + a g: [0, 1] \to [a, b], g(x) = (b – a) x + a g:[0,1]→[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 s s 是单射而非满射，因为 0 , 1 0, 1 0,1 没有原像。
（2） f f f 既非单射也非满射。
（3） f f f 是双射。
（4） h h h 是满射而非单射。
（5） g g g 是双射。
（6） f f f 是单射而非满射。因为 ρ ( N ) \rho(\N) ρ(N) 中 N \N N 上的每个元素在函数 f f f 下都有一个唯一的像，但 ρ ( N ) \rho(\N) ρ(N) 中有些元素没有原像，例如 { 0 , 1 } \{0, 1\} {
0,1} 。【离散数学】集合论 第四章 函数与集合(6) 三歧性定理、两集合基数判等定理（基数的比较）、Cantor定理这篇文章的 Cantor 定理中证明了任意函数 g : M → ρ ( M ) g:M→ρ(M) g:M→ρ(M) 均不是满射。
【例2】 f : [ 0 , 1 ] → [ a , b ] , a < b , f ( x ) = ( b − a ) x + a f: [0, 1] \to [a, b],\ a < b,\ f(x) = (b – a) x + a f:[0,1]→[a,b], a<b, f(x)=(b−a)x+a ，证明 f f f 为双射。
证明：
（1）对任意 x 1 , x 2 ∈ [ 0 , 1 ] , x 1 ≠ x 2 x_1, x_2 \in [0, 1], \ x_1 \ne x_2 x1,x2∈[0,1], x1=x2 ，易知 f ( x 1 ) = ( b − a ) x 1 + a ≠ ( b − a ) x 2 + a = f ( x 2 ) f(x_1) = (b – a) x_1 + a \ne (b – a) x_2 + a = f(x_2) f(x1)=(b−a)x1+a=(b−a)x2+a=f(x2) 。故 f f f 是单射函数。
（2）显然，对任意 y ∈ [ a , b ] y\in [a, b] y∈[a,b] ，均存在 x = y − a b − a ∈ [ 0 , 1 ] x =\dfrac{ y – a}{b – a} \in [0, 1] x=b−ay−a∈[0,1] ，故 f f f 是满射函数。
（3）由(1)、(2)可知， f f f 是双射函数。
定理2.1.1 设 X X X 和 Y Y Y 是有限集合， f f f 是从集合 X X X 到 Y Y Y 的函数。
（1）若 f f f 是单射，则必有 ∣ X ∣ ≤ ∣ Y ∣ |X| \le |Y| ∣X∣≤∣Y∣ 。
（2）若 f f f 是满射，则必有 ∣ X ∣ ≥ ∣ Y ∣ |X| \ge |Y| ∣X∣≥∣Y∣ 。
（3）若 f f f 是双射，则必有 ∣ X ∣ = ∣ Y ∣ |X| = |Y| ∣X∣=∣Y∣ 。
证明 ：
（1）因为 f f f 是单射，所以 ∣ f ( x ) ∣ = ∣ X ∣ |f(x)| = |X| ∣f(x)∣=∣X∣ 。又因为 f ( x ) ⊆ Y f(x) \subseteq Y f(x)⊆Y ，所以有 ∣ f ( x ) ∣ ≤ ∣ Y ∣ |f(x) | \le |Y| ∣f(x)∣≤∣Y∣ ，故有 ∣ X ∣ ≤ ∣ Y ∣ |X| \le |Y| ∣X∣≤∣Y∣ 。
（2）假设 ∣ X ∣ < ∣ Y ∣ |X| < |Y| ∣X∣<∣Y∣ ，因为 ∣ f ( x ) ∣ ≤ ∣ X ∣ |f(x) | \le |X| ∣f(x)∣≤∣X∣（函数定义，对每个 x ∈ X x \in X x∈X ，都有唯一的一个 y ∈ Y y \in Y y∈Y 满足 ⟨ x , y ⟩ ∈ f \lang x, y\rang \in f ⟨x,y⟩∈f ），所以有 ∣ f ( x ) ∣ < ∣ Y ∣ |f(x)|<|Y| ∣f(x)∣<∣Y∣，即 f ( X ) ⊂ Y f(X) \subset Y f(X)⊂Y ，这与 f f f 是满射矛盾。
（3）可由(1)和(2)直接得出。
定理2.1.2 设 X X X 和 Y Y Y 是有限集合， f f f 是从集合 X X X 到 Y Y Y 的函数。若 ∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣X∣=∣Y∣ ，则 f f f 是单射，当且仅当 f f f 是满射。
证明：
- 必要性。若 f f f 是单射函数，则有 ∣ f ( X ) ∣ = ∣ X ∣ |f(X)| = |X| ∣f(X)∣=∣X∣ 。又因为 ∣ X ∣ = ∣ Y ∣ |X| = |Y| ∣X∣=∣Y∣ ，所以有 ∣ f ( x ) ∣ = ∣ Y ∣ |f(x)|= |Y| ∣f(x)∣=∣Y∣ 。因为 Y Y Y 是有限的，且根据函数的定义 f ( X ) ⊆ Y f(X) \subseteq Y f(X)⊆Y ，故 f ( X ) = Y f(X) = Y f(X)=Y ，因此 f f f 是一个满射函数。
- 充分性。若 f f f 是满射函数，假设 f f f 不是单射函数，则存在 a , b ∈ X , a ≠ b a, b \in X, a\ne b a,b∈X,a=b 且 f ( a ) = f ( b ) f(a) = f(b) f(a)=f(b) 。所以有 ∣ X ∣ > ∣ f ( x ) ∣ |X| > |f(x)| ∣X∣>∣f(x)∣ ，而 ∣ X ∣ = ∣ Y ∣ |X| = |Y| ∣X∣=∣Y∣ ，因此有 ∣ Y ∣ > ∣ f ( x ) ∣ |Y| > |f(x)| ∣Y∣>∣f(x)∣ 。因为 Y Y Y 是有限的，故 f ( x ) ⊂ Y f(x) \subset Y f(x)⊂Y 。这与 f f f 是满射函数矛盾。
2.2 常函数、恒等函数、置换/排列
定义2.2.1 对于函数 f : X → Y f: X\to Y f:X→Y ，若存在元素 c ∈ Y c \in Y c∈Y ，对于任意 x ∈ X x\in X x∈X 都有 f ( x ) = c f(x) = c f(x)=c ，则称 f f f 为常函数 constant function 。
定义2.2.2 对于函数 f : X → X f: X\to X f:X→X ，若对于任意 x ∈ X x \in X x∈X 都有 f ( x ) = x f(x) = x f(x)=x ，则称 f f f 为 X X X 上的恒等函数 identity function 。恒等函数是双射函数。
定义2.2.3 对于函数 f : X → X f: X\to X f:X→X ，若 f f f 是双射的，则称 f f f 是集合 X X X 上的一个置换 permutation 或排列。显然， X X X 上的恒等函数是 X X X 上的一个置换，亦称为恒等置换或幺置换。当 X X X 是有限集合且 ∣ X ∣ = n |X| = n ∣X∣=n 时，称 X X X 上的置换是 n n n 次置换；当 X X X 是无限集合时，称 X X X 上的置换是无限次置换。
集合 X X X 上的 n n n 次置换通常写成：
P = ( x 1 x 2 … x n f ( x 1 ) f ( x 2 ) … f ( x n ) ) P = \begin{pmatrix} x_1 & x_2 &\dots& x_n\\ f(x_1) & f(x_2) &\dots& f(x_n) \end{pmatrix} P=(x1f(x1)x2f(x2)……xnf(xn)) 特别的，置换的复合是可结合的（见【离散数学】集合论 第四章 函数与集合(4) 复合函数与逆函数定理4.4.2），即置换在复合运算下具有可结合性。又因为置换是双射函数，而双射函数的复合运算是双射函数（见【离散数学】集合论 第四章 函数与集合(4) 复合函数与逆函数定理4.4.3），所以置换的复合也是置换，即置换在复合运算下具有封闭性。例如（此处运算顺序先左后右）：
P 2 ⋄ P 3 = ( 1 2 3 1 3 2 ) ⋄ ( 1 2 3 2 1 3 ) = ( 1 2 3 2 3 1 ) = P 4 P_2 \diamond P_3 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \diamond \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = P_4 P2⋄P3=(112332)⋄(122133)=(122331)=P4
在后文的抽象代数部分，我们会系统学习置换的性质。
【例3】设 X X X 是有限集合，且有 ∣ X ∣ = n |X| = n ∣X∣=n ，则 X X X 上有多少个不同的置换？
解： X X X 上的置换数等于 X X X 中元素的不同排列数 n ! n! n! 。
【例4】设 A = { 1 , 2 , 3 } A = \{1, 2, 3\} A={
1,2,3} ，给出 A A A 上的所有置换。
解：
P 1 = ( 1 2 3 1 2 3 ) , P 2 = ( 1 2 3 1 3 2 ) , P 3 = ( 1 2 3 2 1 3 ) P 4 = ( 1 2 3 2 3 1 ) , P 5 = ( 1 2 3 3 1 2 ) , P 6 = ( 1 2 3 3 2 1 ) P_1 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix},\ P_2 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix},\ P_3 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \\ {} \\ P_4 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix},\ P_5 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix},\ P_6 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} P1=(112233), P2=(112332), P3=(122133)P4=(122331), P5=(132132), P6=(132231)
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/143696.html原文链接：https://javaforall.net
