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$ .

Formal PIE

PIE, formally

An alternative presentation

About Brent

5 Responses to Formal PIE

Follow Blog via Email

Meta

Categories

Archives

Formal PIE

PIE, formally

An alternative presentation

Share this:

Like this:

Related

About Brent

5 Responses to Formal PIE

Follow Blog via Email

Meta

Categories

Archives