After having understood the inclusion-exclusion principle by working out a few cases and examples in my earlier post, we are now ready to prove the general version of the principle.
As with many things in mathematics, there is a “normal” way of doing proofs and there is the “Polya/Szego” way of doing proofs. (Ok, ok, I admit it’s just a bias I have.) I will stick to the latter. Ok, let’s state the principle first and follow it up with its proof in a step-by-step fashion.
Inclusion-Exclusion Principle: Let there be a set of objects. Suppose out of these objects, there are objects of type , objects of type objects of type and objects of type . Also, suppose denote the number of objects that are simultaneously of type AND AND AND AND respectively. Then, the number of objects that are NOT of type is
— Notation —
Let (finite or infinite) be the universe of discourse. Suppose . Then, the characteristic function of is defined as
and otherwise, for all .
For example, suppose . Let (i.e. even integers.) Then, , and so on.
Note: and for all . Here, denotes the empty set. Due to this, we will use and interchangeably from now.
Lemma 1: iff for all .
Proof: We first prove the “only if”part. So, suppose . Let . If , then . But, we also have , in which case, . If, on the other hand, , then . Hence, in either case, for all .
We now prove the “if” part. So, suppose for all . Let . Then, , which forces , which implies . Hence, , and this completes our proof.
Note: If is finite, then .
for all . (Here, is the complement of .)
Proof: The proof for each case is elementary.
Lemma 3: Suppose is finite. If , then the characteristic function of is , i.e.
for all .
Proof: Note the above is an extension of the third part of lemma . A simple induction on the number of subsets of proves the result.
— Proof of the inclusion-exclusion principle —
Now, suppose are subsets of objects of type , respectively. Observe that the set of objects that are NOT of type is simply the region outside of all the oval regions! (Look at the previous post to see what this means.) And this region is simply the subset . Using the first part of lemma , we see that the characteristic function of this outside region is , which from lemma is the same as
Expand the last expression to get
Now, sum over all the elements of and use the second part of lemma to obtain the desired result. And this completes our proof.