加法の法則(定理)

第1段階(基本ケース $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$ を素な2つの部分 $A_1$ と $A_2$ に分けてそれぞれを1回数えると $|A_1 \cup A_2| = |A_1| + |A_2|$ が得られる。

第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|$ が得られる。

第3段階(結合):この等式に帰納法の仮定 $|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$ で成り立つ。