《集合论与图论》课堂练习1 1

《《集合论与图论》课堂练习1 1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《集合论与图论》课堂练习1（2012年10月31日13:30-15:10复旦大学计算机学院2011级）学号姓名成绩一、填空题（30分，每格2分）1．设A为一个集合，若，则A为有限集。若，则称A为可列集。2．已知集合A和B，且

2、A

3、=n，

4、B

5、=m，由A到B有个不同的关系，有个不同的函数。若n=5,则A上有个全序关系。若n=m=3,则从A到B可产生个不同的双射。3．集合A的递归（归纳）定义由三部分组成：（1）___;（2）__;（3）___。4．设A、B为集合，则AÇB=B的充要条件是：；AÅB=B的充要条件是_____。5．函数f:N´N®N，f((x,y))=x2+y2。f

6、-1({0})=。6.函数f:A®B可逆的充要条件是。7.A,B是集合，P(A),P(B)为其幂集，且AÇB=Æ，则P(A)ÇP(B)=。8.A,B是集合，À0=

7、B

8、<

9、A

10、=À，则

11、A-B

12、=。二、是非判断题（24分，每题6分，其中判断3分，论述3分）1．设A,B,C,D是任意集合；f是从A到B的双射，g是从C到D的双射。h:4A´C®B´D，其中对于任意的(a,c)ÎA´C,h((a,c))=(f(a),g(c))成立。则h是双射。（）2．设R是A上的二元关系，则t(s(R))=s(t(R))。（）3．设A,B是集合，若存在A到B的满射，则

13、B

14、£

15、A

16、。（）4．设A是

17、集合，R是A的幂集P(A)上的二元关系，对所有的S,TÎP(A)，(S,T)ÎR。R是偏序关系当且仅当

18、S

19、£

20、T

21、。（）4三、综合题（46分）1．设有双射f:A®B，试构造从P(A)到P(B)的一个双射，并证明之。（15分，给出双射5分，证明10分）2．某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为1，2，3，4，……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1，2，3，4，…)，称为可列集。　　有一天，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老板于是引用“旅馆公理”说：“满了就是满了，非常

22、对不起！”。正好这时候，聪明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬一下，从这间房搬到下一间”。于是1号房间的客人搬到2号房间，2号房间的客人搬到3号房间……依此类推。最后1号房间空出来，请这位迟到的客人住下了。　　第二天，希尔伯特旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数无穷多位代表一定要住，这又把旅馆经理难住了。老板的女儿再一次来解围，她说：“您让1号房间客人搬到2号，2号房间客人搬到4号……，k号房间客人搬到2k号，这样，1号，3号，5号，……房间就都空出来了，代表团的代表都能住下了。”　　第三天，这个代表团每位代表又出

23、新花招，他们想每个人占可数无穷多间房来安排他们的亲戚朋友，这回不仅把老板难住了，连老板的女儿也被难住了。(1)现在您担任希尔伯特旅馆的客房经理，您准备采取什么方法解决当前的住宿问题？(2)后来老板的女儿进了大学数学系。有一天，康托尔教授来上课，他问老板的女儿：“要是区间[0，1]上每一点都占一个房间，是不是还能安排？”4也请您回答康托尔教授的这一问题，并论证。（15分，第1小题6分，第2小题9分，其中论证为6分）3．R是集合A上的等价关系，

24、A

25、=n，

26、R

27、=s。对于A关于R的商集A/R，

28、A/R

29、=r。证明：rs³n2。（16分）4