有限集

形式陈述 ​

集合 $A$ 是有限集，当且仅当存在自然数公理库自然数模型Natural numbers · Peano system由零元、后继和二阶归纳原则范畴性刻画的离散数系模型。 $n$ 与双射公理库双射Bijective function · One-to-one correspondence同时为单射和满射的函数。

$$A⟷\{0,1,\dots ,n-1\}.$$

这样的 $n$ 唯一，称为 $A$ 的有限基数；空集对应 $n=0$。

直觉 ​

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

例子与边界 ​

集合 $A=\{a,b,c\}$ 与初始段 $\{0,1,2\}$ 的双射可以显式写成 $a\mapsto 0,b\mapsto 1,c\mapsto 2$，所以 $|A|=3$。改变编号顺序会得到另一双射，却不会改变唯一的自然数 $3$。

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

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

封闭性质与计数 ​

有限性在常见集合构造下保持。若 $A,B$ 有限，则 $A\cup B$、$A\cap B$、$A\setminus B$ 与 $A\times B$ 都有限；若

$$|A|=m,|B|=n,$$

则

$$|A\times B|=mn,|A\cup B|=m+n-|A\cap B|.$$

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

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

$$\sum _{a\in A}w(a)$$

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

幂集公理库幂集Power set集合 A 的所有子集组成的集合，记作 P(A)。 $\mathcal{P}(A)$ 仍有限，并满足

$$|\mathcal{P}(A)|=2^{|A|}.$$

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

不可压缩性与高级边界 ​

鸽巢原理公理库鸽巢原理Pigeonhole principle · Dirichlet's box principle把多于 n 个对象放入 n 个容器时，至少一个容器包含两个对象。表达有限基数的不可压缩性：若 $|A|>|B|$，不存在从 $A$ 到 $B$ 的单射。等价地，有限集合到自身的单射自动为满射，满射也自动为单射。这个性质为枚举终止、有限归纳和“排除一个候选后规模严格下降”提供共同依据。

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

有限性只说明候选能够完整列举，不规定表示成本或访问方式。同一个有限集合可以显式存储、隐式编码或通过 oracle 暴露；时间、空间、通信和查询复杂度仍需各自的计算模型。自动反向链接负责展示这些下游用法，本页只保留它们共享的有限计数基础。

参考资料

• Paul R. Halmos, Naive Set Theory, 1960; Dover reprint 2017, §§23–25。
• Richard Hammack, Book of Proof, 3rd ed., 2018, Chapters 3 and 14。