Định lý quy tắc cộng

Bước 1 (trường hợp cơ sở $k=2$): giả sử $A_1$ và $A_2$ rời nhau, tức $A_1 \cap A_2 = \emptyset$. Mỗi phần tử của $A_1 \cup A_2$ thuộc $A_1$ hoặc thuộc $A_2$, và tính rời nhau loại trừ khả năng thuộc cả hai. Chia $A_1 \cup A_2$ thành hai phần rời nhau $A_1$ và $A_2$ rồi đếm mỗi phần một lần cho ta $|A_1 \cup A_2| = |A_1| + |A_2|$.

Bước 2 (quy nạp theo $k$): giả sử công thức đã đúng với $k-1$ tập rời nhau đôi một bất kỳ, tức $|A_1 \cup \cdots \cup A_{k-1}| = |A_1| + \cdots + |A_{k-1}|$. Đặt $B = A_1 \cup \cdots \cup A_{k-1}$. Vì $A_k$ rời với mọi $A_i$ khi $i < k$, nó cũng rời với hợp $B$. Áp dụng trường hợp cơ sở cho $B$ và $A_k$ cho ta $|B \cup A_k| = |B| + |A_k|$.

Bước 3 (kết hợp): thay giả thiết quy nạp cho $|B|$ vào đẳng thức trên, ta được $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_{k-1}| + |A_k|$, đúng là quy tắc cộng cho $k$ tập. Vì trường hợp cơ sở $k=2$ đúng và mỗi bước từ $k-1$ sang $k$ vẫn giữ công thức đúng, nên theo quy nạp công thức đúng với mọi $k \geq 2$.