可数集

可数就是“排得进一张自然数编号的名单”：名单可以无限延伸，但每个成员必须出现在某个有限号码上，没有谁被排在“无限远”的位置。证明可数需要给出统一的编号规则并证明不遗漏；展示任意长的有限前缀，或声称可以继续写下去，都还没有完成这一量词义务。

名单仍然是一维的。对象若天然铺成二维表格，例如全体分数，就不能“先数完第一行再数第二行”，因为第一行永远数不完；必须按坐标和分层或沿对角线折返。可数性保住了逐项处理和归纳枚举，一旦越过这条线，任何名单都必然遗漏对象。

$\mathbb{Z}$ 可数：按 $0,1,-1,2,-2,\dots$ 交错枚举，即可建立与自然数的双射。

$\mathbb{Q}$ 的枚举更能展示分层方法。把最简分数 $p/q$（$q>0$）按 $|p|+q$ 排层，每层只有有限个，再逐层点名，就不会卡在某个无穷行中。类似地，按坐标和 $m+n$ 逐层扫描 $\mathbb{N}\times \mathbb{N}$，每一层都有限而每一对最终都会出现。有限字母表上的全体有限字符串也可先按长度、再按字典序枚举。空集与一切有限集按本条约定同样可数。

反方向，康托对角线论证公理库康托对角线论证Cantor diagonal argument通过在第 n 位偏离第 n 个候选对象构造未被枚举对象的方法。表明 $\mathbb{R}$ 与 $\{0,1{\}}^{\mathbb{N}}$ 是不可数集公理库不可数集Uncountable set无法单射进自然数集的集合；任何自然数编号的名单都会遗漏成员。：任何候选名单都能被对角线构造出的新元素挫败。“每个元素都有有限描述”也不是证明；必须把描述固定为同一套可数字母表上的编码，并验证编码覆盖目标对象且能被自然数编号。

封闭性质有精确边界。可数集的子集可数：已有单射限制到子集即可。有限个可数集的并也可数，可先给来源加有限标签，再把“标签—号码”对编码进 $\mathbb{N}$。但“可数个可数集的并可数”需要同时为每个成员集选定枚举，一般会用到可数选择公理公理库选择公理Axiom of choice · AC把任意集合族中逐个存在的元素同时汇成一个选择函数的公理。；若各集合自带典范枚举，则无需额外选择。

可数性首先刻画“有限语法能够命名多少对象”。有限字母表上的有限字符串只有可数多个，因此程序、公式和有限证明也至多可数；二进制语言却是字符串的子集，全体语言与 $\mathcal{P}(\{0,1{\}}^{\ast })$ 等势而不可数。比较两边便知必有语言不能由任何程序判定。这里真正起作用的是统一编码及幂集增长，不是“每个对象似乎都有某种有限描述”。

可数性还划定分析中允许逐项处理的范围。级数、$\sigma$-代数的可数并和测度的可数可加性都沿自然数索引；可分空间则要求存在一个可数稠密子集。它们共享索引规模，却不是同一个定理：能把事件列成序列，不代表相应极限、并集或测度交换自动成立，仍要检查各自结构条件。

模型论提供一个值得保留的视角边界。向下 Löwenheim–Skolem 定理说明，可数语言中的一阶理论若有无限模型，通常也有可数模型；模型内部所谓“不可数集合”，可能只是不与模型内部任何自然数枚举等势。这不与外部对模型整体的可数枚举矛盾，因为内外允许使用的函数并不相同。