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?
Best Answer
$$ \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.