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

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)|.