Summation indices in a proof of Incluson-Exclusion Principle

Question

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

Answer 1

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