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

 $\displaystyle|A\cup B|$ $\displaystyle=$ $\displaystyle|A\setminus B|+|B\setminus A|+|A\cap B|$ $\displaystyle=$ $\displaystyle|A\setminus B|+|A\cap B|+|B\setminus A|+|A\cap B|-|A\cap B|$ $\displaystyle=$ $\displaystyle|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},\dots A_{N}$. We assume that the principle of inclusion-exclusion holds for any collection of $M$ sets where $1\leq M. 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},\dots A_{N-1}$, and let $I^{\prime}_{k}$ be the collection of all $k$-fold intersections of $A_{1},A_{2},\dots A_{N}$ that include $A_{N}$. Note that $A_{N}$ is included in every member of $I^{\prime}_{k}$ 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

 $\displaystyle\left|\bigcup_{i=1}^{N}A_{i}\right|$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I_{j}}|S|\right)+|A_% {N}|-\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I_{j}}|S\cap A_{N}|\right)$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I_{j}}|S|\right)+|A_% {N}|-\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I^{\prime}_{j+1}}|S|\right)$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I_{j}}|S|\right)+|A_% {N}|-\sum_{j=2}^{N}\left((-1)^{(j)}\sum_{S\in I^{\prime}_{j}}|S|\right)$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I_{j}}|S|\right)+|A_% {N}|+\sum_{j=2}^{N}\left((-1)^{(j+1)}\sum_{S\in I^{\prime}_{j}}|S|\right)$

The second sum does not include $I^{\prime}_{1}$. Note, however, that $I^{\prime}_{1}=\{A_{N}\}$, so we have

 $\displaystyle\left|\bigcup_{i=1}^{N}A_{i}\right|$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{N-1}\left((-1)^{(j+1)}\sum_{S\in I_{j}}|S|\right)+% \sum_{j=1}^{N}\left((-1)^{(j+1)}\sum_{S\in I^{\prime}_{j}}|S|\right)$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{N-1}\left[(-1)^{(j+1)}\left(\sum_{S\in I_{j}}|S|+\sum% _{S\in I^{\prime}_{j}}|S|\right)\right]+(-1)^{N+1}\left|\bigcap_{i=1}^{N}A_{i}\right|$

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

Title principle of inclusion-exclusion, proof of PrincipleOfInclusionexclusionProofOf 2013-03-22 12:33:27 2013-03-22 12:33:27 mps (409) mps (409) 6 mps (409) Proof msc 05A99