# Summation indices in a proof of Incluson-Exclusion Principle

I rewrote (for easier time reading in the future) the proof of PIE given in my book as follows below and got tangled up in sum notation. I got questions about the $$\color{purple}{\text{purple}}$$ and $$\color{brown}{\text{brown}}$$ bits in the rewritten proof below. The expression $$N_{\ge}(\emptyset)$$ has no index $$j$$ so I think $$\color{purple}{\displaystyle{\sum_{j=0}^nN_{\ge}(\emptyset)} = N_{\ge}(\emptyset)}$$ because there's only one item to sum. Does that make sense? In the case of $$\color{brown}{\displaystyle{N_{\ge}(J)\sum_{j=0}^n\left((-1)^m\binom nm\right) = N_{\ge}(J) \cdot 0}}$$, we have $$\color{brown}{\displaystyle{\sum_{j=0}^n\left((-1)^m\binom nm\right) = 0}}$$, but the actual theorem says $$\displaystyle{\sum_{j=0}^n\left((-1)^j\binom nj\right) = 0}$$ and so indices don't match in the $$\color{brown}{\text{brown bit}}$$. How can I make the indices match up in the $$\color{brown}{\text{brown bit}}$$?

Here below is PIE as given in my book:

Definition

Statement of PIE

Proof

Here below is the rewritten proof:

Let $$U$$ be a universe of objects and let $$P = \{p_1, p_2, p_3, \ldots, p_n\}$$ be a set of properties that the objects may or may not have.

Let $$N_=(J)$$ be a set of all objects all of whose properties are in $$J \subseteq P.$$

Suppose $$|J| = 2$$. Then some of the $$N_=(J)$$s are $$N_=(\{p_1, p_7\}), \ N_=(\{p_{n-1}, p_n\})$$ etc. There are $$\binom n2$$ such $$N_=(J)$$s. Generally, if $$|J| = j$$, then there are $$\binom njN_=(J)$$ objects all of whose properties are in $$J$$ meaning $$\color{red}{\displaystyle{\sum_{|J| = j}(-1)^jN_=(J) = (-1)^j\binom njN_=(J)}}$$. Summing both sides of the expression in $$\color{red}{\text{red}}$$ above, we have $$\color{blue}{\sum_{j=0}^n\left(\sum_{|J| = j}(-1)^jN_=(J)\right) = \sum_{j=0}^n(-1)^j\binom njN_=(J)}$$

Since removing $$N_=(J)$$ elements also removes $$N_{\ge}(J)$$ elements, we can replace $$N_=(J)$$s in the expression $$\color{blue}{\text{in blue}}$$ above with $$N_{\ge}(J)$$s as follows: $$\color{green}{\sum_{j=0}^n\left(\sum_{|J| = j}(-1)^jN_{\ge}(J)\right) = \sum_{j=0}^n(-1)^j\binom njN_{\ge}(J)}$$

Note that the number of objects in $$U$$ with none of the properties is $$N_{\ge}(\emptyset)$$ meaning the number of times $$N_{\ge}(\emptyset)$$ includes each object in $$U$$ is $$1$$ when the object has none of the properties and $$0$$ when the object has at least one property. If we can say the same thing about the expression $$\color{green}{\text{in green}}$$ above, then we can use it instead of $$N_{\ge}(\emptyset)$$.

Now assume an object in $$U$$ contains none of the properties in $$P$$. Then $$|J| = 0$$ meaning $$\displaystyle{\sum_{j=0}^n\left(\sum_{|J| = 0}(-1)^0N_{\ge}(\emptyset)\right) = \color{\purple}{\sum_{j=0}^nN_{\ge}(\emptyset) = N_{\ge}(\emptyset)}}$$. Since $$N_{\ge}\emptyset$$ includes each object in $$U$$ only $$1$$ time when the object has none of the properties, so does the expression $$\color{green}{\text{in green}}$$ above.

Suppose an object in $$U$$ contains $$m$$ properties in $$P$$ where $$1 \le m \le n$$. Then $$|J| = m.$$ Now $$\displaystyle{\sum_{j=0}^n\left(\sum_{|J| = m}(-1)^mN_{\ge}(J)\right) = \sum_{j=0}^n\left((-1)^m\binom nmN_{\ge}(J)\right) = \color{brown}{N_{\ge}(J)\sum_{j=0}^n\left((-1)^m\binom nm\right) = N_{\ge}(J) \cdot 0} = 0}$$

Thus the expression $$\color{green}{\text{in green}}$$ above doesn't even count an object with properties in $$J$$.

Edit (number of onto functions):

