如果集合A和集合B之间存在一个一一映射(双射)，则称A和B等价。如果A和正整数集N等价，我们称A是可数的。换句话说，A可数的充要条件是A中的全体元素可以排列成a₁,a₂,…,a_n,..的形状。
根据这个定义，我们很容易得出整数集是可数的。因为我们可以构造如下正整数集到整数集的一一映射：

一个更有意思的命题是：
可数个可数集的并是可数集。
它的证明使用了经典的“对角线”法，这种方法被各种实变函数或集合论的书广泛采用。
证明：假设{A_m}是一列可数集，其中A_m={a_m1,a_m2,…}，把它们按如下顺序排列

可以按如图箭头所指的方向数U{A_m}中的元素，即把U{A_m}中元素排列成a₁₁,a₂₁,a₁₂,a₃₁,…}，于是U{A_m}是可数的，命题得证。
上述证明虽然已经说明U{A_m}可数，却没有给出它与正整数之间的一一映射关系。能否写出这个映射呢？
仔细观察发现，每个“对角线”上元素a_mn的下标之和m+n是一个常数。于是我们可以得到，按上图所示的排列方法，a_mn所处的位置为：

其中m+n≥3，a₁₁=1
这样我们就得到了U{A_m}到正整数集的一个一一映射：

这个命题的一个应用就是：有理数集是可数的。因为有理数可以被看作一个二元有序对(p,q)。但当我们用类似的方法排列有理数时，却发现了上述映射的一个致命错误：

(图片来自维基百科，它采用了“蛇状”的盘旋数法)
注意到图中红色的有理数，它们的分子和分母有公约数，这些数都已经被数过了。也就是说，我们上面构造的映射中忽略了a_mn中会有重复元素的情况。
我试图把重复的情况考虑进去，构建从正有理数到正整数的一一映射，但发现这时问题变得异常复杂，最终没能写出一个通式来。
那么，到底能不能找到这样的一个映射关系呢？ Read the rest of this entry »