集合论-第一二章习题课

1、第一章第一章 集合及其运算（集合及其运算（1 1）例例1 1 设设A,B,CA,B,C是三个任意集合，则是三个任意集合，则(1)(1)若若A AB B则则A A可能吗可能吗? ? A A常真吗常真吗? ?举例说明。举例说明。(2)(2)设设A,BA,B是任意两个集合是任意两个集合,A,AB B与与A A B B同时成立同时成立 这可能吗这可能吗? ?证明你的断言。证明你的断言。 例例2 2 设设A,B,CA,B,C是任意三个集合，则是任意三个集合，则(1)(1)若若A AA A，则有，则有B=CB=C吗？吗？(2)(2)若若A AA A则有则有B=CB=C吗？吗？(3)(3)若若A AA A且

2、且A AA A，则有，则有B=CB=C吗？吗？例例3 3若若A,B,CA,B,C是三个任意集合是三个任意集合, ,当当A AA A且且A AC CA AC C， 是否有是否有B=CB=C？例例4 4 设设A,BA,B是两个任意集合，证明是两个任意集合，证明: :(1)A(1)AB BA A2 2B BA AB BA A=2=2B BA=BA=B2 2A A2 2B BA A；2 2A A2 2B BA A ；(5)(5)A A=2=2A A2 2B B。 (3) (3) 例例6 6设设A,B,CA,B,C是集合是集合, ,求下列各式成立的充分必要条件求下列各式成立的充分必要条件: : (1)

