集合论-第一二章习题课

《集合论-第一二章习题课》由会员分享，可在线阅读，更多相关《集合论-第一二章习题课（36页珍藏版）》请在金锄头文库上搜索。

1、,第一章 集合及其运算（1）例1 设A,B,C是三个任意集合，则 (1)若AB,BC,则AC可能吗?AC常真吗?举例说明。 (2)设A,B是任意两个集合,AB与AB同时成立这可能吗?证明你的断言。 例2 设A,B,C是任意三个集合，则 (1)若AB=AC，则有B=C吗？ (2)若AB=AC，则有B=C吗？ (3)若AB=AC且AB=AC，则有B=C吗？ 例3若A,B,C是三个任意集合,当AB=AC且ACB=ACC，是否有B=C？,例4 设A,B是两个任意集合，证明: (1)AB2A2BAB； (2)2A=2BA=B； (3)2A2B2AB； (4)举例说明：2A2B2AB ； (5)2AB=2

2、A2B。 例5(多项选择)集合A是以空集为唯一元素的集合,集合B=P(P(A)，则有：( )。(1)B；(2)B (3)B；(4),B ；(5),B。 例6设A,B,C是集合,求下列各式成立的充分必要条件:(1)(AB)(AC)=A；(2)(AB)(AC)=；(3)(AB)(AC)=；(4)(AB)(AC)=。,例7 设A,B是任意集合，则 (1)若AB=B，则A与B有何关系？ (2)若AB=BA，则A与B又有何关系。 例8 设A,B,C是三个任意的集合，则(1)证明:(AB)CA(BC) ；(2)举例说明(AB)CA(BC)。 例9设A,B是集合，证明:(1)A=B=AB；(2)(AB)B=

3、(AB)BB=。 例10设A,B,C是任意三个集合，则(AB)C=A(BC)CA。 例11设V是任一集合，证明：S,T,W2V有STW当且仅当STSW且SW。,习题课（2） 例1在1000名大学生的调查中,有804人掌握了英语,205 人掌握了日语,190人掌握了俄语,125人既掌握了英语又掌握了日语,57人既掌握了日语又掌握了俄语,85人既掌握了英语又掌握了俄语。试求这1000名大学生中,英语、日语、俄语全掌握的有多少人？ (23人) 例2 某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？(|ACBC|+|AB|=30, |ACBC|=21人),例3 某

4、校学生数学、物理、英语三科竞赛，某班30人，学生中有15人参加了数学竞赛，8人参加了物理竞赛，6人参加了英语竞赛，并且其中3人三科竞赛都参加了，问至少有多少人一科竞赛都没有参加。 (7人) 例4 甲每5秒放一个爆竹，乙每6秒放一个，丙每7秒放一个，每人都放21个爆竹，共能听见多少声响。 (54响),习题课（3） 例1 设A,B,C是三个任意集合，证明: A(BC)=(AB)C。 左边=(ABCCC)(BACCC)(CBCAC)(ABC) 例2设A,B,C是三个任意集合，化简例3设A,B是两个集合,B,试证:若AB=BB,则A=B。 例4设A,B为集合，试证：ABBA的充要条件是下列三个条件至少

5、有一个成立： (1)A=；(2)B=;(3)A=B。,例5 马大哈写n封信，n个信封，把n封信放入到n个信封中，求全部装错的概率是多少？ n个人，n顶帽子，全部戴错的概率是多少？当n10时,概率都近似等于0.3679 例6 毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过舞。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙子与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。,例7 设M1,M2,和N1,N2,是集合

6、S的子集的两个序列，对ij，i,j=1,2,，有Ni Nj=。 令试证：,第二章 映射习题(1) 讨论下列映射的性质 例1 X=1,2,3,4,Y=a,b,c,d,e,f(1)=a,f(2)=a,f(3)=c,f(4)=d。 例2 令N=1,2,3,，S:NN，则 (1)nN,S(n)=n+1,称为自然数集N上的后继函数。 (2)S(1)=1,nN,S(n)=n-1,n2,称为自然数集N 上的前仆函数。 例3 令为全体偶自然数之集，f:EN，2mE，f(2m)=m。 例4设为整数的有限集，定义集合X-X=x-x|x,x X。试证：若A,B1,2,n且|A|B|2n-1, n1，则(A-A)(B

7、-B)中有一个正整数。,第二章 映射 2 抽屉原理 例1(1)一年365天，今有366个人，则至少有两个人生日相同。(2)抽屉里有10双手套，从中取11只出来，则其中至少有两只是完整配对的。(3) 某次会议有n位代表参加，每一位代表至少认识其余n-1位中的一位，则在这n位代表中，至少有两位认识的人数相等。 例2 在一个边为1的正方形内（包括边界），任意地画七个点，则其中必有三个点，以它们为顶点所组成的三角形面积小于1/6。 例3 证明，从1,2,2n中，任选n+1个数，则在这n+1个数中必有两个数，使得其中一个能整除另一个。,例4 坐标上有五个整数点，则存在有两个点的连线的中点一定是整数点。

8、例5 证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。 抽屉原理也称为鸽巢原理、重叠原理。这个原理十分简单，但若用得好却会得到意想不到的有趣结论。 但也应当注意，抽屉原理并未告诉我们怎样实际地去寻找含有两个或更多个物体的那个抽屉，而只是肯定了确有这样的抽屉。,例6 已知m个整数a1，a2，am，试证：存在两个整数k,l,0kjm，使得ak+1+ak+2+al能被m整除。 例7证明：对任意正整数N，存在N的一个倍数，使得它仅由数字0和7组成。（例如N3,有2593777；N4,有192547700；N5,有14570；N6,有129567770等）。 例8 证明：在任

9、意个人中，或有3个人相互认识，或有3个人相互不认识。 例9 5个整数中必有3个整数其和能被3整除。 例10 设a1,a2,an为1，2，3，n的任一排列,若n是奇数且(a1-1)(a2-2)(an-n)0，则乘积为偶数。,上面的例2、例8使用的鸽巢原理实际上是鸽巢原理的一种推广形式，称为“平均值原理”，即若把m只物体放到n个抽屉里，则一定存在某一个抽屉，它里面至少有(m-1)/n+1个物体。这里x表示不大于x的最大整数。 2.2 抽屉原理强形式 抽屉原理强形式:设m1,m2,mn都是正整数,若把m1+m2+mn-n+1个物体放到n个抽屉里,则或第一个抽屉里至少有m1个物体,或第二个抽屉里至少有

10、m2个物体,或第n个抽屉里至少有mn个物体。 说明:当m1=m2=mn=2时，m1+m2+mn-n+1=n+1。抽屉原理是强形式的一种特殊情况。,推论1 若有m个物体放到n个抽屉里，则一定存在某一个抽屉，它里面至少有(m-1)/n+1个物体。 推论2 若把n(m-1)+1个物体放进n个抽屉里，则一定存在某一个抽屉，它里面至少有m个物体。此推论是强形式中，当m1=m2=mn=m 时的特殊情况。 推论3 若m1,m2,mn是n个正整数，且(m1+m2+mn)/nr-1，则m1,m2,mn中至少有一个大于或等于 r 。,鸽巢原理强形式例题 例1 一个人步行了十小时，共走45公里，已知他第一个小时走了

11、6公里，而最后一小时只走了3公里，证明一定存在连续的两个小时，在这两个小时之内至少走了9公里。 例2 一个园环等分36段，将36个数字1,2,36任意地写在每一段上，使每一段上恰有一个数字，证明：一定存在连续的三段，在这三段上的数字之和至少为56。,例1设A,B,C是任意三个集合，则(AB)C=A(BC)CA。 例2设V是任一集合，证明：S,T,W2V有STW当且仅当STSW且SW。例3设A,B,C是三个任意集合，化简例4设A,B是两个集合,B,试证:若AB=BB,则A=B。 例5设为整数的有限集，定义集合 X-X=x-x|x,xX。试证：若A,B1,2,n且|A|B|2n-1,n1，则(A-

12、A)(B-B)中有一个正整数。,第二章 映射习题课（2） 例1 令X=x1,x2,xm,Y=y1,y2,yn,问： (1)有多少个不同的由X到Y的关系？ (2)有多少个不同的由X到Y的映射？ (3)有多少个不同的由X到Y的双射？ (4)有多少个不同的从X到Y的单射？ 例2 设f:XY，A,BX,证明: (1)f(AB)=f(A)f(B); (2)f(AB)f(A)f(B); (3)f(A)f(B)f(AB);(4)f(A)f(B)f(AB)。,例3设X是一个有限集合，从X到X的部分映射有多少？ 例4 设u1,u2,umn+1是一个两两不相同的整数构成的数列，则必有长至少为n1的递增子序列或有长

13、至少为m1的递减子序列。 例5设N=1,2,3,试构造两个映射f,g:NN，使得fg=IN，但gfIN。 例6设N=1,2,3,试构造两个映射f,g:NN，使得gf=IN，但fgIN。,例9 设f:XY，证明： (1)f是单射F2X，f1(f(F)=F； (2)f是满射E2Y，f(f1(E)=E。 例10 设f:XY，X=m，Y=n，则 (1)若f是左可逆的，则f有多少个左逆映射？ (2)若f是右可逆的，则f有多少个右逆映射？ 例11 设f:XY，则 (1)若存在唯一的一个映射g:YX,使得gf=IX,则f是可逆的吗？ (2)若存在唯一的一个映射g:YX,使得fg=IY,则f是可逆的吗？,习题

14、（2） 例1 设f:XY，AX，BY，证明： f(f-1(B)A)=Bf(A)。 例2 设f:AB,证明:TB，有f(f-1(T)=Tf(A)。 例3 设f:XY，证明：(1)f是单射F2X，f1(f(F)=F；(2)f是满射E2Y，f(f1(E)=E。 例4 设有映射f:AB,HA，令HC是H对A中的余集,当f分别是单射和满射时，给出f(HC)和(f(H)C之间的关系，并给予证明。 例5 设f:NNN,f(x,y)=xy。求f(N1),f-1(0)，并说明是否是单射、满射或双射？ 例6 设X是一个无穷集合，f:XX。证明:存在X的一个真子集E，使得f(E)E。,例7(1)设X=1,2,Y=a,b,求X到Y满射的个数; (2)设X=1,2,3,4,5,Y=a,b,求X到Y的满射的个数; (3)设X=1,2,m,Y=a,b，求X到Y的满射的个数; (4)设X=1,2,m,Y=y1,y2,yn,mn,若f:XY，求X到Y的满射的个数。 例8 设X,Y,Z是三个非空集合，Z2。证明:f:XY 是满射当且仅当不存在从Y到Z的映射g1和g2，使得 g1g2，但g1f=g2f。 例9 设X,Y,Z是三个非空集合,X2。证明:f:XY 是单射当且仅当不存在从Z到X的映射g1和g2，使得 g1g2，但fg1=fg2。,