Inclusion-Exclusion Principle

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal S$ be an algebra of sets.

Let $A_1, A_2, \ldots, A_n$ be finite sets.

Let $f: \mathcal S \to \R$ be an additive function.


Then:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^n A_i}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n f \left({A_i}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le n} f \left({A_i \cap A_j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} f \left({A_i \cap A_j \cap A_k}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle \cdots \, \) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i \mathop = 1}^n A_i}\right)\) $\quad$ $\quad$


Corollary

Let $\mathcal S$ be an algebra of sets.

Let $A_1, A_2, \ldots, A_n$ be finite sets which are pairwise disjoint.

Let $f: \mathcal S \to \R$ be an additive function.


Then:

$\displaystyle f \left({\bigcup_{i \mathop = 1}^n A_i}\right) = \sum_{i \mathop = 1}^n f \left({A_i}\right)$


Proof

Proof by induction:

For all $n \in \N_{>0}$, let $P \left({n}\right)$ be the proposition:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^n A_i}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n f \left({A_i}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le n} f \left({A_i \cap A_j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} f \left({A_i \cap A_j \cap A_k}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle \cdots \, \) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i \mathop = 1}^n A_i}\right)\) $\quad$ $\quad$


$P(1)$ is true, as this just says $f \left({A_1}\right) = f \left({A_1}\right)$.


Basis for the Induction

$P(2)$ is the case:

$f \left({A_1 \cup A_2}\right) = f \left({A_1}\right) + f \left({A_2}\right) - f \left({A_1 \cap A_2}\right)$

which is the result Additive Function is Strongly Additive.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $P \left({r}\right)$ is true, where $r \ge 2$, then it logically follows that $P \left({r+1}\right)$ is true.


So this is our induction hypothesis:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^r A_i}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^r f \left({A_i}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le r} f \left({A_i \cap A_j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le r} f \left({A_i \cap A_j \cap A_k}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle \cdots \, \) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{r-1} f \left({\bigcap_{i \mathop = 1}^r A_i}\right)\) $\quad$ $\quad$


Then we need to show:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^{r+1} A_i}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{r+1} f \left({A_i}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le r+1} f \left({A_i \cap A_j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le r+1} f \left({A_i \cap A_j \cap A_k}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle \cdots \, \) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^r f \left({\bigcap_{i \mathop = 1}^{r+1} A_i}\right)\) $\quad$ $\quad$


Induction Step

This is our induction step:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^{r+1} A_i}\right)\) \(=\) \(\displaystyle f \left({\bigcup_{i \mathop = 1}^r A_i \cup A_{r+1} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f \left({\bigcup_{i \mathop = 1}^r A_i}\right) + f \left({A_{r+1} }\right) - f \left({\bigcup_{i \mathop = 1}^r A_i \cap A_{r+1} }\right)\) $\quad$ Basis for the Induction $\quad$


Consider $\displaystyle f \left({\bigcup_{i \mathop = 1}^r A_i \cap A_{r+1}}\right)$.

By the fact that Intersection Distributes over Union, this can be written:

$\displaystyle f \left({\bigcup_{i \mathop = 1}^r \left({A_i \cap A_{r+1}}\right)}\right)$

To this, we can apply the induction hypothesis:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^r \left({A_i \cap A_{r+1} }\right)}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^r f \left({A_i \cap A_{r+1} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le r} f \left({A_i \cap A_j \cap A_{r+1} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le r} f \left({A_i \cap A_j \cap A_k \cap A_{r+1} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle \cdots \, \) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{r-1} f \left({\bigcap_{i \mathop = 1}^r A_i \cap A_{r+1} }\right)\) $\quad$ $\quad$


At the same time, we have the expansion of the term $\displaystyle f \left({\bigcup_{i \mathop = 1}^r A_i}\right)$ to take into account.


So we can consider the general term of $s$ intersections in the expansion of $\displaystyle f \left({\bigcup_{i \mathop = 1}^{r+1} A_i}\right)$:

$\displaystyle \left({-1}\right)^{s-1} \sum_{{I} \subseteq \left[{1 \,.\,.\,r}\right] \atop {\left|{I}\right| = s}} f \left({\bigcap_{i \mathop \in I} A_i}\right) - \left({-1}\right)^{s-2} \sum_{{J} \subseteq \left[{1 \,.\,.\,r}\right] \atop {\left|{J}\right| = s-1}} f \left({\bigcap_{i \mathop \in J} A_i \cap A_{r+1}}\right)$

where:

$I$ ranges over all sets of $s$ elements out of $\left[{1 \,.\,.\, r}\right]$
$J$ ranges over all sets of $s-1$ elements out of $\left[{1 \,.\,.\, r}\right]$
$1 \le s \le r$


Messy though it is, it can be seen that this expression is merely:

$\displaystyle \left({-1}\right)^{s-1} \sum_{{I'} \subseteq \left[{1 \,.\,.\,r+1}\right] \atop {\left|{I'}\right| = s}} f \left({\bigcap_{i \mathop \in I'} A_i}\right)$

where this time, $I'$ ranges over all sets of $s$ elements out of $\left[{1 \,.\,.\, r+1}\right]$ and $1 \le s \le r+1$.


This is the required term in $s$ intersections in the expansion of $\displaystyle f \left({\bigcup_{i \mathop = 1}^{r+1} A_i}\right)$.


Just to check, we can see the first term is:

$\displaystyle \sum_{i \mathop = 1}^r f \left({A_i}\right) + f \left({A_{r+1}}\right) = \sum_{i \mathop = 1}^{r+1} f \left({A_i}\right)$

As the expression $\displaystyle f \left({\bigcup_{i \mathop = 1}^r A_i \cap A_{r+1}}\right)$ consists only of intersections of two or more elements of $\mathcal S$, we see it does not contribute to this first term.


Finally, let us make sure of the last term - this is:

$\displaystyle - \left({-1}\right)^{r-1} f \left({\bigcap_{i \mathop = 1}^r A_i \cap A_{r+1}}\right)$

which works out as:

$\displaystyle \left({-1}\right)^r f \left({\bigcap_{i \mathop = 1}^{r+1} A_i}\right)$


We've done enough.


So $P \left({r}\right) \implies P \left({r+1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

\(\displaystyle f \left({\bigcup_{i \mathop = 1}^n A_i}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n f \left({A_i}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le n} f \left({A_i \cap A_j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} f \left({A_i \cap A_j \cap A_k}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle \cdots \, \) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i \mathop = 1}^n A_i}\right)\) $\quad$ $\quad$

$\blacksquare$


Comment

This result is usually quoted in the context of combinatorics, where $f$ is the cardinality function.

It is also seen in the context of probability theory, in which $f$ is taken to be a probability measure.


Historical Notes

This formula, in various forms, has been attributed to:


Sources