# Find an expression for $|S-\{A_1\cap A_2\cap \dots \cap A_n\}|$ for $A_1,\, A_2, \dots , A_n\subset S$

Find an expression for $|S-\{A_1\cap A_2\cap \dots \cap A_n\}|$ for $A_1,\, A_2, \dots , A_n\subset S$ . and we assume the knowledge of the size of the union of any number of $A_i$'s but not of the intersection of them.

This problem comes from the section in inclusion-exclusion principle, so I'd imagine that I am supposed to use that somewhere. So far what I have done is that I noted $$\bigcap A_i = \left(\bigcap A_i\right)^{c^{\ c}}.$$ Furthermore, this is equal to $\left(\bigcup A_i^c\right)^c = S - \bigcup A_i^c$. Then I have that $S-\{\bigcap A_i\} = S - \{S-\bigcup A_i^c\}$. Thus $$|S-\{A_1\cap A_2\cap \dots \cap A_n\}| = |S| - |S-\{A_1^c\cup\dots\cup A_n^c \}|.$$ Then I can use the inclusion-exclusion principle to get a value of $|S-\{A_1^c\cup\dots\cup A_n^c \}|$.

Does this work? If not, then what would be another way? Also, is their a more combinatorial argument for this? I enjoy those a lot. Thanks.

• $A_1\cap\cdots\cap A_n\subseteq S$ so you probably mean $|S-(A_1\cap\cdots\cap A_n)|$ – drhab Nov 7 '17 at 10:44

## 1 Answer

$$S-(A_1\cap\cdots\cap A_n)=(A_1\cap\cdots\cap A_n)^{\complement}=A_1^{\complement}\cup\cdots\cup A_n^{\complement}$$ With inclusion/exclusion you can find an expression of the cardinality of this set in terms of the form $|A_{i_1}^{\complement}\cap\cdots\cap A_{i_k}^{\complement}|$ where $i_1<\cdots<i_k$.

Observe that: $$A_{i_1}^{\complement}\cap\cdots\cap A_{i_k}^{\complement}=(A_{i_1}\cup\cdots\cup A_{i_k})^{\complement}$$

So this eventually leads to an expression for the cardinality of $S-(A_1\cap\cdots\cap A_n)$ which is useful if the cardinalities of unions of $A_i$ and also the cardinality of $S$ (it cannot be missed) are known.