可数集

可数集

countable set

能与自然数集N建立一一对应的集合。又称可列集。如果将可数集的每个元素标上与它对应的那个自然数记号，那么可数集的元素就可以按自然数的顺序排成一个无穷序列a1，a2，a3，…an，…。例如，全体正偶数的集合是一个可数集，全体正奇数的集合也是可数集，它们与自然数集可以建立如下的一一对应

自然数

123456……n……

正偶数

24681012……2n……

正奇数

1357911……2n－1……这说明一个可数集可以含有可数的真子集，反过来，两个可数集也可以并成一个可数集。

整数集与有理数集都是可数集。按照基数概念，能一一对应的两个集合的基数相同，于是有理数集、整数集、全体正偶数集等与自然数集有相同的基数。在这个意义上说，这些集合所含元素是“一样多”，但这些集合又是一个包含另一个作为真子集，所以又不同于有限集元素的“多少”概念。值得注意的是，并非所有的无穷集都是可数集，因为G.康托尔证明了实数集不是可数集，这样，实数集与自然数集有不同的基数，因而说明了无穷集所含元素数量的多少还有某种层次区别。

可数集的新定义，以区别可列集

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

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

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

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

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

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

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

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

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

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

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

详见百科词条：基数、集合论。