加法原理定理

第一步(基础情形 $k=2$):设 $A_1$ 与 $A_2$ 不相交,即 $A_1 \cap A_2 = \emptyset$。$A_1 \cup A_2$ 中的每个元素要么属于 $A_1$,要么属于 $A_2$,不相交排除了同时属于两者的可能。将 $A_1 \cup A_2$ 拆成两个不相交的部分 $A_1$ 与 $A_2$,各数一次即得 $|A_1 \cup A_2| = |A_1| + |A_2|$。

第二步(对 $k$ 归纳):假设公式对任意 $k-1$ 个两两不相交的集合已经成立,即 $|A_1 \cup \cdots \cup A_{k-1}| = |A_1| + \cdots + |A_{k-1}|$。令 $B = A_1 \cup \cdots \cup A_{k-1}$。由于 $A_k$ 与所有满足 $i < k$ 的 $A_i$ 不相交,它也与它们的并集 $B$ 不相交。对 $B$ 与 $A_k$ 应用基础情形,得到 $|B \cup A_k| = |B| + |A_k|$。

第三步(合并):把归纳假设中的 $|B|$ 代入上式,得到 $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_{k-1}| + |A_k|$,这正是 $k$ 个集合的加法原理。由于基础情形 $k=2$ 成立,且从 $k-1$ 到 $k$ 的每一步都保持公式成立,由归纳法可知该公式对所有 $k \geq 2$ 都成立。