《离散数学》习题一参考答案 第一节 集合的基数 1.证明两个可数集的并是可数集。 证明：设A，B是两可数集，A{a1,a2,a3,,an,}，B{b1,b2,b3,,bn,} ABNf:ai2i1 ，f是一一对应关系，所以|A∪B|=|N|=0。 b2jj2．证明有限可数集的并是可数集 证：设A1,A2,A3Ak是有限个可数集，Ai(ai1,ai2,ai3,ain,),i1,2,3,,k kkAAiN，f是一一对应关系，所以|A|=|Ai|=|N|=0。 f:i1i1aijj(k1)i3.证明可数个可数集的并是可数集。 证：设A1,A2,A3Ak是无限个可数集，Ai(ai1,ai2,ai3,ain,),i1,2,3, AAiNi1f:， 1aij(ij1)(ij2)i2所以f是一一对应关系，所以|A|=|A|=|N|=。 i0i1 4.证明整系数多项式所构成的集合是可数集。 证明：设整系数n次多项式的全体记为 An{a0xna1xn1an1xan|aiZ} 则整系数多项式所构成的集合AAn； N1由于xk的系数ak是整数，那么所有xk的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得An是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合AAn也是可数集。 N15.证明不存在与自己的真子集等势的有限集合. 证明：设集合A 是有限集，则|A|=n，若B是A的真子集，则|B|≤|A|=n，A-B≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B）∪B，（A-B）B=φ，所以，，就是|A|＞|B|，即得结论。 6．证明正有理数集合是可数集，从而能证明有理数集是可数集。 m证明：因为Q{|m,nN}，是正分数集， nn设Ai{|nN},i1,2,3,4,,m}，Ai是可数集，并QAi ii1由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数集。 有理数集Q=Q{0}Q，由可数集性质1，2，马上可得有理数集是可数集。 7．A、B为无限集，试说明下面的集合是否是无限集。 （1）A∪B （2）A∩B；（3）A－B；（4）A×B 答：（1）A∪B是无限集，由可数集性质（2）可得。 （2）A∩B不一定是无限集，若A∩B=φ，则|A∩B|=0； （3）A－B不一定是无限集，若A=B，则A－B=φ， （4）A×B是无限集。相当于无限个无限集的并是无限集。 8．已知A{n7|nN}，B{n109|nN}，求 （1）A，B的基数；（2）A∪B，A∩B的基数。 A[n7|nN)N解：（1）f:，f是一一对应关系，所以|A|=N|=0 7nnB[n109|nN)Nf:，f是一一对应关系，所以|B|=N|=0 109nn（2）有可数集性质（2）可得A∪B是可数集，既| A∪B|=N|=0 因为(n7)109(n109)7AB，所以A∩B≠φ AB[(n109)7|nN)N，f是一一对应关系，所以| A∩B|=N|=0 f:1097(n)n9.设A为任意集合，证明P（A）与{0，1} A等势，其中{0，1} A为A到{0，1}的全体函数。 1xA解：若fA(x)是A到{0，1}上的一个集函数，则fA(x) 0xA f：ρ（A）→{0,1} B →fB(x) 所以f是一一对应的，即ρ（A）与{0,1}等势。 AA 本文来源：https://www.wddqw.com/doc/8252b155c5da50e2524d7f55.html