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

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),根据