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.

• 346,162 hits