可数集

可数意味着每个对象都能获得一个有限的自然数号码。整张名单可以永不结束，但没有元素需要等到“无穷多个前项全部写完之后”才出现。这是证明枚举不遗漏时必须回答的问题。

二维表格尤其容易让直觉失灵。按行扫描 ${\mathbb{N}}^2$，第一行永远扫不完，第二行一个元素也轮不到；按坐标和扫描则不同。第 $s$ 层只有 $(s,0),(s-1,1),\dots ,(0,s)$，每层都能完成，而 $(m,n)$ 必定在第 $m+n$ 层出现。此前只有 $1+2+\cdots +(m+n)$ 个位置，所以等待步数确实有限；这个层内顺序也与下文按第二坐标编号的公式一致。把层数也纳入调度，便把二维无限表排进一维名单。

可数性只要求存在编号，不要求编号能由程序算出。它讨论对象数量；可计算枚举额外规定一个有效生成过程。即使目标是 $\mathbb{N}$ 的子集，这两层含义也不能互换。

整数、有理数与有限描述 ​

整数可以排成 $0,1,-1,2,-2,\dots$。有理数则把最简分数 $p/q$（$q>0$）按 $|p|+q$ 分层，每层先按分子排序，只保留互素的 $p,q$。任一有理数都在某个有限层中，每层也只有有限项，因此名单覆盖全部 $\mathbb{Q}$ 且没有重复。

更显式地，${\mathbb{N}}^2$ 上的编号

先跳过前面各层，再定位本层中的第 $n$ 个位置。前几层的编号分别是 $0$，$1,2$，$3,4,5$；由一个号码找到它所属的唯一三角数区间，又能恢复 $(m,n)$。这不仅证明“二维也是可数”，还给出可逆编码。

有限字母表上的全体有限字符串也可按长度、再按字典序列举。一串可以很长，但它的长度和在该层的位置都是有限的；因此程序源码、公式与有限证明只有至多可数多个。这里必须固定同一套有限或可数的符号表，不能把任意实数直接当作一个可用的新符号。

无限字符串为何越过边界 ​

有限二进制串的集合 $\{0,1{\}}^{\ast }$ 可数，无限二进制序列的集合 $\{0,1{\}}^{\mathbb{N}}$ 却不可数理路不可数集Uncountable set无法单射进自然数集的集合；任何自然数编号的名单都会遗漏成员。。假设所有无限序列排成名单 $s_0,s_1,\dots$，定义

新序列 $t$ 与第 $n$ 行至少在第 $n$ 位不同，所以它不在名单上。这是对角线论证理路康托对角线论证Cantor diagonal argument通过在第 n 位偏离第 n 个候选对象构造未被枚举对象的方法。；无限长描述不是把有限描述“写得更长一点”，而是改变了可能对象的数量级。

同理，所有二进制语言是 $\{0,1{\}}^{\ast }$ 的子集，形成不可数的幂集；程序却只有可数多个，所以有些语言不存在判定程序。相对地，每个语言作为有限字符串集合的子集，本身仍至多可数。语言中的词有多少与一共有多少种语言是两个问题。

可数并与共同的编号 ​

可数集的子集可数，因为单射可以限制到子集；可数集的像也可数，因为可以从原枚举中读出输出。有限个可数集的乘积可数，可反复使用二元配对编码。

对一族 $A_0,A_1,\dots$，若已经同时给定各集合的枚举或单射，就可以用“集合编号、内部编号”这对自然数给并集编码，再去重。若仅知道每个 $A_n$ 可数，却没有共同选好的编号，一般的“可数个可数集之并可数”在 ZF 中需要额外选择原则；可数选择公理足以支持这一步。不能把“对每个集合存在一个编号”直接写成“已经存在一整列选好的编号”。

分析中许多操作恰好允许可数规模：级数理路级数Infinite series序列各项的有限部分和所组成的序列及其极限。按自然数求和，$\sigma$-代数对可数并封闭，测度对两两不交的可数并可加。编号保证操作的索引形式合法；求和与极限能否交换，仍由相应收敛定理决定。

实数中的有理数既可数又稠密。稠密表示每个非空开区间都碰到它，可数表示它能被编号；两者并不冲突，也不能推出整个实数集可数。这一区分使“先在可数测试集上同时成立，再由连续性延伸”成为常用证明方法。

在模型论中，还要分清编号属于谁。若一个集合论模型从外部看是可数的，外部可以枚举它的元素；模型内部仍可能把某个集合判断为不可数，因为那个外部枚举未必是模型内部的函数。Löwenheim–Skolem 现象的关键是内外可使用的函数不同，不是同一个定义同时得出相反结论。