# Inclusion_exclusion general formula for intersections?

Assume $$A_1,\, A_2, \ldots , A_n$$ are subsets of a finite set $$S$$. Can we find an expression for the size of $$S-\{A_1\cap A_2 \cap \ldots \cap A_n\}$$ in term of the unions of any number of $$A_i$$'s (similar to the one we have for $$S-\{A_1\cup A_2 \cup \ldots \cup A_n\}$$ in term of the intersections of the sets $$A_i$$'s)

• Hint: Complementation transforms unions into intersections and vice versa (de Morgan's law). – darij grinberg Oct 21 '18 at 23:00
• But It complicated to express its explicit general formula. I started with minimum size and faced a difficulty to generalize for all finite numbers, – 2468 Oct 21 '18 at 23:15

## 2 Answers

You are talking about the complement of the union which is the same as the intersection of complements.

Thus this follows your formula for the intersection applied to complements.

$$|\bigcap_i A_i| = \sum_{i} |A_i| - \sum_{i

every element that belongs to all $$A_1...A_n$$ may be found exactly once in the left intersection. In the right-hand part it is counted multiple times, like :

$$n\ times - \binom n 2 \ times + \binom n 3 \ times =\cdots = 1 \ time$$ because $$(1-1)^n = 0$$.

Overall, every element in intersection is counted exactly one time so we get the size of the intersection.