可列集

如果一个无限集中的元素可以按某种规律排成一个序列，或者说，可以对这个集合的元素标号表示为

{a1,a2,a3, ... ,an, ...},

则称其为可列集。1

定义如果一个集合与正整数集合之间存在一一对应，则这个集合称为可列集（或可数集）； 也就是说， 存在一个从该集合到正整数集合的双射（也称可逆映射）。

种类自然数集、有理数集、代数数集都是可列集。

实数集、复数集、直线点集、 平面点集都是不可列集（或不可数集）。

可列集是最小的无限集； 它的幂集是不可数集--和实数集存在一一对应（也称同势）。 所谓幂集， 就是原集合中所有的子集（包括全集和空集）构成的集族。

举例证明证明：有理数集Q是可列集

证 由于区间（−∞,+∞）可以表示为可列个区间（n,n+1](n∈Z)的并，我们只须证明区间（0,1]中的有理数是可列集即可。

由于区间（0,1]中的有理数可惟一地表示为既约分数q/p，其中p∈N+，q∈N+，q≤p，并且p，q互质。我们按下列方式排列这些有理数：

分母p=1的既约分数只有一个： x11=1;

分母p=2的既约分数也只有一个：x21 =1/2；

分母p=3的既约分数有两个： x31=1/3, x32 =2/3；

分母p=4的既约分数也只有两个：x41=1/4，x42=3/4；

... ...

一般地，分母p=n的既约分数至多不超过n-1个，可将它们记为xn1，xn2，... ，xnk(n)，其中k（n）≤n。

于是区间（0,1]中的有理数全体可以排成

x11，x21，x31，x32，x41，x42，... ，xn1，xn2，... ，xnk(n)，... 。

这就证明了有理数Q是可列集。

可以证明，可列集有下列重要性质：

1、 有限个可列集的并是可列集。

2、 可列个可列集的并是可列集。

3、 任何可列集的的无穷子集是可列集。

4、 任何无穷集都包含一个可列的真子集。

5、 一个无穷集并上一个可列集还与其自身等势 。

6、 可列集的幂集与实数集等势。1

猜想和悖论康托第一个认真研究了无限集合， 分清了可列集和不可数集的区别， 并用对角线法证明了实数集不是可列集。此外，康托指出了幂集的势总是严格大于原集合。由此结论导致了康托猜想（即连续统假设）和康托悖论。

康托猜想不存在一个集合， 它的势严格大于可列集的势， 同时严格小于实数集的势。

逻辑学家歌德尔证明了这个连续统假设是不能被证明的，也不能被证伪--就是说不能从现有的数学公理体系推演出该结论或者否定该结论。

康托悖论考虑所有的集合组成的最大的集族， 这个集族的幂集当然也是集合， 所以本身也是该集合的一部分， 从而它的势应该不超过原集合的势；但是另一方面， 幂集的势又严格大于原集合的势， 从而导致矛盾。

罗素首先意识到集合的概念存在问题。 他提出所谓的类型论， 指出有一类“集合”并不是真正的集合， 而是所谓的“类”，集合本身是不能包含自身的；“类”却可以。 从这个角度出发，就可以解释上述的悖论。

等势概念**定义：**集合A与集合B等势(等基数)，当且仅当，A与B之间存在双射（一一对应、可逆映射）。

在此意义下，刻画了两个无穷集合比较“多少”的一种办法。但这里的“多少”概念只是一种直观的解释，已经和有限集合比较多少的情况发生了变化。

在有限集合中，一个集合不可能与其真子集等势。但无限集合的比较，则不同。比如，整数集和偶数集之间，可以通过双射f(n)=2n 建立一一对应的关系。所以整数集和偶数集是等势的，虽然偶数集是整数集的真子集。集合论认为，这种与其某一真子集等势的性质，恰好反映了无穷集合的本质，反映出了有限集和无穷集之间的一个重大区别。

康托尔对角线证明实数区间[0,1]中所有的实数组成的集合是不可列集。

其实只要证明(0,1]区间的实数集是不可列的。反证法，如果它是可列的，说明其中所有的实数均可排列成一数列t1,t2,...,tn,...，只有这样，它才能一一对应于自然数集。好，这时我们将(0,1]中的实数用十进制的无限小数表示：

t1=0.t11t12t13...t1n...

t2=0.t21t22t23...t2n...

...

tm=0. tm1tm2tm3...tmn...

...

其中所有的tij都是0～9这十个数字中的某一个。

但是现在我们可以构造一个小数a=0.a1a2a3...ak...，任意的ai也都是0～9这十个数字中的某一个，但我们让每个ai都不等于上述实数列中的tii，也就是a的第i位的数字跟ti的第i个数字不同。这是可行的，因为我们用的是十进制小数，不同于tii的还剩9个不同的数字可供ai选择。

当我们构造好了这样的一个小数之后，我们发现它实际上跟上述小数列中的任何一个都不相等。这就造成了逻辑上的矛盾，你说已经把所有小数都列出来了，但是我却发现至少我构造的这个小数，你还没有罗列出来。就算你亡羊补牢，把我这个也补充进去，但是我还是可以根据同样规则又构造出另一个。所以，只能说明实数是无法跟可列集形成一一对应的，也就是前面的假设是错误的。

因此[0,1]区间的实数不是可列集。同样，取掉0，1两个数之后的(0,1)区间的实数也不是可列集。

本词条内容贡献者为:

朱坤平 - 副教授 - 华东理工大学