有限集

有限性意味着存在一个会终止且无遗漏、无重复的编号。它不是“对象看起来很少”，也不只是“可以开始列举”：自然数本身能依次列出，却没有最后一个编号。与初始自然数段的双射同时给出终止位置和每个元素的唯一位置，这才使有限归纳、无序求和与计数公式有严格基础。

一个作业调度器的状态集合可以写成

把这四种状态任意编号为 $0,1,2,3$，便给出 $S$ 与初始段 $4=\{0,1,2,3\}$ 的双射。换一种编号会改变编码，却不会改变 $|S|=4$；有限基数只记录状态种类数，不携带状态转换规则。

“可以逐个列出来”不是有限性的充分条件。映射 $n\mapsto n$ 枚举了全部自然数，但这个过程没有有限终点；有限集合的编号只使用 $0$ 到 $n-1$。有限集合到自身的单射自动为满射；对无限集合则会失败，例如 $n\mapsto n+1$ 是 $\mathbb{N}$ 到自身的单射，却遗漏 $0$。

集合 $\{a,b,a\}$ 实际只有两个元素，因为集合不记录重复；它与 $\{1,2\}$ 等势。若 $A$ 有 $m$ 个元素、$B$ 有 $n$ 个元素且不交，则 $|A\cup B|=m+n$；不交条件去掉后必须扣除交集。空集有限且基数为零，它与空的自然数初始段之间存在唯一双射。

不可压缩性与高级边界 ​

鸽巢原理表达有限基数的不可压缩性：若 $|A|>|B|$，不存在从 $A$ 到 $B$ 的单射。等价地，有限集合到自身的单射自动为满射，满射也自动为单射。这个性质为枚举终止、有限归纳和“排除一个候选后规模严格下降”提供共同依据。

证明一个集合无限，可以证明它不与任何自然数初始段等势，或说明每个候选有限编号都会遗漏元素。若已构造集合与自身真子集之间的双射，也足以推出无限。有限集必然不与自身真子集等势，即 Dedekind-finite；反方向在 ZF 中不能无条件倒置，因为其等价性涉及选择原则。这一集合论边界不改变本科主线中的初始段定义。

有限性只说明候选能够完整列举，不规定表示成本或访问方式。同一个有限集合可以显式存储、隐式编码或通过 oracle 暴露；时间、空间、通信和查询复杂度仍需各自的计算模型。

封闭性质与计数 ​

有限集的每个子集仍有限。若 $A,B$ 有限，则 $A\cup B$、$A\cap B$、$A\setminus B$ 与 $A\times B$ 都有限；若

则

有限多个有限集的并仍有限，证明可沿集合个数归纳。这里“有限多个”不可省略：无限族中每个成员即使都是单点，其并也可能无限。

同一个归纳机制允许在有限集上定义与证明无序求和。若运算有单位元，且交换律和结合律成立，表达式

不依赖枚举 $A$ 的顺序：从空集的零元开始，每次加入一个尚未列出的元素即可。若运算不交换，结果仍会依赖排列，有限性本身不会替代代数条件。

有限集也是至多可数集公理库可数集Countable set · At most countable · Countably infinite能单射进自然数集的集合；等价地，它有限或能按自然数无重复枚举。的特例：把有限编号直接看成到 $\mathbb{N}$ 的单射即可。其幂集公理库幂集Power set把 A 的每一种子集选择提升为元素所得的集合，记作 P(A)。 $\mathcal{P}(A)$ 仍有限，并满足

更一般地，从 $A$ 到含 $q$ 个元素集合的函数共有 $q^{|A|}$ 个。这些公式分别对应“每个元素选入或不选入”以及“每个输入独立选择一个像”；它们依赖有限乘法原理，而不是把无穷基数运算机械套入。