Formal PIE

I’ve been talking informally about the Principle of Inclusion-Exclusion but I realized it would be useful to state it more formally before proceeding to some proofs. The only problem is that a fully formal statement of PIE has a lot of details and uses a lot of notation—so I’ll state it formally and then spend some time going through and explaining the parts carefully.

Suppose we have a collection of n finite sets A_1, A_2, A_3, and so on up to A_n, which are all subsets of a finite set U. We think of U as the “universe”, i.e. the entire population of things we are considering, and all the A_i are sets which “live in” the universe. Each set A_i typically represents a subpopulation with a particular property. For example, U might be the set of all people; then A_1 might be the set of people named Brent, A_2 might be the set of people who own a dog, and so on. Or as another example, U might be the set of natural numbers up to one million, and then A_1 might be the even numbers up to one million, A_2 might be the prime numbers less than one million, A_3 might be the set of all the ages I’ve ever been in my life, and so on.

The diagram below illustrates the general situation for n=3. The big green rectangle is the universe set U; the blue circles represent the three subsets A_1, A_2, and A_3, which in general may overlap, as in the diagram (though they don’t have to).

As I’ve presented it so far, PIE then tells us how to compute the number of elements of the universe which are not in any of the A_i, represented by the green shaded area in the diagram above. Put another way, this is the number of elements of the universe which have none of the properties (e.g. people not named Brent who don’t own a dog; natural numbers up to one million which aren’t even or prime or an age I’ve ever been; etc.).

PIE, formally

Without further ado, here is PIE:

\displaystyle |U| - \left| \bigcup_{i = 1}^n A_i \right| = \sum_{S \subseteq \{1 \dots n\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|

Let’s go through this piece by piece. On the left-hand side, the big union symbol works just like a summation symbol, i.e. big-sigma notation: so \displaystyle \bigcup_{i=1}^n A_i means A_1 \cup A_2 \cup \dots \cup A_n, the union of all the A_i. Unioning the sets throws out duplicates, so the union represents all the elements of the universe which are in one or more of the A_i (i.e. the blue area in the diagram above). Subtracting this number from the size of U then gives the number of elements which aren’t in any of the A_i.

The right-hand side is a bit more complicated. First, \displaystyle \sum_{S \subseteq \{1 \dots n\}} means we take a sum over every subset of \{1 \dots n\}. That is, we will get one number for every possible subset of \{1 \dots n\} (all 2^n of them), and we add all these numbers up. Now, for each subset S, the big intersection symbol \displaystyle \bigcap_{i \in S} A_i means to take the intersection of all the A_i represented by S. For example, if S = \{2, 3, 7, 9\}, then we get the intersection A_2 \cap A_3 \cap A_7 \cap A_9. We find the size of this intersection and make it either positive or negative: raising -1 to a power keeps flipping back and forth between 1 (if the power is even) and -1 (if the power is odd). So (-1)^{|S|} means we should add the term if the number of A_i in the intersection is even, and subtract if the number is odd.

There is one subtle point to make, which I also mentioned in my previous post. All subsets of \{1 \dots n\} includes the empty subset, S = \varnothing, and it’s not necessarily obvious what the intersection \displaystyle \bigcap_{i \in S} A_i means when S is the empty set. How are we supposed to take the intersection of zero sets? To make everything work, we have to interpret it as being equal to the entire universe U. However, this is actually sensible, since U is like the “identity” for intersection: U \cap A_i = A_i for each A_i. Put another way, intersecting always results in a smaller set than you started with, so when intersecting you always start with the biggest possible set (namely, the universe U) and then the result gets smaller and smaller as you intersect more sets. That is, we can interpret A_i \cap A_j \cap A_k \cap \dots as (((U \cap A_i) \cap A_j) \cap A_k) \cap \dots. So if you don’t intersect any A_i you’re just left with the starting set U. (This is exactly the same argument for why a union of zero sets should be the empty set, but that certainly feels more intuitive! Pop quiz: what do we get if we’re taking the product of a set of numbers and the set is empty?)

For some examples, see the previous post. You might like to try writing out PIE for n=4.

An alternative presentation

Since we just argued why the empty set results in a term of |U| on the right-hand side (note it is positive since (-1)^{|\varnothing|} = (-1)^0 = 1), and there is also a positive |U| term on the left-hand side, we can subtract |U| from both sides to cancel them out, leaving this:

\displaystyle - \left| \bigcup_{i = 1}^n A_i \right| = \sum_{\stackrel{S \subseteq \{1 \dots n\}}{S \neq \varnothing}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|

(Notice how we got rid of the |U| term on the right-hand side just by specifying that the summation should not use S = \varnothing.)

If we finally negate both sides, we get an alternative form of PIE which is actually the way it is typically presented. We can negate every term on the right-hand side by simply adding 1 to the power of (-1), so any terms which used to be positive are now negative and vice versa.

\displaystyle \left| \bigcup_{i = 1}^n A_i \right| = \sum_{\stackrel{S \subseteq \{1 \dots n\}}{S \neq \varnothing}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|

For example, when n = 3 this says

|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|.

This alternative presentation is nice because it tells us directly about the size of the union of all the A_i, i.e. the number of things in at least one of the sets (the blue region in the diagram), rather than the number of things in none of the sets (the green region). It seems like we would typically care more about the blue region; talking about the green region seems roundabout. However, as you can see, the right-hand side becomes a bit more awkward in this alternative presentation, because of the need to specify the extra condition S \neq \varnothing, and the +1 in the exponent of the (-1). Strange as it might seem at first, PIE is really more natural when phrased in terms of the number of things in none of the sets A_i.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in combinatorics, pattern and tagged , , , , , . Bookmark the permalink.