3
$\begingroup$

The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:

THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION   Let $A_1,A_2,\ldots,A_n$ be finite sets. Then $$ \begin{multline*} |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|. \end{multline*} $$ Proof: We will prove the formula by showing that an element in the union is counted exactly once by the right-hand side of the equation. Suppose that $a$ is a member of exactly $r$ of the sets $A_1,A_2,\ldots,A_n$, where $1 \leq r \leq n$. This element is counted $\binom{r}{1}$ times by $\sum |A_i|$. It is counted $\binom{r}{2}$ times by $\sum |A_i \cap A_j|$. In general, it is counted $\binom{r}{m}$ times by the summation involving $m$ of the sets $A_i$. Thus, this element is counted exactly $$ \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r} $$ times by the expression on the right-hand side of this equation. Our goal is to evaluate this quantity. The binomial formula shows that $$ 0 = (1-1)^r = \binom{r}{0} - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^r \binom{r}{r}. $$ Hence $$ 1 = \binom{r}{0} = \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}. $$ Therefore, each element in the union is counted exactly once by the expression on the right-hand side of the equation. This proves the principle of inclusion-exclusion.

Although the proof seems very exciting, I am confused because what the author has proved is $1=1$ from the LHS and RHS.

Thus, is this still a valid proof? We need to prove that the total cardinality of LHS is the RHS. The RHS produces a $1$ for each member of the union of the sets.

I think in order to produce the cardinality of the union, an extra summation sign should be appended before the expression in RHS. Could someone please clarify?

$\endgroup$
  • $\begingroup$ Who is the author, and what textbook is this taken from? $\endgroup$ – Yuval Filmus Dec 16 '19 at 20:48
  • $\begingroup$ @YuvalFilmus discrete Math, Keneth Rosen $\endgroup$ – MathMan Dec 16 '19 at 20:53
5
$\begingroup$

Let me slightly rephrase the argument. Let $N_r$ be the number of elements contained in exactly $r$ of the sets $A_1,\ldots,A_n$. Then the left-hand side is $$ |A_1 \cup \cdots \cup A_n| = \sum_{r=1}^n N_r. $$ The first sum on the right-hand side is $$ \sum_{1 \leq i \leq n} |A_i| = \sum_{r=1}^n \binom{r}{1} N_r. $$ The second sum on the right-hand side is $$ \sum_{1 \leq i < j \leq n} |A_i \cap A_j| = \sum_{r=2}^n \binom{r}{2} N_r. $$ More generally, the $m$th sum on the right-hand side is $$ \sum_{1 \leq i_1 < i_2 < \cdots < i_m \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_m}| = \sum_{r=m}^n \binom{r}{m} N_r. $$ Therefore the right-hand side is equal to $$ \sum_{r=1}^n \binom{r}{1} N_r - \sum_{r=2}^n \binom{r}{2} N_r + \sum_{r=3}^n \binom{r}{3} N_r - \cdots + (-1)^{n+1} \sum_{r=n}^n \binom{r}{n} N_r. $$ Rearranging, the right-hand side is equal to $$ \left[ \binom{1}{1} \right] N_1 + \left[ \binom{2}{1} - \binom{2}{2} \right] N_2 + \left[ \binom{3}{1} - \binom{3}{2} + \binom{3}{3} \right] N_3 + \cdots + \\ \left[ \binom{n}{1} - \binom{n}{2} + \binom{n}{3} - \cdots + (-1)^{n+1} \binom{n}{n} \right] N_n. $$ The coefficient of the general term $N_m$ is $$ \binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1} \binom{m}{m}. $$ By the binomial theorem, this equals $1$, and so the right-hand side equals $$ 1 \cdot N_1 + 1 \cdot N_2 + 1 \cdot N_3 + \cdots + 1 \cdot N_n = \sum_{r=1}^n N_r, $$ which is exactly the same as the left-hand side.

$\endgroup$
  • $\begingroup$ Sorry. Do you mean $N_r = |A_r|?$ $\endgroup$ – MathMan Dec 16 '19 at 21:42
  • $\begingroup$ I have a bit difficulty comprehending the meaning of $N_r$ here. Thanks for your efforts! $\endgroup$ – MathMan Dec 16 '19 at 21:44
  • $\begingroup$ No, I don't mean $N_r = |A_r|$. Give it a few hours and see if you can decipher my definition of $N_r$. $\endgroup$ – Yuval Filmus Dec 16 '19 at 22:28
2
$\begingroup$

Yes, you are right that an extra summation needs to be appended to the beginning of both sides to prove the inclusion-exclusion formula. This can be understood by using indicator functions (also known as characteristic functions), as follows. Let $U$ be some finite set (the universe), and let $S \subseteq U$. The indicator function (or characteristic function) of $S$ is the 0,1-valued function $I_S: U \rightarrow \{0,1\}$ on the domain $U$, defined by $I_S(x) = 1$ if $x \in U$, and $I_S(x)=0$ if $x \notin U$. Observe that $|S| = \sum_{x \in U} I_S(x)$. In other words, the number of elements in $S$ is equal to a sum of $0$'s and $1$'s, where the number of $1$'s is of course the size of $S$. We are interested in the case where $S = A_1 \cup A_2 \cup \cdots \cup A_n$.

What the proof given in text shows is that the indicator function $I_S$ (where $S = A_1 \cup A_2 \cup \cdots \cup A_n$) is equal to a particular sum of indicator functions (where the subscripts for these latter indicator functions are intersections of the $A_i$'s). More specifically, it is proved that $$I_{A_1 \cup \cdots \cup A_n} = (I_{A_1} + \cdots + I_{A_n} ) - (I_{A_1 \cap A_2} + \cdots + \cdots I_{A_{n-1} \cap A_n}) + (I_{A_1 \cap A_2 \cap A_3} + \cdots )+ \cdots + (-1)^n I_{A_1 \cap \cdots \cap A_n}.$$ This formula holds because, as you show, if an element $x \in U$ appears in exactly $r$ of the $A_i$'s for some $r \ge 1$, then the LHS indicator function trivially evaluates to $1$, and the RHS sum of indicator functions also evaluates to $1$ (by the binomial formula). Similarly, both sides evaluate to $0$ if $r=0$ (i.e. if $x \in U, x \notin S$). Thus, the two 0,1-valued functions are equal, meaning the two functions take the same value for each $x$ in the domain $U$. This means the many terms in RHS sum cancel out to give either a $0$ or a $1$, for any $x \in U$ that you pick.

If two functions $f, g$ on domain $U$ are equal, i.e. if $f(x)=g(x)$ for all $x \in U$, then the summations $\sum_{x \in U} f(x)$ and $\sum_{x \in U} g(x)$ are also equal. So, take the summation of the LHS indicator function's values over $x \in U$, and similarly for the RHS. Recall that for any set $X \subseteq U$, we have $\sum_{x \in U} I_X(u) = |X|$. So, for the left hand side, the sum $\sum_{x \in U} I_{A_1 \cup \cdots \cup A_n}(x)$ evaluates to $|A_1 \cup \cdots \cup A_n|$. For the right hand side, we are taking the sum of all those indicator functions over $x \in U$. Use the fact that $\sum_{x \in U} I_{A_i}(x) = |A_i|$, that $\sum_{x \in U} I_{A_1 \cap A_2}(x) = |A_1 \cap A_2|$ (by taking $X = A_1 \cap A_2$), and so on, to get the inclusion-exclusion formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.