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?

Solution 1:

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

Solution 2:

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.