PIE: proof by algebra

In my previous post I stated a very formal, general form of the Principle of Inclusion-Exclusion, or PIE.¹ In this post I am going to outline one proof of PIE. I’m not going to give a completely formal proof, because the notation gets quite hairy (imagine doing algebraic manipulations on the formulas in the previous post)! But I hope to give enough of an intuition that when I say “and so on”, intrepid readers with good algebra skills should be able to complete a formal algebraic proof.

Set algebra

For the proof, we will first need a few algebraic facts about set operations:

Set intersection distributes over union, that is,

$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ .

You should be able to convince yourself of this by staring at a picture:

Also, if you think of union as being like addition and intersection as being like multiplication, then this says $(A + B)C = AC + BC$ , which makes it easy to remember. (Although unlike the case of addition and multiplication, union also distributes over intersection, that is, $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$ —you might like to try convincing yourself that this works. We won’t need this fact, though.)
Set intersection has some nice properties:
- It is idempotent, that is, $A \cap A = A$ : if you intersect a set with itself you get the same set back.
- It is commutative, that is, $A \cap B = B \cap A$ : the order of sets being intersected doesn’t matter.
- Finally, it is associative, that is, $(A \cap B) \cap C = A \cap (B \cap C)$ : if we have a sequence of intersections to do it doesn’t matter which one we start with. Because of this we can just write things like $A \cap B \cap C \cap D$ without worrying about parentheses.
Later in the proof we will use these properties together to argue, for example, that $A \cap C \cap B \cap C = A \cap B \cap C$ : associativity means it doesn’t matter where we put parentheses; commutativity means we can swap the $C$ and $B$ , and then idempotence says that the two adjacent copies of $C$ can be replaced by one copy.

There are lots of other nice properties, too—for example, union has similar properties to intersection—but these are the only ones we will need for the proof below.

Finally, to save space and make things a bit easier to read, in the rest of the post I will sometimes omit the $\cap$ symbol and write just $AB$ instead of $A \cap B$ . For example, using this notation the fact that intersection distributes over union can be written

$(A \cup B)C = AC \cup BC.$

The proof

Onward to the proof! We’ll prove the alternative presentation of PIE I introduced in my previous post, which tells us how to compute the size of a set like $A \cup B \cup C \cup \dots$ . The proof is by induction on the number of sets being unioned.

First, for $n = 1$ , PIE just says that $|A| = |A|$ . Done!

Well, actually, to get things off the ground we really need to treat $n=2$ as a base case as well. In this case, PIE says that

$|A \cup B| = |A| + |B| - |AB|$

(remember that $AB$ means $A \cap B$ ). We’ll call this equation PIE2. We can prove it by staring at another picture:

This is pretty clear: adding the sizes of $A$ and $B$ double-counts their overlap, so we have to subtract it once.

Now is where it gets more interesting. Consider the case with three sets, $|A \cup B \cup C|$ . The trick is to start by writing $A \cup B \cup C$ as $(A \cup B) \cup C$ and then to apply PIE2, using $A \cup B$ as the first set and $C$ as the second. In the proof below I’ve written the justification for each step in curly brackets.

$\begin{array}{rcl}|A \cup B \cup C| &=& |(A \cup B) \cup C| \\[1em] &=& \quad\text{\{ PIE2 \}} \\[1em] && |A \cup B| + |C| - |(A \cup B)C| \\[1em] &=& \quad\text{\{ intersection distributes over union \}} \\[1em] && |A \cup B| + |C| - |AC \cup BC| \\[1em] &=& \quad\text{\{ PIE2, twice \}} \\[1em] && (|A| + |B| - |AB|) + |C| - (|AC| + |BC| - |ACBC|) \\[1em] &=& \quad\text{\{ intersection properties, rearrange \}} \\[1em] && |A| + |B| + |C| - |AB| - |AC| - |BC| + |ABC| \end{array}$

Notice in the last step how we turned $ACBC$ into $ABC$ —recall that the properties of intersection let us reorder the sets in an intersection like this and get rid of duplicates.

And there we go, we have derived PIE for $n = 3$ just using PIE2 and the laws of set algebra! We’ll call this result PIE3. Now, what about the case for $n = 4$ ?

$\begin{array}{rcl}|A \cup B \cup C \cup D| &=& |(A \cup B \cup C) \cup D| \\[1em] &=& \quad\text{\{ PIE2 \}} \\[1em] && |A \cup B \cup C| + |D| - |(A \cup B \cup C)D| \\[1em] &=& \quad\text{\{ intersection distributes over union \}} \\[1em] && |A \cup B \cup C| + |D| - |AD \cup BD \cup CD| \\[1em] &=& \quad\text{\{ PIE3, twice \}} \\[1em] \dots \end{array}$

There is a lot of algebra to do after applying PIE3 twice, but I think it’s actually better to not do it and instead focus on the big picture. We already know what $|A \cup B \cup C|$ is. We get every combination of intersections among $A$ , $B$ , and $C$ , added or subtracted according to whether the number is odd or even. But what about $|AD \cup BD \cup CD|$ ? Notice it’s the same as $|A \cup B \cup C|$ but where each set has been intersected with $D$ . We’re going to end up with every possible intersection between $AD$ , $BD$ , and $CD$ , but because we can cancel out duplicate copies of $D$ , this is the same as taking every possible intersection between $A$ , $B$ , and $C$ , and then intersecting each with one copy of $D$ . Also note that because we’re subtracting $|AD \cup BD \cup CD|$ , the signs will be flipped relative to what we got with $|A \cup B \cup C|$ —which makes sense since each term will have one extra set in it (namely, $D$ ) which will turn odd intersections into even and vice versa. In other words, at a very high level we will end up with

(all combinations of $A$ , $B$ , $C$ ) + $D$ – (all combinations of $A$ , $B$ , $C$ with a $D$ added)

Notice how every possible combination of $A$ , $B$ , $C$ , and $D$ other than the empty intersection shows up exactly once, with the correct sign: every combination that doesn’t include $D$ shows up in the first part (with the correct sign); then $|D|$ is added by itself; then every combination that does include $D$ and at least one other set shows up in the last part (with sign flipped to reflect the addition of one extra set).

In general, you can see how this is going to work. For each $n$ we can prove PIE $(n+1)$ , that is, the version of PIE for a union of $n+1$ sets, by splitting off a single set $X$ , using PIE2 like so:

$|(A_1 \cup \dots \cup A_n) \cup X| = |A_1 \cup \dots \cup A_n| + |X| - |(A_1 \cup \dots \cup A_n)X|$

and then using PIE $n$ twice, once yielding all combinations without $X$ , and once yielding all combinations with $X$ . As I said, the notation to write that out formally (without any ellipses!) gets a bit hairy, but hopefully the idea makes sense!

Next time we’ll see a completely different proof of PIE, that relies on counting rather than algebra.

It turns out there are even more general forms—for example see Callan McGill’s comment on my previous post—perhaps a later post!↩