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.

  • $\begingroup$ $A_1\cap\cdots\cap A_n\subseteq S$ so you probably mean $|S-(A_1\cap\cdots\cap A_n)|$ $\endgroup$
    – drhab
    Commented Nov 7, 2017 at 10:44

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .