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.
[…] 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 |