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 Nov 7 '17 at 10:44

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.