Nguyên lý bao hàm và loại trừ

Mỗi phần tử của $A\cup B$ rơi vào đúng một trong ba nhóm rời nhau: chỉ thuộc $A$, chỉ thuộc $B$, hoặc thuộc cả hai; cộng $|A|+|B|$ đếm nhóm "cả hai" hai lần, nên phải bỏ bớt một lần.

Chia $A\cup B$ thành ba phần rời nhau đôi một: $A\setminus B$ (chỉ thuộc $A$), $B\setminus A$ (chỉ thuộc $B$), và $A\cap B$ (thuộc cả hai). Vì các phần này rời nhau và phủ kín $A\cup B$, nên $|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|$.

Bây giờ để ý rằng $A$ tự nó chia thành hai phần rời nhau $A\setminus B$ và $A\cap B$, nên $|A|=|A\setminus B|+|A\cap B|$, tức $|A\setminus B|=|A|-|A\cap B|$. Tương tự, $|B\setminus A|=|B|-|A\cap B|$.

Thay hai biểu thức này vào phương trình đầu, ta được $|A\cup B|=(|A|-|A\cap B|)+(|B|-|A\cap B|)+|A\cap B|=|A|+|B|-|A\cap B|$, chính là $|A\cup B|=|A|+|B|-|A\cap B|$.

Mỗi phần tử thuộc nhiều tập sẽ được cộng một lần cho mỗi tập đơn, trừ một lần cho mỗi cặp, cộng lại cho mỗi bộ ba, và cứ thế; mẫu dấu xen kẽ chính là điều cần thiết để đưa tổng đếm của nó về đúng $1$.

Cố định một phần tử bất kỳ $x$. Nếu $x$ không thuộc tập nào trong $A_1,\ldots,A_n$, nó đóng góp $0$ cho cả hai vế, nên giả sử $x$ thuộc đúng $m\ge 1$ tập.

Với mỗi $k$, số giao $k$ tập $A_{i_1}\cap\cdots\cap A_{i_k}$ chứa $x$ bằng số cách chọn $k$ trong $m$ tập chứa $x$, tức là $\binom{m}{k}$. Vậy tổng đóng góp của $x$ vào vế phải là $\sum_{k=1}^n(-1)^{k+1}\binom{m}{k}=\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}$ (các số hạng với $k>m$ triệt tiêu vì $\binom{m}{k}=0$).

Theo định lý nhị thức, $\sum_{k=0}^m(-1)^k\binom{m}{k}=(1-1)^m=0$, nên $\sum_{k=1}^m(-1)^k\binom{m}{k}=-1$, nhân với $-1$ cho đúng $\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}=1$.

Vậy mọi phần tử thuộc ít nhất một tập đóng góp đúng $1$ vào vế phải, khớp với đóng góp $1$ của nó vào $\left|\bigcup_{i=1}^n A_i\right|$; phần tử không thuộc tập nào đóng góp $0$ cho cả hai vế. Vì mọi phần tử đóng góp như nhau cho cả hai vế, hai vế bằng nhau.