principle of inclusion-exclusion, proof of

The proof is by induction. Consider a single set $A_1$. Then the principle of inclusion-exclusion states that $|A_1|=|A_1|$, which is trivially true.

Now consider a collection of exactly two sets $A_1$ and $A_2$. We know that

$$A\cup B=(A\setminus B)\cup (B\setminus A)\cup (A\cap B)$$

Furthermore, the three sets on the right-hand side of that equation must be disjoint. Therefore, by the addition principle, we have

$|A\cup B|$$=$$|A\setminus B|+|B\setminus A|+|A\cap B|$

$=$$|A\setminus B|+|A\cap B|+|B\setminus A|+|A\cap B|-|A\cap B|$

$=$$|A|+|B|-|A\cap B|$

So the principle of inclusion-exclusion holds for any two sets.

Now consider a collection of $N>2$ finite sets $A_1,A_2,\mathrm{\dots }{A}_N$. We assume that the principle of inclusion-exclusion holds for any collection of $M$ sets where . Because the union of sets is associative, we may break up the union of all sets in the collection into a union of two sets:

$$\bigcup _{i=1}^N{A}_i=\left(\bigcup _{i=1}^{N-1}{A}_i\right)\cup A_N$$

By the principle of inclusion-exclusion for two sets, we have

$$\left|\bigcup _{i=1}^N{A}_i\right|=\left|\bigcup _{i=1}^{N-1}{A}_i\right|+|A_N|-\left|\left(\bigcup _{i=1}^{N-1}{A}_i\right)\cap A_N\right|$$

Now, let $I_k$ be the collection of all $k$-fold intersections of $A_1,A_2,\mathrm{\dots }{A}_{N-1}$, and let $I_k^{\prime }$ be the collection of all $k$-fold intersections of $A_1,A_2,\mathrm{\dots }{A}_N$ that include $A_N$. Note that $A_N$ is included in every member of $I_k^{\prime }$ and in no member of $I_k$, so the two sets do not duplicate one another.

We then have

$$\left|\bigcup _{i=1}^N{A}_i\right|=\sum _{j=1}^N\left({(-1)}^{(j+1)}\sum _{S\in I_j}|S|\right)+|A_N|-\left|\left(\bigcup _{i=1}^{N-1}{A}_i\right)\cap A_N\right|$$

by the principle of inclusion-exclusion for a collection of $N-1$ sets. Then, we may distribute set intersection over set union to find that

$$\left|\bigcup _{i=1}^N{A}_i\right|=\sum _{j=1}^N\left({(-1)}^{(j+1)}\sum _{S\in I_j}|S|\right)+|A_N|-\left|\bigcup _{i=1}^{N-1}(A_i\cap A_N)\right|$$

Note, however, that

$$(A_x\cap A_N)\cup (A_y\cap A_N)=(A_x\cap A_y\cap A_N)$$

Hence we may again apply the principle of inclusion-exclusion for $N-1$ sets, revealing that

$\left|{\displaystyle \bigcup _{i=1}^N}{A}_i\right|$$=$${\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j}}|S|\right)+|A_N|-{\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j}}|S\cap A_N|\right)$

$=$${\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j}}|S|\right)+|A_N|-{\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_{j+1}^{\prime }}}|S|\right)$

$=$${\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j}}|S|\right)+|A_N|-{\displaystyle \sum _{j=2}^N}\left({(-1)}^{(j)}{\displaystyle \sum _{S\in I_j^{\prime }}}|S|\right)$

$=$${\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j}}|S|\right)+|A_N|+{\displaystyle \sum _{j=2}^N}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j^{\prime }}}|S|\right)$

The second sum does not include $I_1^{\prime }$. Note, however, that $I_1^{\prime }=\{A_N\}$, so we have

$\left|{\displaystyle \bigcup _{i=1}^N}{A}_i\right|$$=$${\displaystyle \sum _{j=1}^{N-1}}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j}}|S|\right)+{\displaystyle \sum _{j=1}^N}\left({(-1)}^{(j+1)}{\displaystyle \sum _{S\in I_j^{\prime }}}|S|\right)$

$=$${\displaystyle \sum _{j=1}^{N-1}}\left[{(-1)}^{(j+1)}\left({\displaystyle \sum _{S\in I_j}}|S|+{\displaystyle \sum _{S\in I_j^{\prime }}}|S|\right)\right]+{(-1)}^{N+1}\left|{\displaystyle \bigcap _{i=1}^N}{A}_i\right|$

Combining the two sums yields the principle of inclusion-exclusion for $N$ sets.