离散数学第二版邓辉文编著第一章第六节习题答案_离散数学习题6答案

离散数学第二版邓辉文编著第一章第六节习题答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学习题6答案”。

1.6 集合对等

习题1.6 1.证明: 任意无限集合均存在可数子集.证 设A是无限集合，取a0A，则A{a0}是无限集合.取a1A，则A{a0,a1}是无限集合.一直下去，即可得到无限集合A的可数子集{a0,a1,...an,...}.2.证明:(0,1)~[0,1].证 由于(0,1)是无限集合，而任意无限集合均存在可数子集，设{a0,a1,...an,...}是(0,1)开区间的一个可数子集合，令f:(0,1)[0,1]，满足下面的条件

f(a0)0,f(a1)1, f(ai)ai2,i2;f(x)x,x{a0,a1,...,an,...}.显然，f是(0,1)到[0, 1]的一个双射.故(0,1)~[0,1].3.证明: [0,1]~[a,b],ab.证 令f:[0,1][a,b]，f(x)a(ba)x，容易证明f是一个双射，进而[0,1]~[a,b].4.有理数集合Q是可数集合.证 由于正有理数集合Q+ = nm,nN,m0,m与n互素，令mf:QNN，nf(m,n)，m则f是单射，所以|Q+| |NN|.由于N~NN，于是|Q+| |N|0.而Q+是无限集合，所以|Q+| |N|0.于是|Q+| = 0.所以正有理数集合Q+是可数集合.显然Q+与所有负有理数集合Q-对等，而Q = Q+Q-{0}，所有Q是可数集合.5.证明: 全体无理数组成的集合R – Q与R有相同的基数.证 在全体无理数集合R – Q中选取可数子集{a0,a1,...an,...}，因为Q可数，设Q = {b0,b1,...bn,...}.构造映射f:RQR如下

f(a2i)ai,f(a2i1)bi,i0,1,2,...； f(x)x,x{a0,a1,...,an,...}.则f:RQR是双射，所以R – Q与R有相同的基数.6.对于任意集合A，P(A)是A的幂集，证明: |A||P(A)|.证 令g:AP(A),g(x){x}，则g是A到P(A)的单射，所以|A||P(A)|.假设|A||P(A)|，则存在A到P(A)的双射f.令

S{x|xf(x)}，则SA.因为f是A到P(A)的双射，必存在yA是得f(y)S.考虑是否yS.由于

ySy{x|xf(x)}yf(y)yS，这是一个矛盾.于是|A||P(A)|不成立，因此有|A||P(A)|.