The Unapologetic Mathematician

Inclusion-Exclusion Again

Now that we know a little more about characteristic functions, let’s see how they can be used to understand the inclusion-exclusion principle. Our first pass was through a very categorified lens, which was a neat tie-in to Euler characteristics. But we want something a little more down-to-Earth.

So, let’s take a finite collection $\left\{S_i\right\}_{i=1}^n$ of subsets of a set $X$. To each one we have a corresponding idempotent function $\chi_{S_i}$, which is ${1}$ for points in $S_i$ and ${0}$ elsewhere. We can take the complement of a subset in the language of idempotents as usual: $1-\chi_{S_i}=\chi_{{S_i}^c}$. This function is ${1}$ for points not in $S_i$, and ${0}$ in $S_i$.

Now let’s take and multiply all these complementary functions together to get

$\displaystyle\prod\limits_{i=1}^n\left(1-\chi_{S_i}\right)=\prod\limits_{i=1}^n\chi_{{S_i}^c}=\chi_{{S_1}^c\cap\dots\cap{S_n}^c}$

By DeMorgan’s Laws, the intersection of all these complements is the complement of the union of all the $S_i$. Thus

$\displaystyle\prod\limits_{i=1}^n\left(1-\chi_{S_i}\right)=\chi_{(S_1\cup\dots\cup S_n)^c}=1-\chi_{S_1\cup\dots\cup S_n}$

Now let’s expand out the product, just like we expand out the product of any sequence of binomials. In each factor, we choose which of the ${1}$ or the $\chi_{S_i}$ to contribute. First we get the term where we always choose ${1}$, then the terms where we choose exactly one of the $\chi_{S_i}$, then the terms where we choose exactly two of them, and so on until we choose all $n$ of them. The sign of a term is negative when we choose an odd number of the $\chi_{S_i}$, and positive when we choose an even number. That is

\displaystyle\begin{aligned}\prod\limits_{i=1}^n\left(1-\chi_{S_i}\right)&=1-\sum\limits_{1\leq i\leq n}\chi_{S_i}+\sum\limits_{1\leq i

Putting this together with the earlier expression, we find

$\displaystyle\chi_{S_1\cup\dots\cup S_n}=\sum\limits_{1\leq i\leq n}\chi_{S_i}-\sum\limits_{1\leq i

For $n=2$ this gives us back our formula for the characteristic function of the intersection of two sets. For larger $n$ it gives us the inclusion-exclusion principle in terms of characteristic functions.

December 28, 2009 - Posted by | Fundamentals

1 Comment »

1. […] inclusion-exclusion principle tells us that we can rewrite the characteristic function of […]

Pingback by Integrals are Additive Over Regions « The Unapologetic Mathematician | December 30, 2009 | Reply