《离散数学 Discrete Mathematics》课程教学资源（习题集）《集合论与图论》课堂练习1-07解答（2011级）.doc_大学文库

2 8. A, B 是集合，0=|B|<|A|=，则|A-B|=  。二、是非判断题（24 分，每题 6 分，其中判断 3 分，论述 3 分） 1．设 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 是双射。（真） /*武汉大学 1999 年试题*/ （1）证明 h 是满射。对于任意的(b, d)BD, 则 bB, dD, 因为 f 是从 A 到 B 的双射，g 是从 C 到 D 的双射，所以存在 aA, cC, 使得 f(a)= b, g(c)=d 成立；即存在(a, c)AC, 使得 h((a, c))=(f(a), g(c))= (b, d)成立。所以 h 是满射。（2）证明 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)。因为 f 是从 A 到 B 的双射，g 是从 C 到 D 的双射，所以 a1=a2, c1=c2。则(a1, c1)= (a2, c2)。所以 h 是内射。所以 h 是双射。 2．设 R 是 A 上的二元关系，则 t(s(R))=s(t(R))。（假）定理 2.12(3)。 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。（真）设存在 A 到 B 的满射 f，对任意 bB，存在 xA，f(a)=b。而由函数的定义，f(a1)=b1，f(a2)=b2，若 b1b2，则 a1a2。则|B||A|。 4．设 A 是集合，R 是 A 的幂集 P(A)上的二元关系，对所有的 S, TP(A)，(S, T)R。 R 是偏序关系当且仅当|S||T|。（假）对于 R 是 A 的幂集 P(A)上的二元关系来说，|S||T|，R 是偏序关系既不是充分条件，也不是必要条件。取 A={a, b}, S={a}, T={b}。因为|S||T|并且|T||S|，所以(S, T)R，并且(T, S)R；因为 ST，R 不是反对称的。所以 R 不是偏序关系。所以|S||T|不是充分条件。令 R={(, ), ({a}, {a}), ({b}, {b}), ({a, b}, {a, b}), ({a, b}, {a})}，R 是偏序关系。因为({a, b}, {a})R，|S||T|不成立。所以|S||T|不是必要条件。三、综合题（46 分） 1．设有双射 f: A→B，试构造从 P(A)到 P(B)的一个双射，并证明之。（15 分，给出双射 5 分，证明 10 分） /**构造性证明**/ 解：构造函数 g: P(A)→P(B)，xP(A)，令 g(x)=y，满足：ax，都有 f(a)y，且对于by，都有 f -1 (b)x，即 y 为仅由 x 中各元素在 f 作用下的象组成的集合。证明：g 是从 P(A)到 P(B)的一个双射

(1)g是从P(4到P/B)的一个满射。 h∈P(B,则彐x∈P(A),对于b曰,都有f(b)ax,即x为仅由y中各元素在f 作用下的象组成的集合。这样的x总是存在的。所以g是从P4)到P(B的一个满射。 (2)g是从P)到P(B的一个内射。 b,x2∈P(4),若g(x=g(x)=y,则hex1,fa=g(x)y,而g(xy)=y,所以fa ∈g(x),由g的定义,aex2,所以xgx2,同理xgx,所以x=x。所以g是从 P(4到PB的一个内射因此,g是从P4到P(B)的一个双射。 2.某一个市镇只有一家旅馆,这个旅馆与通常旅馆没有不同,只是房间数不是有限而是无穷多间,房间号码为1,2,3,4,……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1,2,3,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分) (1)定义双射 f: NXN-N(参考教材68页) (2)[0,1是不可列集(参考教材69页) 3.R是集合A上的等价关系,4=n,|R=。对于A关于R的商集AR,MA/R=r 证明:r22。(16分) *中国科学院计算所2000* 习题解析: R、A和AR三者的基数之间存在什么关系 1)R是集合A上的等价关系→R对A形成的一个划分,这个划分就是商集AR 2)取划分的一个块,若块中元素k个,则该块产生的有序对为k2个

3 （1）g 是从 P(A)到 P(B)的一个满射。 yP(B)，则xP(A) ，对于by，都有 f -1 (b)x，即 x 为仅由 y 中各元素在 f -1 作用下的象组成的集合。这样的 x 总是存在的。所以 g 是从 P(A)到 P(B)的一个满射。（2）g 是从 P(A)到 P(B)的一个内射。 x1, x2P(A)，若 g(x1)=g( x2)=y，则ax1，f(a)= g(x1)y，而 g( x2)=y，所以 f(a)  g( x2)，由 g 的定义，ax2，所以 x1x2，同理 x2x1，所以 x1=x2。所以 g 是从 P(A)到 P(B)的一个内射。因此，g 是从 P(A)到 P(B)的一个双射。 2．某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为 1，2，3，4，……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1，2，3，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 分） (1) 定义双射 f: NN→N (参考教材 68 页) (2) [0，1]是不可列集(参考教材 69 页) 3．R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。证明：rsn 2。（16 分） /*中国科学院计算所 2000*/ 习题解析： • R、A 和 A/R 三者的基数之间存在什么关系？ 1）R 是集合 A 上的等价关系 R 对 A 形成的一个划分，这个划分就是商集 A/R。 2）取划分的一个块，若块中元素 k 个，则该块产生的有序对为 k 2 个