形式陈述

集合 $A$$A$ 是有限集，当且仅当存在自然数 $n$$n$ 与双射

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

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

直觉

有限意味着可以在有限步中无重复地列完全部元素，并且列表长度与列举顺序无关。它比“目前只看到有限多个”更强。

例子与边界

有限集的子集有限，有限个有限集的并有限。有限集合到自身的单射自动为满射；对无限集合失败，例如 $n\mapsto n+1$$n\mapsto n+1$ 是 $\mathbb N$$\mathbb{N}$ 到自身的单射但不是满射。

推论与应用

有限性是组合计数、算法输入规模和鸽巢原理的基础。证明集合无限，可构造任意大的有限子集或否定任何有限枚举。

参考资料

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