无限集合在数学中时时出现、自然数、完全平方数、素数、整数、有理数、实数等等都构成无限集合。人们时常自然地想要比较这些集合的大小，人们直觉地感觉自然数的集合“小于”整数的集合（因为后者还包含了负数），但是比完全平方数的集合就大得多（因为一个典型的大数不大可能是完全平方数）。但是我们能在精确的意义下比较它们的大小吗？

一个明显的解决这个问题的方法建立在我们关于有限集合的直觉上。若A和B是两个有限集合，有两个方法来比较它们的大小。一是去数它们的元素的个数，于是会得到两个非负的整数m和n、然后看一看，是m<n。还是m=n，还是m>n。但是还有另一个重要的方法，不需要确知A或B的大小，这就是把A的元素和B的元素配对，直到有一个集合的元素被取尽为止，元素先被取尽的集合就是较小的集合，如果总是“打成平手”，这两个集合就是一样大小。

第二个方法（配对）稍作修改以后，也可以用于无限集合。如果两个集合之间有一个一一对应，就说它们的大小相同。我们将会看到，这是一个重要而又有用的定义，虽然它有一些推论会让我们一开始感到有点怪。例如，在自然数集合和完全平方数集合之间有一个显然的一一对应：对每一个 n，让n^2与之相应。这样，按照定义，平方数和自然数应该是“一样多”。类似于此，素数和自然数也是一样多，对于n，有第n个素数与它对应。

关于整数Z又如何？似乎它应该是自然数N的两倍大，但是我们又能找到二者之间的一一对应。只需把整数列表如下：0，1，-1，2，-2，3，-3，…，然后把它们与自然数配对，方法是，1配0，2配1，3配-1，4配2，5配-2，等等。

如果一个无限集合与自然数集合有相同的大小，就称为可数集合。正如上面的例子所说明的，这和说这个集合的元素可以列表是完全一样的，实际上，如果把一个集合的元素列表为 a1，a2，a3，……，则我们的一一对应就是n与an对应。值得注意的是，当然有一些我们想用的列表是不行的，例如，可以试着把Z列表为-3，-2，-1，0、1，2，3，4……想一想为什么不行？

因为这个列表实际上会漏掉一些负数（如 -4、-5 等）。所以，这种方法不能建立整数集 Z 和自然数集的一一对应关系。为了解决这个问题，我们可以用另一种方法来列举整数集 Z，以便确保涵盖所有的正数和负数。一种有效的方法就是上面提到的0, 1, -1, 2, -2, 3, -3, 4, -4…

所以重要的是要认识到。当我们说一个集合是可数集合时，并不是我们想用的哪一个列表方法都能行，甚至也不是说，那些明显的列表方法是行的，我们只是说，集合的元素有某种列表的方法。这与有限集合完全不同，对于有限集合，如果应用某一种配对的方法有一个集合留下了一些元素，我们就知道，这两个集合之间不会有一一对应，上面出现的那些“奇怪的"推论主要是来自于此。

现在我们已经确定了某些看来比N小，或者比N大的集合，实际上是可数集合，那么我们再转到一个看起来"大得多"的集合，即有理数集合Q。我们怎么能够希望把所有的有理数列成一个表呢？归根结底，在任意两个有理数之间可以找到无穷多个其他有理数，所以当想去把它们列成一个表的时候，很难不漏掉哪一个，然而，尽管看起来很值得注意，确实可以把有理数列成一个表，关键的思想是在列表的时候，要使这个有理数的分数表示的分子和分母二者（按绝对值）都小于某个定数k。这样列表就容易了，因为符合这个条件的有理数只有有限多个。所以，我们就按下面次序进行：首先排列分子分母都最多为1的有理数，再排分子分母最多为2的，仿此以往（注意不要重复任意的数，例如排列了1/2以后，就不要再排2/4，3/6了）。这就会给出例如下面的列表：

我们可以用同样的思想来排列看起来甚至更大的集合，例如代数数集合（即所有满足整数系数的多项式方程的实数）。实际上，注意到每一个多项式方程只有有限多个根（这些根可以列成表）所以需要我们去做的就只是把多项式列成表（然后在每一个多项式里面依次列出所有的根就行了）。在把多项式列表的时候，又可以用上面的办法：对于每个定数d，排列那些次数不超过d，系数之模最多也为d而且还没有排列过的多项式。

基于以上的例子，可能会猜想，每一个无限集合都是可数的。但是康托的一个漂亮的论据，称为“对角线”方法的论证方法，说明实数集合是不可数的。设想实数集合有一个列表的方法：r_1，r_2，r_3，……。我们的目的是要证明这个列表不可能包含所有的实数，所以要造出一个不在这个表上的实数。怎样做这件事呢？把每一个 r_i都写成例如一个无穷十进小数，现在来造出一个实数s，它的小数点后的第一位数码要选得和ri的第一位数码不同。这就已经保证了s不可能等于r_1（为了避免递推地出现9等等，最好s的第一位数码连9和0也不要取）。然后，s的第二位要取一个与r_2的第二位不同的数码，这就保证了s也不可能等于r_2。像这样做下去，最后就得出一个不在所说的列表中的实数s，不论n是多少，s都不可能等于r_n，因为它们在小数点后的第n位不同！

当这样来确定一个对象时（如要选择s的各位数码那样），都可以采用上面的论证方法而有“无穷多个独立的选择要作”。例如，让我们用同样的思想来证明自然数集合N的子集合的个数是不可数的。假设我们能够把N的所有子集合列成一个表A_1、A_2，A_3，…。要定义N的一个新的子集合B，使它不等于任何一个A _n。把1放进B中，当且仅当1不在A_1中（这就保证了B不等于A_1）。把2放进B中，当且仅当2不在A_2中，如此等等。有趣的是，我们可以把这个集合B写下来：

这表明 B很像罗素悖论里的集合。

可数集合是“最小的”无限集合。然而实数集合绝非“最大的”无限集合。事实上，上面的论证说明任意一个集合X都不能与它自己的所有子集合的集合一一对应。所以，实数集合的所有子集合的集合“严格地大于”实数集合，等等。

可数性的概念是非常富有成果的，值得记在心上。例如，设我们想知道是否所有实数都是代数数，要想证明一个特定的实数真正是超越数而不是代数数这是一个很难的练习，但是上面的论证使得证明超越数的存在变成极为不足道的事情，事实上，实数集合是不可数的，而代数数的集合则是可数的。此外，这个论证还说明"绝大多数"实数都是超越数、代数数只占了实数的极小一部分。