如果一个无限集中的元素可按某种规律排成一个序列，则称其为可列集。 每个无限集必包含可列子集，但无限集并非一定是可列集。

定义

种类

重要性质

猜想和悖论(康托猜想 康托悖论)

等势（等基数）的相关概念

其它定义

康托尔对角线证明

定义

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

种类

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

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

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

重要性质

这些性质是在我们承认选择公理得出的)：

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

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

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

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

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

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

猜想和悖论

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

康托猜想

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

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

康托悖论

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

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

详见百科词条：基数、集合论、双射、一一对应、可逆映射、选择公理。

等势（等基数）的相关概念

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

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

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

反驳：对等的方法，只能在有限集比较中有效。扩展到无限集是不可信的。

例：“问：某班学生人数与教室的凳子数哪个多？最笨但也最显然的方法是规定每个学生都去坐在凳子上，而且一个学生只能坐一张凳子。最后，如果有学生没坐到凳子，那么便是学生多。如果最后有凳子空着，那么便是凳子多。”

如果是有限数量，可以用一对一的方法比较，无限数量，不行。

假设来个副校长，要求每两个学生坐一个凳子，然后他检查了教室一，教室2，教室三......他看到的每个教室都是如此，后面的教室他认为不用检查了（或根本不可能检查完——无穷的概念），于是他宣布，本学校凳子数量，正好是学生数量的一半。

第二天，又来个副校长，要求每个学生坐一个凳子，然后他检查了教室一，教室2，教室三......他看到的每个教室都是如此，后面的教室他认为不用检查了（或根本不可能检查完——无穷的概念），于是他宣布，本学校凳子数量，正好等于学生数量。

两位自以为是的校长都有可能是对的，也可能是错的，方法不对。

在有限集的比较过程中，关键不在建立了怎样的对应关系，关键在于我们要比较到最后，至少一个集合结束了，而另一个集合中元素数量已经超过对比集合数量，而且还没结束，我们才能证明一个集合建立的对应关系比另一个集合数量多。

自然数集中可以抽出偶数集，跟偶数集完全一一对应，而自然数集还有剩余元素，因此我们可以得到结论：自然数集比偶数集多。

其它定义

另一个定义，以区别可数集

可列和可数在英文里是一个词：countable，这是以前科学不够发达，不需要进行区分时的结果。

而现在我们需要进行概念区分，因此按字面意思，将“可列”理解为“可以写出”；“可数”理解为“可以记数”。在下面的论述中，分这样两个概念讨论。

我们无法写出一个最大的自然数，因此自然数全体是不可写全的，任何无限集，都是不可写全的。(不可列)

如果有一些数，位数多的我们承认有生之年无法完全比较，而在可比较的范围内它们又一样，这样我们在数元素个数时，不知道它们该算一个元素还是多个元素，这种情况，称为不可记数。

从定义可以看出，不可写全的数，如果我们发现它的一部分，和集合中的其它元素都不一样，我们就知道它是一个独立元素，就可以记数。而不可记数的数，我们可能可以知道它的数量范围（最大数量每个算一个元素，最小数量认为只有一个元素），或者也可以知道它们都是可写的。因此这两个概念是有交叉而互不影响的。

无理数除了能用有理数表示的和可以定义的，都是不可列的

集合比较的等势概念，并非统一公认的，很多数学家对此进行了质疑。康托尔对实数集不是可数集的证明，也是被质疑的证明。

康托尔对角线证明

现在来证明实数区间[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，也就是让第i位的数字跟数列中第i行第i个数字不同。这是可行的，因为我们用的是十进制小数，还剩下9个不同数字可供选择呢。

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

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

反驳：无限集都是不可写全的，比如跟本不能写出一个(0,1)之间小数位最长的有理数，因此本证明的假设条件不成立，其它一切都无效。除非新构造的不是实数，否则只能证明假设将所有实数列出的假设不成立。所以康托尔对角线证明法不成立。而事实上，如果允许等势的概念存在，所有无穷集，都等势。总是你有一个元素，我就能拿出一个元素对应，同样也都可以你拿1个我拿2个，或相反，你拿2个我拿1个，都是能永远对应的，没有尽头。

这样一来，康托尔悖论不存在。

定理：无限集的元素是不可能全部写出来的，连最大元素数量的有限集，或与最大数量有限集差固定常数的集合，也是不可能写全的。最大元素数量有限集是无限趋近于无限集的，以致于没有手段进行判断。任何定义的无限集或有限集都需要满足此公理。

证明：假设最大有限集元素被全部写出，我们用自然数集的一部分与该集合的元素一一对应，再增加一个元素，该集合元素数量还是有限的，但元素数量比已写出的集合元素数量多1，证明原来假设写出的是数量最多的有限集不成立。所以最大元素数量的有限集，是不可能写全的。

定理：位数最多的非无限循环有理数是不可能被写出的，尽管它的定义是有有限位，但它是无限趋近于无理数的，以致于没有手段进行判断。

证明：假设位数最多的非无限循环有理数被写出，我们在这个数的最后再加一位，这个数还是有限位有理数，但位数比已写出有理数多一位，证明原来写出的不是位数最多的非无限循环有理数。所以位数最多的非无限循环有理数是不可能被写出的。