1、集合论与图论课堂练习1集合论与图论课堂练习1 学号 姓名 成绩 一、 填空题（30分，每格2分）1设A为一个集合，若 A为有限集。若 ，则称A为可列集。2已知集合A和B，且|A|=n，|B|=m，由A到B有 个不同的关系，有 个不同的函数。若n =5, 则A上有 个全序关系。若n =m=3, 则从A到B 可产生 个不同的双射。3集合A的递归（归纳）定义由三部分组成：（1）_ _ _;（2）_ _ ;（3）_ _ _。4设A、B为集合，则AB=B的充要条件是： ； AB=B的充要条件是 _。5函数f:NNN，f(x, y)=x2+y2。f-1(0)= 。6. 函数f: A B可逆的充要条件是 。
2、7. A, B是集合，P(A), P(B)为其幂集，且AB=，则P(A)P(B) = 。8. A, B是集合，0=|B|A|=，则|A-B|= 。二、是非判断题（24分，每题6分，其中判断3分，论述3分）1设A, B, C, D是任意集合；f是从A到B的双射，g是从C到D的双射。h: ACBD，其中对于任意的(a, c)AC, h(a, c)=(f(a), g(c)成立。则h是双射。（ ）2设R是A上的二元关系，则t(s(R)=s(t(R)。（ ）3设A, B是集合，若存在A到B的满射，则|B|A|。（ ）4设A是集合，R是A的幂集P(A)上的二元关系，对所有的S, TP(A)，(S, T)R
3、。R是偏序关系当且仅当|S|T|。（）三、综合题（46分）1设有双射f: AB，试构造从P(A)到P(B)的一个双射，并证明之。（15分，给出双射5分，证明10分）2某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为1，2，3，4，我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1，2，3，4，)，称为可列集。 有一天，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老板于是引用“旅馆公理”说：“满了就是满了，非常对不起！”。正好这时候，聪明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬一下，从
4、这间房搬到下一间”。于是1号房间的客人搬到2号房间，2号房间的客人搬到3号房间依此类推。最后1号房间空出来，请这位迟到的客人住下了。 第二天，希尔伯特旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数无穷多位代表一定要住，这又把旅馆经理难住了。老板的女儿再一次来解围，她说：“您让1号房间客人搬到2号，2号房间客人搬到4号，k号房间客人搬到2k号，这样，1号，3号，5号，房间就都空出来了，代表团的代表都能住下了。” 第三天，这个代表团每位代表又出新花招，他们想每个人占可数无穷多间房来安排他们的亲戚朋友，这回不仅把老板难住了，连老板的女儿也被难住了。(1) 现在您担任希尔伯特旅馆的客房经理，您准备采取什么方法解决当前的住宿问题？ (2) 后来老板的女儿进了大学数学系。有一天，康托尔教授来上课，他问老板的女儿：“要是区间0，1上每一点都占一个房间，是不是还能安排？”也请您回答康托尔教授的这一问题，并论证。（15分，第1小题6分，第2小题9分，其中论证为6分）3R是集合A上的等价关系，|A|=n，|R|=s。对于A关于R的商集A/R，|A/R|=r。证明：rsn2。（16分）4 / 4
