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<N$ . 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
Canonical name	PrincipleOfInclusionexclusionProofOf
Date of creation	2013-03-22 12:33:27
Last modified on	2013-03-22 12:33:27
Owner	mps (409)
Last modified by	mps (409)
Numerical id	6
Author	mps (409)
Entry type	Proof
Classification	msc 05A99

$\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\|$

$\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)$

	$\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\|$