§3.6集合的等势与基数习题3.61.判断下列集合是否为无限可数集

§3.6 集合的等势与基数

习题3.6

1. 判断下列集合是否为无限可数集，若是，给出自然数集合和该集合之间的一个双射函数。

（1）偶整数。 （2）0和0.5之间的实数。

（3）是7的倍数的整数。 （4）不能被3整除的整数。

（5）能被5整除但不能被7整除的整数。 （6）十进制表示中只含数字1的实数。

（7）十进制表示中只含数字1或9的实数。

解（5）、（6）、（7）略

A＝{偶整数}是无限可数集，其中的一个双射函数为 （1）

f：NA， f(x)2x

A＝（0，0.5）不是无限可数集。 （2）

A＝{是7的倍数的整数}是无限可数集，其中的一个双射函数为 （3）

f：NA， f(x)7x

A＝{不能被3整除的整数}是无限可数集，其中的一个双射函数为 （4）

11224455778810100123456 710111213

2. 若A为不可数集合而B是可数集合，AB必定是不可数集合吗？若是请给予证明，若不是，请举出反例。

解 略

A，A，，A，12n3. 设是可列集，证明n1列集。

An也是可列集。即可列个可列集的并仍是可

证明 因为A1，A2，，An，是可列集，所以不妨假设

A1{a11，a12，，a1n，}

A2{a21，a22，，a2n，}

A3{a31，a32，，a3n，}



这样，类似于课本上NN~N的证明，

An1n中的元素aij可以按下列方式进行排列：先排

ij2的元素，再排ij3的元素，然后是ij4的元素，等等，这样集合

An1n{a11,a12,a21,a31,a22,a13,}也是可列集。

A，A，，A，12n4. 设是连续集，证明n1续集。

An也是连续集。即可列个连续集的并仍是连

解 略

5. 设A、B、C、D是4个集合，且A~C，B~D，证明AB~CD。

解 略

6. 证明所有位串组成的集合是可数的。

解 略

7. 证明用特定的一种程序语言写的计算机程序组成的集合是可数的。[提示：可以认为以某种程序语言写的计算机程序是由有限字母集中字母组成的符号串。]

证明 对于有限的字母表，只有有限多个长度为n的位串，其中n为正整数，这样，根据习题3知，有限字母表上长度不超过给定正整数的位串只有有限多个。由于用特定程序语言写的计算机程序集合是某个有限字母表上的所有位串之集合的子集，所以作为可数集合的子集，程序集合也是可数的。

1，2，3，4，5，6，7，8，9}的函数组成的集合是不可数的。8. 证明从正整数集合到集合{0，[提示：找一个0到1之间的实数集合到这个函数组成的集合的一个子集的双射函数。为此

d1d2dn对应函数f，而f(n)dn。] 可以让实数0.解 略

9. 如果有计算机程序能计算函数的值，就说这一函数是可计算的。利用上面的习题7和习题8证明存在不可计算的函数。

解 略

1}的10. 设A为任意集合，则P(A){0，1}，这里{0，1}是所有从集合A到二值集合{0，AΨ{0，1}P(A)B函数组成的集合。[提示：中的任意元素B与B的特征函数一一对应。]

AA解 略

11. 证明20，即证明无限可数集的幂集是连续集。[提示：结合习题8的提示和习

题10的提示进行证明。]

解 略