离散数学第二版邓辉文编著第一章第二节习题答案

1.2 映射的有关概念

习题1.2

1. 分别计算⎡1. 5⎤，⎡-1⎤，⎡-1. 5⎤，⎣1. 5⎦，⎣-1⎦，⎣-1. 5⎦.

解 ⎡1. 5⎤=2，⎡-1⎤=-1，⎡-1. 5⎤=-1，⎣1. 5⎦=1，⎣-1⎦=-1，⎣-1. 5⎦=-2.

2. 下列映射中，那些是双射? 说明理由.

(1)f :Z →Z , f (x ) =3x .

(2)f :Z →N , f (x ) =|x |+1.

(3)f :R →R , f (x ) =x 3+1.

(4)f :N ⨯N →N , f (x 1, x 2) =x 1+x 2+1.

(5)f :N →N ⨯N , f (x ) =(x , x +1).

解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射.

(2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射.

(3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时

1⎡⎤3f (x ) =x +1=⎢(y -1) 3⎥+1=(y -1) +1=y ，

⎣⎦33313

所以f 是满射. 进而f 是双射.

(4)由于(1, 2), (2, 1) ∈N ⨯N 且(1, 2) ≠(2, 1) ，而f (1, 2) =f (2, 1) =4，因此f 不是单射. 又由于0∈N ，而任意(x 1, x 2) ∈N ⨯N 均有f (x 1, x 2) =x 1+x 2+1≠0，于是f 不是满射. 显然，f 就不是双射.

(5)由于x 1, x 2∈N ，若f (x 1) =f (x 2) ，则(x 1, x 1+1) =(x 2, x 2+1) ，于是x 1=x 2，因此f 是单射. 又由于(0, 0) ∈N ⨯N ，而任意x ∈N 均有f (x ) =(x , x +1) ≠(0, 0) ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.

3. 对于有限集合A 和B ，假定f :A →B 且|A |=|B |，证明: f 是单射的充要条件是f 是满射. 对于无限集合，上述结论成立吗？举例说明.

证(⇒) 因为f 是单射，所以|A |=|f (A ) |. 由于|A |=|B |，所以|f (A ) |=|B |. 又因为B 有限且f (A ) ⊆B ，故f (A ) =B ，即f 是满射.

(⇐) 若f 是满射，则f (A ) =B . 由于|A |=|B |，于是|A |=|f (A ) |. 又因为A 和B 是有限集合，因此f 是单射.

对于无限集合，上述结论不成立. 例如f :N →N ，f (x ) =2x ，f 是单射，但f 不是满射.

4. 设f :A →B , 试证明:

(1)f I B =f .

(2)I A f =f .

特别地，若f :A →A ，则f I A =I A f =f .

证 (1)对于任意x ∈A ，由于f (x ) ∈B ，所以(f I B )(x ) =I B (f (x )) =f (x ) ，因此f I B =f .

(2)对于任意x ∈A ，由于I A (x ) =x ，所以(I A f )(x ) =f (I A (x )) =f (x ) ，于是有I A f =f .

由(1)和(2)知，若f :A →A ，则f I A =I A f =f .

5. 试举出一个例子说明f f =f 成立，其中f :A →A 且f ≠I A . 若f 的逆映射存在，满足条件的f 还存在吗?

解 令A ={a , b , c }，f (a ) =f (b ) =f (c ) =a ，即对于任意x ∈A ，f (x ) =a ，显然f :A →A 且f ≠I A . 而对于任意x ∈A ，有(f f )(x ) =f (f (x )) =f (a ) =a ，因此f f =f .

若f f =f 且f 的逆映射f -1存在，由第3题知f f =f =f I A ，所以

-1-1于是利用定理7有(f f ) f =(f f ) I A ，f -1 (f f ) =f -1 (f I A ) ，

进而I A f =I A I A ，因此f =I A . 所以若f 的逆映射存在，满足条件的f 不存在.

6. 设f :A →B , g :B →C . 若f 和g 是满射，则f g 是满射，试证明.

证 因为f 是满射，所以f (A ) =B . 又因为g 是满射，所以g (B ) =C . 于是(f g )(A ) =g (f (A )) =g (B ) =C ，因此f g 是A 到C 的满射.

另证 对于任意z ∈C ，因为g 是满射，于是存在y ∈B 使得g (y ) =z . 又因为f 是满射，存在x ∈A 使得f (x ) =y . 因此，(f g )(x ) =g (f (x )) =g (y ) =z ，所以f g 是A 到C 的满射.

7. 设f :A →B , g :B →C . 试证明: 若f g 是单射，则f 是单射. 试举例说明，这时g 不一定是单射.

证 对于任意x 1, x 2∈A ，假定f (x 1) =f (x 2) ，则显然g (f (x 1)) =g (f (x 2)) ，即(f g )(x 1) =(f g )(x 2) . 因为f g 是单射，所以x 1=x 2，于是f 是单射.

例如A ={a , b }，B ={1, 2, 3}，C ={α, β, γ, δ}，令f (a ) =1, f (b ) =2，g (1) =α, g (2) =β, g (3) =β，则显然有(f g )(a ) =g (f (a )) =g (1) =α, (f g )(b ) =g (f (b )) =g (2) =β, 于是f g 是A 到C 的单射，但g 显然不是单射.

8. 设f :A →B , 若存在g :B →A ，使得f g =I A 且g f =I B ，试证明: f 是双射且f -1=g .

证 因为f g =I A ，而I A 是单射，所以f 是单射. 又因为g f =I B ，而I B 是满射，所以f 是满射. 因此f 是双射.

由于f 是双射，所以f

而(f -1-1存在. 因为f g =I A ，于是f -1 (f g ) =f -1 I A . f ) g =f -1 I A 且I B g =f -1，所以有f -1=g .

9. 设f :A →B , g :B →C . 若f 和g 是双射，则f g 是双射且(f g ) -1=g -1 f -1.

-1-1证 根据定理4(1)(2)知，f g 是双射. 下证(f g ) =g f -1. 因为

(f g ) (g -1 f -1) =f (g g -1) f -1=f I B f -1=f f -1=I A ， (g -1 f -1) (f g ) =g -1 (f -1 f ) g =g -1 I B g =g -1 g =I C ， 在上面的推导中多次利用了定理7. 由第7题知，(f g ) -1=g -1 f

10. 设G 是集合A 到A 的所有双射组成的集合，证明

(1)任意f , g ∈G ，有f g ∈G .

(2)对于任意f , g , h ∈G ，有(f g ) h =f (g h ).

(3)I A ∈G 且对于任意f ∈G ，有I A f =f I A =f .

(4)对于任意f ∈G ，有f -1-1. ∈G 且f f -1=f -1 f =I A .

证 (1)由定理5.

(2)由定理7.

(3)由第3题.

(4)由定理4.

11. 若A = {a , b , c }, B = {1, 2}, 问A 到B 的满射、单射、双射各有多少个? 试推广你的结论.

解 将A 中的3个元素对应到B 中的2个元素，相当于将3个元素分成2部分，共有3种分法; 在计算A 到B 的满射个数时还需要将B 中元素进行排列，共有2种排列方式，于是A 到B 的满射共有3⨯2=6个(请自己分别写出A 到B 的6个满射).

由于|A |=3, |B |=2，所以A 到B 的单射没有，进而A 到B 的双射也没有. 假设|A |=m , |B |=n .

(1) A到B 的满射 若m

(2) A到B 的单射 若m >n ，不存在单射；若m ≤n ，由于B 中任意选取m 个

m 元素，再将其进行全排列都得到A 到B 的单射，故A 到B 的单射共有C n ⋅m ! 个.

(3)A 到B 的双射 若m ≠n ，不存在双射；若m =n ，此时B 中元素的任意一个排列均可得到一个A 到B 的双射，因此A 到B 的双射共有m ! 个.

12. 设A , B , C , D 是任意集合，f 是A 到B 的双射， g 是C 到D 的双射，令h :A ⨯C →B ⨯D ，对任意(a , c ) ∈A ⨯C , h (a , c ) =(f (a ), g (c )). 证明:h 是双射.

证 对于任意(a 1, c 1) ∈A ⨯C ，(a 2, c 2) ∈A ⨯C ，假定h (a 1, c 1) =h (a 2, c 2) ，即(f (a 1), g (c 1)) =(f (a 2), g (c 2)) ，于是f (a 1) =f (a 2) 且g (c 1) =g (c 2) ，根据

已知条件有a 1=a 2且c 1=c 2，进而(a 1, c 1) =(a 2, c 2) ，因此h 是单射.

任意(b , d ) ∈B ⨯D ，则b ∈B , d ∈D ，由于f 是A 到B 的双射且g 是C 到D 的双射，于是存在a ∈A , c ∈C 使得f (a ) =b , g (c ) =d ，因此h (a , c ) =(f (a ), g (c )) =(b , d ) ，所以h 是满射.

故h 是双射.

13. 设f :A →B , g :B →C , h :C →A ，若f g h =I A ，g h f =I B ，h f g =I C ，则f , g , h 均可逆，并求出f -1, g -1, h -1.

证 因为恒等映射是双射，多次使用定理6即可得结论.

由于f g h =I A ，所以f 是单射且h 是满射. 由于g h f =I B ，所以g 是单射且f 是满射. 由于h f g =I C ，所以h 是单射且g 是满射. 于是f , g , h 是双射，因此f , g , h 均可逆.

由于f g h =I A ，所以f -1=g h 且h -1=f g ，进而g -1=h f .

14. 已知Ackermann 函数A :N ⨯N →N 的定义为

(1)A (0, n ) =n +1, n ≥0;

(2)A (m , 0) =A (m -1, 1), m >0;

(3)A (m , n ) =A (m -1, A (m , n -1)), m >0, n >0.

分别计算A (2, 3) 和A (3, 2) .

解 由已知条件有A (0, 1) =2，A (1, 0) =A (0, 1) =2，于是

A (1, 1) =A (0, A (1, 0)) =A (0, 2) =2+1=3，

A (1, 2) =A (0, A (1, 1)) =A (0, 3) =3+1=4，

由此可进一步得出

A (1, n ) =n +2，

A (2, 0) =A (1, 1) =3，

A (2, 1) =A (1, A (2, 0)) =A (1, 3) =3+2=5，

A (2, 2) =A (1, A (2, 1)) =A (1, 5) =5+2=7， A (2, 3) =A (1, A (2, 2)) =A (1, 7) =7+2=9. 因此有

A (2, n ) =2n +3，

A (3, 0) =A (2, 1) =2⋅1+3=5，

A (3, 1) =A (2, A (3, 0)) =A (2, 5) =2⋅5+3=13， A (3, 2) =A (2, A (2, 2)) =A (2, 13) =2⋅13+3=29. 所以有A (2, 3) =9, A (3, 2) =29.