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 of subsets of a set . To each one we have a corresponding idempotent function , which is for points in and elsewhere. We can take the complement of a subset in the language of idempotents as usual: . This function is for points not in , and in .

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

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

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 or the to contribute. First we get the term where we always choose , then the terms where we choose exactly one of the , then the terms where we choose exactly two of them, and so on until we choose all of them. The sign of a term is negative when we choose an odd number of the , and positive when we choose an even number. That is

Putting this together with the earlier expression, we find

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

About these ads