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 N objects. Suppose out of these N objects, there are N_a objects of type a, N_b objects of type b, \ldots , N_k objects of type k and N_l objects of type l. Also, suppose N_{ab}, N_{ac}, \ldots , N_{abc}, \ldots , N_{ab \ldots kl} denote the number of objects that are simultaneously of type a AND b, a AND c, \ldots , a, b AND c, \ldots , a, b, c, k AND l, respectively. Then, the number of objects that are NOT of type a, b, c, \ldots , k, l is

N - (N_a + N_b + \ldots + N_k + N_l)

+ (N_{ab} + N_{ac} + \ldots + N_{kl})

- (N_{abc} + \ldots ) + \ldots

\pm N_{abc \ldots kl}.

Notation —

Let U (finite or infinite) be the universe of discourse. Suppose A \subset U. Then, the characteristic function 1_A: U \to \{ 0, 1 \} of A is defined as

1_A (x) = 1 if x \in A,

and 1_A(x) = 0 otherwise, for all x \in U.

For example, suppose U = \{ 1, 2, 3, 4, \ldots , 29, 30 \}. Let A = \{ 2, 4, 6, \ldots , 28, 30 \} (i.e. even integers.) Then, 1_A(2) = 1_A(26) = 1, 1_A(3) = 1_A(29) = 0, and so on.

Note: 1_U (x) = 1 and 1_{\emptyset}(x) = 0 for all x \in U. Here, \emptyset denotes the empty set. Due to this, we will use 1 and 1_U interchangeably from now.



Lemma 1: A \subset B iff 1_A(x) \le 1_B(x) for all x \in U.

Proof: We first prove the “only if”part. So, suppose A \subset B. Let x \in U. If x \in A, then 1_A(x) = 1. But, we also have x \in B, in which case, 1_B(x) = 1. If, on the other hand, x \notin A, then 1_A(x) = 0 \le 1_B(x). Hence, in either case, 1_A(x) \le 1_B(x) for all x \in U.

We now prove the “if” part. So, suppose 1_A(x) \le 1_B(x) for all x \in U. Let x \in A. Then, 1_A(x) = 1, which forces 1_B(x) = 1, which implies x \in B. Hence, A \subset B, and this completes our proof.

Note: If U is finite, then \displaystyle |A| = \sum_{x \in U}1_A(x).

Lemma 2: 1_{A^c}(x) = 1 - 1_A(x) ,

1_{A \cap B}(x) = 1_A(x) 1_B(x), and

1_{A \cup B}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))

for all x \in U. (Here, A^c is the complement of A.)

Proof: The proof for each case is elementary.

Lemma 3: Suppose U is finite. If A, B, C, \ldots \subset U, then the characteristic function of A \cup B \cup C \cup \ldots is 1 - (1 - 1_A)(1 - 1_B)(1 - 1_C) \ldots, i.e.

1_{A \cup B \cup C \cup \ldots}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))(1 - 1_C(x)) \ldots for all x \in U.

Proof: Note the above is an extension of the third part of lemma (2). A simple induction on the number of subsets of U proves the result.

Proof of the inclusion-exclusion principle —

Now, suppose A, B, C, \ldots, K, L are subsets of objects of type a, b, c, \ldots, k, l, respectively. Observe that the set of objects that are NOT of type a, b, c, \ldots , k, l 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 (A \cup B \cup B \cup \ldots \cup K \cup L)^c. Using the first part of lemma (2), we see that the characteristic function of this outside region is 1 - 1_{A \cup B \cup B \cup \ldots \cup K \cup L}, which from lemma (3) is the same as

(1-1_A)(1-1_B)(1-1_C) \ldots (1-1_K)(1-1_L).

Expand the last expression to get

1 - (1_A + 1_B + 1_C + \ldots)

+ (1_A1_B + 1_A1_C + \ldots)

- (1_A1_B1_C + \ldots) + \ldots

\pm 1_A1_B\ldots 1_L.

Now, sum over all the elements of U and use the second part of lemma (2) to obtain the desired result. And this completes our proof.

About these ads