可数集

集合若是有限的，或能把元素排成 $a_1,a_2,\dots$ 的序列而不遗漏，就称为至多可数；无限且能这样排列的集合称可数无限。等价地，可数无限集能与正整数集建立双射。下标不要求大小有序，要求的是每个元素在某个有限位置出现。

整数的排列

整数看似在正、负两个方向都没有尽头，仍可排列为 $$0,1,-1,2,-2,3,-3,\dots .$$ 绝对值为 $k$ 的两个整数在第 $2k$ 附近出现，因此每个整数最终会被列出。这说明“向两边无限延伸”不等于不可数。

有理数也能列成一列

每个有理数可写作 $p/q$，其中 $p\in \mathbb{Z}$、$q\in \mathbb{N}$ 且 $q>0$。按 $|p|+q=1,2,3,\dots$ 逐层扫描整数对；每一层只有有限对，所以能依次处理。遇到 $2/2$ 与 $1/1$ 之类重复表示，只保留约分后的第一次出现。任意 $p/q$ 对应有限的层数，故不会遗漏。由此得到 $\mathbb{Q}$ 可数。

稠密与可数并不冲突

任意两个不同实数之间都有有理数，但这不使有理数“多到不可列”。稠密讨论的是位置分布；可数讨论的是能否编号。反过来，实数区间 $(0,1)$ 无法完整列成序列，见不可数集与对角线论证。区分这两个问题，才能理解“每段都有分数”与“还有列不完的实数”为什么可以同时成立。

参考资料

• MIT，Mathematics for Computer Science，Countability 章节。
• MIT 18.100A Fall 2020，实分析讲义。
• 继续阅读：双射、不可数集、有理数的稠密性。