1

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)

2468
  • 137
  • 2
    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 Answers2

1

$|\bigcap_i A_i| = \sum_{i} |A_i| - \sum_{i<j}|A_i\bigcup A_j| + \sum_{i<j<k }| A_i\bigcup A_j\bigcup A_k| - \dots$

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.

Boyku
  • 712
  • 3
  • 10
0

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.

Mohammad Riazi-Kermani
  • 68,728