You are currently browsing the daily archive for March 20, 2008.

**Part 2:**

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

if ,

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 .

**Lemma 2:**

and

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.

## Recent Comments