7
$\begingroup$

Proofs class homework question - It doesn't ask for us to prove, derive, or even illustrate the inclusion/exclusion principle - Just to jot it down.

We're learning about sets and inclusivity/exclusivity (evidently) I've got the inclusion/exclusion principle for three sets down to 2 sets. I'm sort a bit confused as to how I'd go about getting 4. Is there a systematic/elementary manner to prove it or is this more to do with general knowledge and research?

$\endgroup$
  • 1
    $\begingroup$ Do you know what is PIE for 3 sets? If so, what would you guess the 4 set equation is? Once you have the correct equation, it is pretty easy to prove it, esp if you know a good proof of the 2 set case. $\endgroup$ – Calvin Lin Feb 24 '14 at 2:53
17
$\begingroup$

$$ \begin{align} &|A\cup B\cup C\cup D|\\[3pt] &=|A|+|B|+|C|+|D|\Big\}\text{ all singletons}\\ &-(|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|)\Big\}\text{ all pairs}\\ &+(|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|)\Big\}\text{ all triples}\\ &-|A\cap B\cap C\cap D|\Big\}\text{ all quadruples}\\ \end{align} $$ This is an instance of a special case of the Generalized Inclusion-Exclusion Principle.

$\endgroup$
  • $\begingroup$ So.. that's it right up there? Or is that a hint $\endgroup$ – user122661 Feb 24 '14 at 15:31
  • 1
    $\begingroup$ @user122661: That is the whole thing for 4 sets. It is also arranged so that it might be possible to extrapolate to more sets. $\endgroup$ – robjohn Feb 24 '14 at 15:36
  • $\begingroup$ ahh I see didn't think the pattern would come out looking so simple $\endgroup$ – user122661 Feb 24 '14 at 15:45
6
$\begingroup$

You could intuitively try to prove an equation by drawing four sets in the form of a Venn diagram -- say $A_1, A_2, A_3, A_4$, and observing the intersections between the circles. You want to find the cardinality of the union. Now, you will notice that if you just try to add the four sets, there will be repeated elements. Elements in the intersections need to be subtracted. But after subtracting, you might find you need to add some elements back in again. Quickly, you will find this is hard to generalize, but you will see a pattern -- you alternate signs with respect to the intersection sets.

Ultimately, a nice way to prove PIE for $n$ sets is to consider the binomial theorem. The ultimate equation is something like sum of cardinalities of all 1-sets (i.e., $|A_1| + |A_2| + |A_3| + \ldots + |A_n|$) - intersections of all 2-sets + intersections of all 3-sets - ... $\pm$ intersections of $n$-sets. Observe that every element is in the intersection of $j$ sets. When adding the entire previous sum together, note that the element is added in $S = \dbinom{j}{1} - \dbinom{j}{2} + \ldots \pm \dbinom{j}{n}$ times. We want to show $S = 1$. Note the binomial identity, ${(-1+1)}^n = \displaystyle\sum_{k=0}^n \dbinom{n}{k} (-1)^k (1)^{(n-k)} = \displaystyle\sum_{k=0}^n \dbinom{n}{k} (-1)^k$, and observe that this summation is equivalent to $1-S$. ${(-1+1)}^n = 0^n = 0$, and $1-S = 0$, yielding $S=1$, as desired, for every element. That is, every element is counted exactly once.

$\endgroup$
  • 1
    $\begingroup$ This is exactly how I prove the Generalized Inclusion-Exclusion Principle in this answer (+1) $\endgroup$ – robjohn Feb 24 '14 at 8:22

protected by Community Oct 4 '18 at 6:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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