We consider functions $$\{1, 2, 3, 4, \ldots,k\} \to \{A, B, C, D\}$$. Let $$A$$ stand for a set of functions whose image does not contain $$a$$. Define $$B, C, D$$ similarly. Let $$N_=(\emptyset)$$ be the number of elements in a set of functions whose image does not miss any of $$a, b, c, d$$ and $$N_{\ge}(\emptyset) -$$ the number of elements in set of all functions including $$\emptyset.$$ Let $$N_{\ge}(m_a)$$ be the number of elements in a set of functions whose image misses $$a$$ and also possibly $$b, c, d$$. In other words, $$N_{\ge}(m_a) = |A|$$ or $$N_{\ge}(m_a) = |A \cap B|$$ or $$N_{\ge}(m_a) = |A \cap C \cap D|$$ etc. Also, let $$AB$$ stand for $$A \cap B.$$

Now take a look at the given pics. Our goal is to count the elements in the square outside the union of $$A, B, C, D$$ as shown in pic 1. To that end start by counting all the elements in the square as shown in pic 2, then remove the elements in the union of $$A, B, C, D$$ from the total number of elements. When we remove $$A$$, we remove $$AB$$ with it. Look at pic 3. When we remove $$B$$, we remove $$AB$$ again. Thus removing $$A \cup B$$ results in us removing $$AB$$ twice. Generally, removing $$A \cup B \cup C \cup D$$ results in us removing $$AB, AC, AD, BC, BD, CD$$ twice each meaning we need to add one copy of each of $$AB, AC, AD, BC, BD, CD$$ back as we meant to remove them only once. When we remove $$A$$, we remove $$ABC$$ with it as in pic 4. Similarly, removing $$B$$ also results in removal of $$ABC$$. This holds for $$C$$ as well meaning as we remove $$A \cup B \cup C$$ we also remove $$ABC$$ three times. But earlier we added $$AB, BC, AC, AD$$ back which resulted in us adding $$ABC$$ back four times. So, when we remove $$A \cup B \cup C \cup D$$, one copy of $$ABC$$ is left behind which we need to get rid of. Similarly we need to remove one copy of each of $$ACD, BCD, ABD.$$ Now removing $$A$$ results in removal of $$ABCD$$ with it as in pic 5. Similarly, removing $$B, C, D$$ means we remove $$ABCD$$ three more times. Earlier, we added $$AB, AC, AD, BC, BD, CD$$ which added $$ABCD$$ back six times. Then we removed $$ABC, BCD, ACD, ABD$$ which removed $$ABCD$$ four times. Thus removing $$A \cup B \cup C \cup D$$ results in removing $$ABCD$$ twice meaning we need to add $$ABCD$$ back once. Algebraically,

