离散数学中证明以下两个集合是等势的

Question

（a）分母为2的幂的有理数的集合，既形式为m/n的有理数的集合，其中n=1，2，4，8或2的更高次幂。
（b）正整数集的所有有限子集以及余有限子集的集合，其中一个正整数的集合S是余有限子集的是指，不再S中的所有正整数组成的集合是有限的。
你好，谢谢你的回答，请问下：N+的势=有理数的势是什么根据 ,请问下你的意思是就是说（a）的势也是等于（c）的势。

Answer 1

对集合（a），一方面它是有理数集的子集；另一方面，建立正整数集N+到（a）的映射n=3^n/2^(2n)。由这两方面的论证可知，Z的势≤（a）的势≤有理数的势，但N+的势=有理数的势，由贝恩斯坦定理，（a）的势=N+的势
对集合（b），考虑（b）的子集（c）：正整数的所有有限子集组成的集合。考察如下引理：n维欧氏空间中的整点（此处整点指坐标均为正整数的点）集的势等于正整数的势。事实上，由于正有理数的势等于正整数的势，而有理数集可以跟平面上的整点建立一一对应关系，所以正整数的势等于2维欧氏空间的整点集的势；而对于3维空间的整点，我们可以先建立它的其中两个坐标跟正整数集的双射，从而建立3维空间的整点到2维空间的整点的双射，再建立2维空间整点到正整数集的双射，则建立了3维空间整点到正整数集的双射；而对于4维空间，先建立它的三个坐标到正整数集的双射……引理证毕。然后，我们建立(c)到二维空间整点的双射。对（c）中的正整数单点集（即｛1｝，｛2｝，｛18｝，……），建立它到Y坐标为1的二维空间直线上的整点的双射，由引理知，这是可以办到的；对（c）中的正整数双点集（即｛1，2｝，｛3，4｝，……），建立它到二维空间Y坐标为2的直线的整点的双射，由引理知，这也是可以办到的。更一般的，建立（c）中的正整数n点集到二维空间Y坐标为n的直线上的整点的双射，由引理知，这都是可以办到的，因为n点集一一对应于n维空间的整点，n维空间整点一一对应于正整数，正整数一一对应于直线上的整点。用这种办法，我们建立了（c）到二维空间整点的双射，再建立二维空间到正整数集的双射，我们就得到了（c）到正整数集的双射。再考虑（b）中的余有限子集的集合，每一个余有限子集对应于一个有限子集，这个有限子集就是余有限子集关于正整数集的补集，易知，这是一个一一对应关系。故（b）中的余有限子集的集合等势于正整数集。因为（b）=（b）中的余有限子集的集合∪（c），所以（b）等势于正整数集（这个应该明白吧？）。
综上，（a）的势=正整数集的势=（b）的势。

教科书上没有写吗？ 有很多证法。这是一种：
正有理数可以和平面上的整点建立一一对应关系，然后，按照这种顺序数点：（1，1），（1，2），（2，1），（1，3）（2，2），（3，1），（1，4），（2，3），（3，2），（4，1）……从几何上看，这相当于按照对角线方向数平面上的整点，每一个整点都会被数到，第n个被数到的点与n相对应，则得到了整点和正整数的一一对应关系。所以每一个有理数都对应一个正整数，所以N+的势=有理数的势。

楼下错了吧。正整数集的子集除了有限子集和余有限子集还有其他集合。例如:
奇正整数集。

没错，（a）的势也等于（c）的势。

Answer 2

解（a）设分母为2的幂的所有有理数构成的集合为A,有理数的集合为Q,显然A是Q的子集,且A是无穷集合,有理数的集合是可数集,其势为阿列夫零,一个可数集任意一个无穷集合也一定是可数集,故A的势也为阿列夫零。
（b）设A为正整数集所有有限子集构成的集合,A中的有限子集排列如下：
空集,{1},{2},{1,2},{3},{1,3},{4},{2,3}，......
(按子集元素之和从小到大排列,如果两个子集元素之和相等可按字典顺序决定先后)
由A中的有限子集可排列成一个序列,故A是可数集,其势为阿列夫零；
设B是由余有限子集构成的集合,故A∩B=空集,A∪B=正整数所有子集构成的集合C，即A∪B=正整数集合的幂集C,可数集的幂集的势恰等于连续统的势阿列夫,故C的势为阿列夫,从一个无穷集中去掉一个可数集不改变原来的势,故由B=C-A,可得B的势也为阿列夫.

如果余有限子集是有限集的补，那么所有这些集与有限集一一对应，也应是可数集，故B的势也是阿列夫零。

故(a)中的集合与(b)的集合A等势,同为阿列夫零;(a)中的集合的势与(b)的集合B的势也一样。

N+的势=有理数的势任何教学书上均有。