1
$\begingroup$

I am having trouble figuring out how this notation works, specifically how the intersection relates to the rest of the summation. It's just stuck there after it.

I would greatly appreciate any help you can give in explaining it to me!

$$\left\vert \bigcup^{n}_{i=1} A_{i} \right\vert = \sum_{\substack{J \neq Ø \\ J \subseteq {[} n {]}}} (-1)^{\left\vert J \right\vert -1} {} \left\vert \bigcap_{i \in J} A_{i} {} \right\vert$$

Wikipedia, Inclusion–exclusion principle

$\endgroup$
  • $\begingroup$ Well it's explained right there in the wikipedia page! The "sum" is really more like a successive adding, then subtracting, then adding, then... $\endgroup$ – The Chaz 2.0 Dec 10 '14 at 5:02
2
$\begingroup$

The sum runs over every nonempty subset $J$ of $\{1, 2, 3, ..., n\}$. There will be exactly $2^n-1$ of these subsets, so there will be $2^n-1$ terms in the summation. I think this is most easily seen with an example. Say $n=2$. Then the sum would be:

$\left| \cup_{i=1}^n A_i \right| = (-1)^{|{\{1\}|-1}}|A_1| + (-1)^{|{\{2\}|-1}}|A_2| + (-1)^{|{\{1, 2\}|-1}}|A_1\cap A_2| = |A_1| + |A_2|-|A_1 \cap A_2|$

Hope this helps. If not, feel free to comment and I can try to clear things up.

$\textbf{Edit:}$

To clear up some questions of the OP, I'll include a simple example application of the inclusion-exclusion principle. I'll do an example in which $n=2$. That is, in which we want to determine the cardinality of the union of two sets.

Let $A_1 = \{1, 2, 3, 4, 5\}$, and $A_2 = \{3, 4, 5, 6, 7\}$. We wish to determine $|A_1 \cup A_2|$. We can easily see by inspection that $A_1 \cup A_2 = \{1, 2, 3, 4, 5, 6, 7\}$, so $|A_1 \cup A_2| = 7$. Therefore, we'll be able to check our answer after we use the inclusion-exclusion principle to compute $|A_1 \cup A_2|$.

By the inclusion-exclusion principle we have:

$$\left| \bigcup_{i=1}^2 A_i \right| = |A_1 \cup A_2| = \sum_{\substack{J \subseteq \{1, 2\} \\ J \ne \emptyset}} (-1)^{|J|-1}\left| \bigcap_{i \in J} A_i \right|$$

This means that for each nonempty subset $J$ of $\{1, 2\}$, we add a new term to our subset. The nonempty subsets of $\{1, 2\}$ are $\{1\}, \{2\},$ and $\{1, 2\}$. Therefore, the inclusion-exclusion principle gives:

$$\left| A_1 \cup A_2 \right| = (-1)^{|{\{1\}|-1}}\left|\bigcap_{i \in \{1\}} A_i\right| + (-1)^{|{\{2\}|-1}}\left|\bigcap_{i \in \{2\}} A_i\right| + (-1)^{|{\{1, 2\}|-1}}\left|\bigcap_{i \in \{1, 2\}} A_i\right| = (-1)^0 |A_1| + (-1)^0|A_2|+(-1)^1 |A_1 \cap A_2| = |A_1| + |A_2|+|A_1 \cap A_2|$$

Now, $A_1 = \{1, 2, 3, 4, 5\}$, $A_2 = \{3, 4, 5, 6, 7\}$, and $A_1 \cap A_2 = \{3, 4, 5, 6, 7\}$, so $|A_1| = |A_2| = 5$, and $|A_1 \cup A_2| = 3$. Plugging these into our most recent formula gives:

$$\left| A_1 \cup A_2 \right| = |A_1| + |A_2|+|A_1 \cap A_2| = 5 + 5 - 3 = 7$$

As stated above, we know that $A_1 \cup A_2 = \{1, 2, 3, 4, 5, 6, 7\}$, so $|A_1 \cup A_2| = 7$. Therefore, the inclusion-exclusion principle gave the correct answer! If you have any questions about this example, feel free to ask in the comments below. :)

