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

Our other blog

Visitors to this blog

Blog Stats

  • 346,162 hits

Wikio Ranking

Wikio - Top Blogs - Sciences

Current Online Readers

Recent Comments

prof dr drd horia or… on My first post
prof drd horia orasa… on My first post
prof dr mircea orasa… on Inequality with log
notedscholar on Self-referential Paradoxes, In…
prof dr mircea orasa… on Inequality with log
prof dr mircea orasa… on Inequality with log
prof dr mircea orasa… on 2010 in review
kenji on Basic category theory, I
prof dr mircea orasa… on Solution to POW-10: Another ha…
prof drd horia orasa… on Continued fraction for e
prof drd horia orasa… on Inequality with log
prof dr mircea orasa… on Solution to POW-12: A graph co…
prof dr mircea orasa… on The Character of Physical…
prof dr mircea orasa… on Milk and Tea puzzle
prof drd horia orasa… on Inequality with log

Archives

March 2008
M T W T F S S
 12
3456789
10111213141516
17181920212223
24252627282930
31