Inclusion-Exclusion Principle
Contents |
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 \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^n A_i}\right)\) | \(=\) | \(\displaystyle \sum_{i=1}^n f \left({A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \le i < j \le n} f \left({A_i \cap A_j}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \sum_{1 \le i < j < k \le n} f \left({A_i \cap A_j \cap A_k}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i=1}^n A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
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=1}^n A_i}\right) = \sum_{i=1}^n f \left({A_i}\right)$
Proof
Proof by induction:
For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^n A_i}\right)\) | \(=\) | \(\displaystyle \sum_{i=1}^n f \left({A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \le i < j \le n} f \left({A_i \cap A_j}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \sum_{1 \le i < j < k \le n} f \left({A_i \cap A_j \cap A_k}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i=1}^n A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
$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 on Union of Sets.
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 \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^r A_i}\right)\) | \(=\) | \(\displaystyle \sum_{i=1}^r f \left({A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \le i < j \le r} f \left({A_i \cap A_j}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \sum_{1 \le i < j < k \le r} f \left({A_i \cap A_j \cap A_k}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \left({-1}\right)^{r-1} f \left({\bigcap_{i=1}^r A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Then we need to show:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^{r+1} A_i}\right)\) | \(=\) | \(\displaystyle \sum_{i=1}^{r+1} f \left({A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \le i < j \le r+1} f \left({A_i \cap A_j}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \sum_{1 \le i < j < k \le r+1} f \left({A_i \cap A_j \cap A_k}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \left({-1}\right)^r f \left({\bigcap_{i=1}^{r+1} A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Induction Step
This is our induction step:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^{r+1} A_i}\right)\) | \(=\) | \(\displaystyle f \left({\bigcup_{i=1}^r A_i \cup A_{r+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle f \left({\bigcup_{i=1}^r A_i}\right) + f \left({A_{r+1} }\right) - f \left({\bigcup_{i=1}^r A_i \cap A_{r+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | from the base case |
Consider $\displaystyle f \left({\bigcup_{i=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=1}^r \left({A_i \cap A_{r+1}}\right)}\right)$
To this, we can apply the induction hypothesis:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^r \left({A_i \cap A_{r+1} }\right)}\right)\) | \(=\) | \(\displaystyle \sum_{i=1}^r f \left({A_i \cap A_{r+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \le i < j \le r} f \left({A_i \cap A_j \cap A_{r+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \sum_{1 \le i < j < k \le r} f \left({A_i \cap A_j \cap A_k \cap A_{r+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \left({-1}\right)^{r-1} f \left({\bigcap_{i=1}^r A_i \cap A_{r+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
At the same time, we have the expansion of the term $\displaystyle f \left({\bigcup_{i=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=1}^{r+1} A_i}\right)$:
- $\displaystyle \left({-1}\right)^{s-1} \sum_{{i \in I} \atop {\left|{I}\right| = s}} f \left({\bigcap_{i \in I} A_i}\right) - \left({-1}\right)^{s-2} \sum_{{i \in J} \atop {\left|{J}\right| = s-1}} f \left({\bigcap_{i \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 \in I'} \atop {\left|{I'}\right| = s}} f \left({\bigcap_{i \in I'} A_i}\right)$
where this time, $I'$ ranges over all sets of $s$ elements out of $\left[{1 \, . \, . \, r+1}\right]$.
This is the required term in $s$ intersections in the expansion of $\displaystyle f \left({\bigcup_{i=1}^{r+1} A_i}\right)$.
Just to check, we can see the first term is:
- $\displaystyle \sum_{i=1}^r f \left({A_i}\right) + f \left({A_{r+1}}\right) = \sum_{i=1}^{r+1} f \left({A_i}\right)$
As the expression $\displaystyle f \left({\bigcup_{i=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=1}^r A_i \cap A_{r+1}}\right)$
which works out as:
- $\displaystyle \left({-1}\right)^r f \left({\bigcap_{i=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 \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f \left({\bigcup_{i=1}^n A_i}\right)\) | \(=\) | \(\displaystyle \sum_{i=1}^n f \left({A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \le i < j \le n} f \left({A_i \cap A_j}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \sum_{1 \le i < j < k \le n} f \left({A_i \cap A_j \cap A_k}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(+\) | \(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i=1}^n A_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
$\blacksquare$
Proof of Corollary
As $A_1, A_2, \ldots, A_n$ are pairwise disjoint, their intersections are all empty.
The main result holds, but from Cardinality of Empty Set, all the terms apart from the first vanish.
$\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
- Geoffrey Grimmett and Dominic Welsh: Probability: An Introduction (1986): $\S 1.4 \ (12), \ (13)$: Exercise $8$
- Geoffrey Grimmett and Dominic Welsh: Probability: An Introduction (1986): $\S 1.11$: Problem $12 \ \text{(a)}$
