# What is the inclusion-exclusion principle for 4 sets?

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?

• 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. – Calvin Lin Feb 24 '14 at 2:53

\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.
• @user122661 Note that for $n$ sets there are $2^n - 1$ terms, for this special case there are $2^{\color{red}{4}}-1$ cases. – Eduardo Sebastian Aug 6 '20 at 21:42
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.