$$N_=(\emptyset) = \\ N_{\ge}(\emptyset) \\ - (N_{\ge}(m_a) + N_{\ge}(m_b) + N_{\ge}(m_c) + N_{\ge}(m_d)) \\ + (N_{\ge}(m_am_b) + N_{\ge}(m_am_c) + N_{\ge}(m_am_d) + (N_{\ge}(m_bm_c) + N_{\ge}(m_bm_d) + N_{\ge}(m_cm_d)) \\ - (N_{\ge}(m_am_bm_c) + N_{\ge}(m_am_bm_d) + N_{\ge}(m_bm_cm_d) + N_{\ge}(m_am_bm_d)) \\ + N_{\ge}(m_am_bm_cm_d)$$

Now note, $$N_{\ge}(m_a), \ N_{\ge}(m_b), \ N_{\ge}(m_c), \ N_{\ge}(m_d) \ge (n - 1)^k \\ N_{\ge}(m_am_b), \ N_{\ge}(m_am_c), \ N_{\ge}(m_am_d), \ (N_{\ge}(m_bm_c), \ N_{\ge}(m_bm_d), N_{\ge}(m_cm_d \ge (n - 2)^k \\ N_{\ge}(m_am_bm_c), \ N_{\ge}(m_am_bm_d), \ N_{\ge}(m_bm_cm_d), \ N_{\ge}(m_am_bm_d) \ge (n - 3)^k \\ N_{\ge}(m_am_bm_cm_d) \ge (n - 4)^k \\ N_{\ge}(\emptyset) \ge (n - 0)^k$$

Note, $$n = 4$$, but we use either $$n$$ or $$4$$ depending on whichever is more instructive at the time. Thus, we have $$N_=(\emptyset) \ge \binom 40(n - 0)^k - \binom 41(n - 1)^k + \binom 42(n - 2)^k - \binom 43(n - 3)^k + \binom 44(n - 4)^k = \sum_{j=0}^4\binom 4j(-1)^j(n - j)^k$$

Finally, $$N_= (m_a) = (n - 1)^k$$. However, as we saw above (when working with overlapping circles) removing an object with $$N_= (m_a)$$ properties results in the removal of an object with $$N_{\ge} (m_a)$$ properties. Thus we can replace $$N_{\ge} (m_a)$$ with $$N_= (m_a)$$ meaning $$N_=(\emptyset) = \sum_{j=0}^4\binom 4j(-1)^j(n - j)^k$$

I’ll take them in order. First,

$$\sum_{j=0}^nN_\ge(\varnothing)=(n+1)N_\ge(\varnothing)\,:$$

there are $$n+1$$ terms, one for each value of $$j$$ from $$0$$ through $$n$$, and each term is $$N_\ge(\varnothing)$$. However, this summation never actually occurs in the proof: your derivation of it further down is incorrect.

Your second question is also based on a misunderstanding of the argument; see below.

Now for the proof. $$N_=(J)$$ is not the set of all objects whose properties are in $$J$$: it is the number of objects that have precisely the properties in $$J$$.

You write:

Since removing $$N_=(J)$$ elements also removes $$N_\ge(J)$$ elements, ...

This is not true: $$N_\ge(J)$$ is the number of objects that have all of the properties in $$J$$ and possibly others as well and is generally greater than $$N_=(J)$$. It is the lefthand side of the green displayed expression that is the starting point for the argument; the righthand side is meaningless as written, since $$J$$ is undefined, and the blue displayed expression is irrelevant.

The number of objects in $$U$$ that have none of the properties is $$N_=(\varnothing)$$. It is not $$N_\ge(\varnothing)$$: that is the number of objects in $$U$$ that have at least $$0$$ of the properties, so it is in fact $$|U|$$, the number of objects in $$U$$. The point here is that an object with none of the properties is counted once in the $$j=0$$ term of the lefthand side of the green expression and $$0$$ times in each of the other terms of that sum, so altogether the sum counts it exactly once.

Now we consider an object in $$U$$ that has exactly $$m\ge 1$$ of the $$n$$ properties and want to know how many times it is counted by the sum

$$\sum_{j=0}^n\left(\sum_{\substack{J\subseteq P\\|J|=j}}(-1)^jN_\ge(J)\right)\,.\tag{0}$$

Let $$I$$ be the set of $$m$$ properties possessed by the object. If $$J$$ is any subset of $$P$$, the object is counted in $$N_\ge(J)$$ if and only if $$J\subseteq I$$, i.e., if and only if the object has all of the properties in $$J$$ (and possibly some others as well).

Clearly $$J\nsubseteq I$$ if $$|J|>m$$, so the object is not counted in $$N_\ge(J)$$. Thus, the object is not counted at all in any of the terms

$$\sum_{\substack{J\subseteq P\\|J|=j}}(-1)^jN_\ge(J)\tag{1}$$

with $$j>m$$: it affects only the terms with $$j\le m$$.

Now suppose that $$j\le m$$; how many times is the object counted in $$(1)$$? It is counted once in $$N_\ge(J)$$ for each $$J$$ of cardinality $$j$$ that is a subset of $$I$$. $$I$$ has $$\binom{m}j$$ subsets of cardinality $$j$$, and the object is counted once in each of them, so the object is counted $$\binom{m}j$$ times in the term $$(1)$$. That number is then multiplied by $$(-1)^j$$, so altogether the $$j$$ term $$(1)$$ contributes a total of $$(-1)^j\binom{m}j$$ to the sum $$(0)$$.

In short, the object contributes $$0$$ to the terms $$(1)$$ with $$j>m$$ and $$(-1)^j\binom{m}j$$ to the terms with $$J\le m$$, so altogether it contributes

$$\sum_{j=0}^m(-1)^j\binom{m}j=0$$

to the sum $$(0)$$.

Now put the pieces together: each object that has none of the properties in $$P$$ is counted once in the sum $$(0)$$, and each object that has at least one of those properties is counted a net total of $$0$$ times, so the sum $$(0)$$ is the number of objects in $$U$$ that have none of the properties in $$P$$.

• Thank you. I tried deriving the formula for the number of onto functions (with only four elements in the codomain) using the method of the given proof to better understand the proof in question. Then I modeled the proof in my OP off of the one with onto funcs. I added that attempt in my OPs edit. Not to bother you, but can you take a look at that attempt as well to see if it contains exactly the same mistakes as the ones you outlined in your post. Nov 7, 2020 at 22:23