3、(1)(AB)(AB)AC)=AAC)=A；(2)(AB)(2)(AB)AC)=AC)= (3)(AB)(3)(AB)AC)=AC)=(4)(AB)(4)(AB)AC)=AC)=例例7 7 设设A,BA,B是任意集合，则是任意集合，则(1)(1)若若AB=BAB=B，则，则A A与与B B有何关系？有何关系？(2)(2)若若AB=BAAB=BA，则，则A A与与B B又有何关系。又有何关系。例例8 8 设设A,B,CA,B,C是三个任意的集合，则是三个任意的集合，则 (1)(1)证明证明:(:(AB)CAB)CA(A( ； (2)(2)举例说明举例说明( (AB)CAB)CA(A(。例例9 9

4、设设A,BA,B是集合，证明是集合，证明: : (1)A= (1)A=； (2)(AB)(2)(AB) S,T,WS,T,W 习题课（习题课（2 2）例例1 1在在10001000名大学生的调查中名大学生的调查中, ,有有804804人掌握了英语人掌握了英语,205,205人掌握了日语人掌握了日语,190,190人掌握了俄语人掌握了俄语,125,125人既掌握了英语人既掌握了英语又掌握了日语又掌握了日语,57,57人既掌握了日语又掌握了俄语人既掌握了日语又掌握了俄语,85,85人人既掌握了英语又掌握了俄语。试求这既掌握了英语又掌握了俄语。试求这10001000名大学生中名大学生中, ,英语、日

5、语、俄语全掌握的有多少人？英语、日语、俄语全掌握的有多少人？(23(23人人) )例例2 2 某班某班3030名学生中学英语有名学生中学英语有7 7人，学日语有人，学日语有5 5人，这人，这两科都选有两科都选有3 3人，问两科都不选的有多少人？人，问两科都不选的有多少人？ (|A(|AC CB BC C|+|AB|=30, |A|+|AB|=30, |AC CB BC C|=21|=21人人) )例例3 3 某校学生数学、物理、英语三科竞赛，某班某校学生数学、物理、英语三科竞赛，某班3030人，人，学生中有学生中有1515人参加了数学竞赛，人参加了数学竞赛，8 8人参加了物理竞赛，人参加了物理

6、竞赛，6 6人参加了英语竞赛，并且其中人参加了英语竞赛，并且其中3 3人三科竞赛都参加了，人三科竞赛都参加了，问至少有多少人一科竞赛都没有参加。问至少有多少人一科竞赛都没有参加。(7(7人人) )例例4 4 甲每甲每5 5秒放一个爆竹，乙每秒放一个爆竹，乙每6 6秒放一个，丙每秒放一个，丙每7 7秒秒放一个，每人都放放一个，每人都放2121个爆竹，共能听见多少声响。个爆竹，共能听见多少声响。(54(54响响) )习题课（习题课（3 3）例例1 1 设设A,B,CA,B,C是三个任意集合，证明是三个任意集合，证明: :A A (B(B C)=C)=( (A A B)B) C C。 左边左边=(A

7、=(AB BC CC CC C)(B)(BC CC CC C)(C)(CB BC CA AC C)(A)(AB BC)C) 例例2 2设设A,B,CA,B,C是三个任意集合，化简是三个任意集合，化简例例3 3设设A,BA,B是两个集合是两个集合,B,B , ,试证试证: :若若A AB=BB=BB,B,则则A=BA=B。例例4 4设设A,BA,B为集合，试证：为集合，试证：A AB BB BA A的充要条件是下列的充要条件是下列三个条件至少有一个成立：三个条件至少有一个成立：(1)A=(1)A= ；(2)B=(2)B=3)A=B3)A=B。()()()()()()()CCCCCCCCCABCA

8、BCABCABCABCABCABC例例5 5 马大哈写马大哈写n n封信，封信，n n个信封，把个信封，把n n封信放入到封信放入到n n个信个信封中，求全部装错的概率是多少？封中，求全部装错的概率是多少？n n个人，个人，n n顶帽子，全部戴错的概率是多少？顶帽子，全部戴错的概率是多少？ 当当n10n10时时, ,概率都近似等于概率都近似等于0.36790.3679例例6 6 毕业舞会上，小伙子与姑娘跳舞，已知每个小伙毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过子至少与一个姑娘跳过舞，但未能与所有姑娘跳过舞舞。同样地，每个姑娘也至少与一个小伙子跳舞，

9、但也未同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙子与姑娘中，必可找到两个小伙子和两个姑娘，小伙子与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。的一个跳过舞。例例7 7 设设M M1 1,M,M2 2, ,和和N N1 1,N,N2 2, ,是集合是集合S S的子集的两个序列，的子集的两个序列，对对ijij，

10、i,j=1,2,i,j=1,2,，有，有N Ni i N Nj j= = 。 令令试证：试证：1111,() ,2,3,nCnnkkQM QMMn 1()nnniiiNQNM第二章第二章 映射习题映射习题(1)(1)讨论下列映射的性质讨论下列映射的性质例例1 1 X=1,2,3,4,Y=X=1,2,3,4,Y=a,b,c,d,ea,b,c,d,e,f(1)=,f(1)=a,fa,f(2)=a,(2)=a, f(3)= f(3)=c,fc,f(4)=d(4)=d。例例2 2 令令N=1,2,3,N=1,2,3, ，S:NS:NN N，则，则(1)(1) n nS S(n)=n+1,(n)=n+1

11、,称为自然数集称为自然数集N N上的后继函数。上的后继函数。(2)S(1)=1,(2)S(1)=1, n nS(n)=n-1,nS(n)=n-1,n2,2,称为自然数集称为自然数集N N 上的前仆函数。上的前仆函数。例例3 3 令为全体偶自然数之集，令为全体偶自然数之集，f:Ef:EN N， 2m2m f(2m)=mf(2m)=m。例例4 4设为整数的有限集，定义集合设为整数的有限集，定义集合X-X=x-X-X=x-x x|x,x|x,x 。试证：若。试证：若A,BA,B且且|A|A|B|B|2n-1,2n-1,n1n1，则，则(A-A)(A-A)(B-B)(B-B)中有一个正整数。中有一个正

12、整数。第二章映射第二章映射2 2 抽屉原理抽屉原理例例1 1(1)(1)一年一年365365天，今有天，今有366366个人，则至少有两个人生个人，则至少有两个人生日相同。日相同。 (2)(2)抽屉里有抽屉里有1010双手套，从中取双手套，从中取1111只出来，则其中只出来，则其中至少有两只是完整配对的。至少有两只是完整配对的。 (3) (3) 某次会议有某次会议有n n位代表参加，每一位代表至少认位代表参加，每一位代表至少认识其余识其余n-1n-1位中的一位，则在这位中的一位，则在这n n位代表中，至少有两位代表中，至少有两位认识的人数相等。位认识的人数相等。例例2 2 在一个边为在一个边为

13、1 1的正方形内（包括边界），任意地画的正方形内（包括边界），任意地画七个点，则其中必有三个点，以它们为顶点所组成的七个点，则其中必有三个点，以它们为顶点所组成的三角形面积小于三角形面积小于1/61/6。例例3 3 证明，从证明，从1,2,2n1,2,2n中，任选中，任选n+1n+1个数，则在这个数，则在这n+1n+1个数中必有两个数，使得其中一个能整除另一个。个数中必有两个数，使得其中一个能整除另一个。例例4 4 坐标上有五个整数点，则存在有两个点的连线坐标上有五个整数点，则存在有两个点的连线的中点一定是整数点。的中点一定是整数点。例例5 5 证明：在证明：在5252个正整数中，必有两个整数

14、，使得个正整数中，必有两个整数，使得这两个整数之和或差能被这两个整数之和或差能被100100整除。整除。 抽屉原理抽屉原理也称为鸽巢原理、重叠原理。这个原也称为鸽巢原理、重叠原理。这个原理十分简单，但若用得好却会得到意想不到的有趣理十分简单，但若用得好却会得到意想不到的有趣结论。结论。 但也应当注意，但也应当注意，抽屉原理抽屉原理并未告诉我们怎样实并未告诉我们怎样实际地去寻找含有两个或更多个物体的那个抽屉，而际地去寻找含有两个或更多个物体的那个抽屉，而只是肯定了确有这样的抽屉。只是肯定了确有这样的抽屉。例例6 6 已知已知m m个整数个整数a a1 1，a a2 2，a am m，试证：存在两

15、个整，试证：存在两个整数数k,l,0k,l,0 k k j j m m，使得使得a ak+1k+1+a+ak+2k+2+ +a+al l能被能被m m整除。整除。例例7 7证明：对任意正整数证明：对任意正整数N N，存在，存在N N的一个倍数，使得的一个倍数，使得它仅由数字它仅由数字0 0和和7 7组成。（例如组成。（例如N N3,3,有有2592593 3777777；N N4,4,有有192519254 477007700；N N5,5,有有14145 57070；N N6,6,有有129512956 677707770等）。等）。例例8 8 证明：在任意个人中，或有证明：在任意个人中，或

16、有3 3个人相互认识，个人相互认识，或有或有3 3个人相互不认识。个人相互不认识。例例9 9 5 5个整数中必有个整数中必有3 3个整数其和能被个整数其和能被3 3整除。整除。例例1010 设设a a1 1,a,a2 2, ,a,an n为为1 1，2 2，3 3，n n的任一排列的任一排列, ,若若n n是奇数且是奇数且(a(a1 1-1)(a-1)(a2 2-2)-2)(a(an n-n)-n) 0 0，则乘积为偶数。则乘积为偶数。 上面的上面的例例2 2、例、例8 8使用的使用的鸽巢原理鸽巢原理实际上是鸽巢原实际上是鸽巢原理的一种推广形式，称为理的一种推广形式，称为“平均值原理平均值原理

17、”，即即 若把若把m m只物体放到只物体放到n n个抽屉里，则一定存在某一个个抽屉里，则一定存在某一个抽屉，它里面至少有抽屉，它里面至少有(m-1)/n+1(m-1)/n+1个物体。个物体。 这里这里xx表示不大于表示不大于x x的最大整数。的最大整数。2.2 2.2 抽屉原理强形式抽屉原理强形式抽屉原理强形式抽屉原理强形式: :设设m m1 1,m,m2 2,m,mn n都是正整数都是正整数, ,若把若把m m1 1+m+m2 2+m+mn n-n+1-n+1个物体放到个物体放到n n个抽屉里个抽屉里, ,则或第一个抽则或第一个抽屉里至少有屉里至少有m m1 1个物体个物体, ,或第二个抽屉

18、里至少有或第二个抽屉里至少有m m2 2个物个物体体,或第或第n n个抽屉里至少有个抽屉里至少有m mn n个物体。个物体。说明说明: :当当m m1 1=m=m2 2=m=mn n=2=2时，时，m m1 1+m+m2 2+m+mn n-n+1=n+1-n+1=n+1。抽屉。抽屉原理是强形式的一种特殊情况。原理是强形式的一种特殊情况。推论推论1 1 若有若有m m个物体放到个物体放到n n个抽屉里，则一定存在某个抽屉里，则一定存在某一个抽屉，它里面至少有一个抽屉，它里面至少有(m-1)/n+1(m-1)/n+1个物体。个物体。推论推论2 2 若把若把n(m-1)+1n(m-1)+1个物体放进

19、个物体放进n n个抽屉里，则一定个抽屉里，则一定存在某一个抽屉，它里面至少有存在某一个抽屉，它里面至少有m m个物体。个物体。 此推论是强形式中，当此推论是强形式中，当m m1 1=m=m2 2=m=mn n=m =m 时的特殊时的特殊情况。情况。推 论推 论 3 3 若若 m m1 1, m, m2 2, , m, , mn n是是 n n 个 正 整 数 ， 且个 正 整 数 ， 且(m(m1 1+m+m2 2+m+mn n)/nr-1)/nr-1，则，则m m1 1,m,m2 2,m,mn n中至少有一个中至少有一个大于或等于大于或等于 r r 。 鸽巢原理强形式例题鸽巢原理强形式例题例

20、例1 1 一个人步行了十小时，共走一个人步行了十小时，共走4545公里，已知他第公里，已知他第一个小时走了一个小时走了6 6公里，而最后一小时只走了公里，而最后一小时只走了3 3公里，公里，证明一定存在连续的两个小时，在这两个小时之内证明一定存在连续的两个小时，在这两个小时之内至少走了至少走了9 9公里。公里。例例2 2 一个园环等分一个园环等分3636段，将段，将3636个数字个数字1,2,361,2,36任任意地写在每一段上，使每一段上恰有一个数字，证意地写在每一段上，使每一段上恰有一个数字，证明：一定存在连续的三段，在这三段上的数字之和明：一定存在连续的三段，在这三段上的数字之和至少为至

21、少为5656。 S,T,WS,T,W 例例3 3设设A,B,CA,B,C是三个任意集合，化简是三个任意集合，化简例例4 4设设A,BA,B是两个集合是两个集合,B,B , ,试证试证: :若若A AB=BB=BB,B,则则A=BA=B。例例5 5设为整数的有限集，定义集合设为整数的有限集，定义集合 X-X=x- X-X=x-x|x,xx|x,x。试证：若。试证：若A,BA,B且且|A|A|B|B|2n-1,n12n-1,n1，则，则(A-A)(A-A)(B-B)(B-B)中有一个正整数。中有一个正整数。() () () ()() () ()CCCCCCCCCA B CAB CA BCA B C

22、ABCA BCAB C 第二章第二章 映射习题课（映射习题课（2 2）例例1 1 令令X=xX=x1 1,x,x2 2, , ,x xm m,Y=y,Y=y1 1,y,y2 2, , ,y yn n,问：问：(1)(1)有多少个不同的由有多少个不同的由X X到到Y Y的关系？的关系？(2)(2)有多少个不同的由有多少个不同的由X X到到Y Y的映射？的映射？(3)(3)有多少个不同的由有多少个不同的由X X到到Y Y的双射？的双射？(4)(4)有多少个不同的从有多少个不同的从X X到到Y Y的单射？的单射？例例2 2 设设f:Xf:XY Y，A,BA,BX,X,证明证明: :(1)f(A(1)

23、f(AB)=f(A)B)=f(A)f(B); (2)f(Af(B); (2)f(AB)B)f(A)f(A)f(B);f(B);(3)f(A)f(B)(3)f(A)f(B)f(AB);(4)f(A)f(AB);(4)f(A) f(B)f(B)f(Af(A B)B)。例例3 3设设X X是一个有限集合，从是一个有限集合，从X X到到X X的部分映射有的部分映射有多少？多少？例例4 4 设设u u1,1,u u2,2,u umn+1mn+1是一个两两不相同的整数构是一个两两不相同的整数构成的数列，则必有长至少为成的数列，则必有长至少为n n1 1的递增子序列的递增子序列或有长至少为或有长至少为m m

24、1 1的递减子序列。的递减子序列。例例5 5设设N=1,2,3,N=1,2,3,试构造两个映射试构造两个映射f,g:Nf,g:N，使得使得fgfg=I=IN N，但，但gfgf I IN N。例例6 6设设N=1,2,3,N=1,2,3,试构造两个映射试构造两个映射f,g:Nf,g:N，使得使得gfgf=I=IN N，但，但fgfg I IN N。例例9 9 设设，证明：，证明：(1)f(1)f是单射是单射 F F 2 2X X，f f1 1(f(f(F(F)=F)=F；(2)f(2)f是满射是满射 E E 2 2Y Y，f(ff(f1 1(E)=E(E)=E。例例1010 设设， X X =

25、m=m， Y Y =n=n，则则(1)(1)若若f f是左可逆的，则是左可逆的，则f f有多少个左逆映射？有多少个左逆映射？(2)(2)若若f f是右可逆的，则是右可逆的，则f f有多少个右逆映射？有多少个右逆映射？例例1111 设设，则，则(1)(1)若存在唯一的一个映射若存在唯一的一个映射g g, ,使得使得gfgf=I=IX X, ,则则f f是可是可逆的吗？逆的吗？(2)(2)若存在唯一的一个映射若存在唯一的一个映射g g, ,使得使得fgfg=I=IY Y, ,则则f f是可是可逆的吗？逆的吗？习题（习题（2 2）例例1 1 设设f:Xf:XY Y，A AX X，B BY Y，证明：，证明：f(ff(f-1-1(B)(B)A)=BA)=Bf(A)f(A)。例例2 2 设设f:Af:AB,B,证明证明: : T T例例3 3 设设，证明：，证明： (1)f(1)f是单射是单射 F F 2 2X X，f f1 1(f(F)=F(f(F)=F； (2)f(2)f是满射是满射 E E 2 2Y Y，f(ff(f1 1(E)=E(E)=E。例例4 4 设有映射设有映射f:Af:AB B,HA，令，令H HC C是是H H对对A A中