$\endgroup$
  • $\begingroup$ Thank you! So, if $n$ = 3 then I would have 8 possible sets, 7 if the empty one is removed? $A_1$ being {1} and $A_7$ being {1,2,3}? I would end up with a really long formula along the lines of $|A_1| + |A_2| + |A_3| + |A_4| + |A_5| + |A_6| + |A_7| - |A_1 \cap A_2| - |A_1 \cap A_3 |... + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_3 \cap A_4|...$ ? $\endgroup$ – Amedea d'Amore Dec 12 '14 at 1:24
  • $\begingroup$ You're welcome! However, your reasoning isn't quite correct. The $n$-value indicates how many sets $A_i$ there are. For example, if $n=3$, then you have three sets $A_1, A_2, A_3$, and you want to compute the cardinality of their union. On the other hand, the value $2^n-1$ indicates the number of nonempty subsets of $\{1, 2, 3, \dots , n\}$. There will then be $2^n-1$ terms in your summation. So for $n=3$, there are $2^3-1 = 7$ nonempty subsets of $\{1, 2, 3\}$, and hence 7 terms in the summation. I'll update my answer to include a worked example of what I mean. Let me know if it helps. $\endgroup$ – Gecko Dec 12 '14 at 3:34
  • $\begingroup$ Absolutely brilliant answer! I'm having a much easier job understanding my books now! A final (maybe silly) question - Is there a rule stating the order that each operand in the expression should be operated on? i.e. $A_1$ first, then $A_2$ second, then $A_3$ or maybe $A_1 \cap A_2$ third? Is there a standard? $\endgroup$ – Amedea d'Amore Dec 15 '14 at 0:47
  • $\begingroup$ I'm glad you've found the answer helpful. Sorry, but I'm slightly unclear on what you mean by "a rule stating the order that each operand in the expression should be operated on". Is the operator to which you're referring the intersection operator $\cap_{i \in J}$? $\endgroup$ – Gecko Dec 15 '14 at 3:07
  • $\begingroup$ My apologies, I am probably coming at this wrong, but say we implemented a rule that states after 2 iterations, the summation must stop. $|A_1| + |A_2|+|A_1 \cap A_2|$ would give us $|A_1| + |A_2|$, but $|A_2| + |A_2 \cap A_1| + |A_1|$ would give us $|A_2| + |A_2 \cap A_1|$. So the order that everything is evaluated would be important. Maybe I am wrong to look at summations like loops running over and over? $\endgroup$ – Amedea d'Amore Dec 16 '14 at 21:45
0
$\begingroup$

From the context, it seems $[n]$ is the power set of $\{1,2,3,....,n\}$, so its summing over all nonempty subsets $J$ of the power set. So, for subsets of length 1 (that's the $|J|$), you ADD the order of each $A_i$, then for subsets of length 2, it's saying to subtract each pairwise intersection, then add each triple-wise intersection, etc.

$\endgroup$
0
$\begingroup$

Literally, the sum reads: Take the sum over the expression: $$(-1)^{|J|-1}\left|\bigcap_{i\in J}A_i\right|$$ for all non-empty subsets $J$ of the integers $\{1,2,\ldots,n\}$. The expression is the size of the intersection of the subsets $A_i$ where $i\in J$, negated when $|J|$ is odd. More intutively, you can read this as:

The size of the union of the $A_i$ is equal to the size of the intersection of an odd number of terms of $A_i$ (e.g. the size of each $A_i$ plus the size of any intersection of three $A_i$, ...) minus the size of the intersection of even numbers of terms from $A_i$ (e.g. the intersection of any pair). You could, equivalently read it as:

Sum up the sizes of each $A_i$. Now, subtract the size of the intersection of each pair. Now add the size of the intersection of each triplet, etc.

So, for $n=2$, the sum expands as: $$|A_i|+|A_j|-|A_i\cap A_j|$$

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