发布时间 : 星期一 文章离散数学第二版邓辉文编著第一章第二节习题答案更新完毕开始阅读
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)?x3?1.
(4)f:N?N?N,f(x1,x2)?x1?x2?1. (5)f:N?N?N,f(x)?(x,x?1).
解 (1)对于任意对x1,x2?Z，若f(x1)?f(x2)，则3x1?3x2，于是x1?x2，所以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)对于任意对x1,x2?R，若f(x1)?f(x2)，则x1?1?x2?1，于是x1?x2，所以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，而任意(x1,x2)?N?N均有f(x1,x2)?x1?x2?1?0，于是f不是满射. 显然，f就不是双射.
(5)由于x1,x2?N，若f(x1)?f(x2)，则(x1,x1?1)?(x2,x2?1)，于是
x1?x2，因此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?IB?f. (2)IA?f?f.
特别地，若f:A?A，则f?IA?IA?f?f.
证 (1)对于任意x?A，由于f(x)?B，所以(f?IB)(x)?IB(f(x))?f(x)，因此f?IB?f.
(2)对于任意x?A，由于IA(x)?x，所以(IA?f)(x)?f(IA(x))?f(x)，于是有IA?f?f.
由(1)和(2)知，若f:A?A，则f?IA?IA?f?f.
5.试举出一个例子说明f?f?f成立，其中f:A?A且f?IA. 若f的逆映射存在，满足条件的f还存在吗?
解 令A?{a,b,c}，f(a)?f(b)?f(c)?a，即对于任意x?A，f(x)?a，显
然
f:A?A且
f?IA. 而对于任意
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?IA，所以
?1?1于是利用定理7有(f?f)?f?(f?f)?IA，f?1?(f?f)?f?1?(f?IA)，
进而IA?f?IA?IA，因此f?IA. 所以若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不一定是单射.
证 对于任意x1,x2?A，假定f(x1)?f(x2)，则显然g(f(x1))?g(f(x2))，即(f?g)(x1)?(f?g)(x2). 因为f?g是单射，所以x1?x2，于是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?IA且g?f?IB，试证明: f是双射且f?1?g.
证 因为f?g?IA，而IA是单射，所以f是单射. 又因为g?f?IB，而IB是满射，所以f是满射. 因此f是双射.
由于f是双射，所以f而(f?1?1存在. 因为f?g?IA，于是f?1?(f?g)?f?1?IA.
?f)?g?f?1?IA且IB?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?IB?f?1?f?f?1?IA，
(g?1?f?1)?(f?g)?g?1?(f?1?f)?g?g?1?IB?g?g?1?g?IC，
在上面的推导中多次利用了定理7. 由第7题知，(f?g)?1?g?1?f10.设G是集合A到A的所有双射组成的集合，证明 (1)任意f,g?G，有f?g?G.
(2)对于任意f,g,h?G，有(f?g)?h?f?(g?h). (3)IA?G且对于任意f?G，有IA?f?f?IA?f. (4)对于任意f?G，有f?1?1.
?G且f?f?1?f?1?f?IA.
证 (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?n，不存在满射；若m?n，先将m个元素划分成n个块(参见1.5节)，共有S(m,n)种方式；再将B中元素进行全排列，共有n!种方式，于是A到B的满射共有S(m,n)?n!个.
(2) A到B的单射 若m?n，不存在单射；若m?n，由于B中任意选取m个
m元素，再将其进行全排列都得到A到B的单射，故A到B的单射共有Cn?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是双射.
证 对于任意(a1,c1)?A?C，(a2,c2)?A?C，假定h(a1,c1)?h(a2,c2)，即(f(a1),g(c1))?(f(a2),g(c2))，于是f(a1)?f(a2)且g(c1)?g(c2)，根据