有限集

有限性把“可以点名”加强为“存在一个有终点、无遗漏、无重复的点名表”。双射中的满射保证不遗漏，单射保证不重复，初始段的长度给出终点。自然数也可以逐个点名，但它没有最后一项，因此“可以继续列举”并不意味着有限。

编号不把集合变成有序对象。一个作业调度器有“等待、运行、成功、失败”四种状态，可以任意编码为 $0,1,2,3$；重新排列编码后，状态集合和状态种类数不变。哪些状态允许互相转换，需要另给转移关系，不能从数字编号中读出。

有限性还是一种规模陈述，而不是效率承诺。长度为 $n$ 的二进制串只有 $2^n$ 个，集合当然有限；逐一检查它们，仍可能需要指数级工作。显式数组、隐式约束和查询接口也可能描述同一有限集合，却提供完全不同的访问成本。

元素、位置和空集 ​

$\{a,b,a\}=\{a,b\}$，所以当 $a\ne b$ 时它只有两个元素。有限序列理路序列Sequence以自然数为定义域的函数。 $(a,b,a)$ 则有三个位置：集合计数不同的元素，序列长度计数位置。

空集的基数是零，而 $\{\varnothing \}$ 的基数是一。前者没有元素，后者把空集本身当作一个元素。空集之间的空函数是唯一双射，因此零元素情形已经包含在定义中。

有限集合无法“挤出一个空位” ​

若 $A$ 有限，任何单射 $f:A\to A$ 都是满射，否则它把全部 $|A|$ 个元素塞进较小的真子集 $f(A)$。反过来，满射 $A\to A$ 也是单射：一旦两个输入共用一个输出，剩余输入就不足以覆盖全部输出。

无限集的行为不同。$f(n)=n+1$ 是 $\mathbb{N}\to \mathbb{N}$ 的单射，却遗漏 $0$；$g(0)=0$、$g(n+1)=n$ 是满射，却把 $0,1$ 都映到 $0$。证明“自映射单射等价于满射”时，有限性承担的是实质条件。

“不能与自身真子集双射”称为 Dedekind 有限。有限集一定具有这个性质；在不带选择公理的 ZF 集合论中，逆命题不能无条件使用。加入选择公理后，Dedekind 有限与这里的有限性等价。

从编号得到计数规则 ​

有限集的子集仍有限：沿原编号依次保留属于子集的元素，再从零重新编号。有限集合的像也有限，因为每个输出都来自有限多个输入中的某一个，去掉重复输出即可。

设 $|A|=m$、$|B|=n$。不交并可以先列 $A$ 再列 $B$，得到 $m+n$ 个位置；笛卡尔积可以给 $(i,j)$ 编号为 $in+j$，得到 $mn$ 个位置。因此

并集公式中的减项修正了交集被重复计数的问题；乘积公式则把一次选择拆成两个坐标。例如两台区分身份的工作器各处于四种状态之一，联合状态有 $4^2=16$ 种。若系统另外限制了哪些状态能同时出现，就要从这 16 种组合中筛选。

给 $A$ 的每个元素决定“选入”或“不选入”，就唯一确定一个子集；故幂集理路幂集Power set把 A 的每一种子集选择提升为元素所得的集合，记作 P(A)。满足

更一般地，若目标集合有 $q$ 个元素，则函数 $A\to B$ 有 $q^m$ 个。空定义域也有且仅有一个函数；计数中的 $0^0=1$ 在这里表达“没有任何位置需要填写，空方案恰有一个”。当定义域非空而目标为空时，函数数为零。

有限归纳与有限求和 ​

“每次删去一个元素”给出在有限集合上归纳的方式：先处理空集，再证明加入一个新元素不会破坏所需结论。有限多个有限集的并仍有限，就可沿集合个数反复应用不交分解与加法计数；换成无限多个集合时，单点集的并已经可能是整个 $\mathbb{N}$。

对取值于交换幺半群的权重 $w$，可以定义

空和取单位元，结合律允许改变括号，交换律允许改变枚举顺序。缺少交换律时，有限性仍保证计算结束，却不保证重排后结果相同；例如字符串拼接就应保留输入次序。有限集能够嵌入自然数集，因而也是至多可数集理路可数集Countable set · At most countable能单射进自然数集的集合；等价地，它有限或能按自然数无重复枚举。，但它额外提供了一个有限终点。