I'd like to express every combination represented using union or intersection between multiple sets.

For example, we have 3 sets $A_1,A_2,A_3$, the following combinations can be generated by unions and/or intersections between $A_1, A_2, A_3$.

$$A_1 \setminus (A_2 \cup A_3)$$ $$A_2 \setminus (A_1 \cup A_3)$$ $$A_3 \setminus (A_1 \cup A_2)$$ $$(A_1 \cap A_2) \setminus A_3$$ $$(A_1 \cap A_3) \setminus A_2$$ $$(A_2 \cap A_3) \setminus A_1$$ $$A_1 \cap A_2 \cap A_3$$

Using Venn diagram, the combination means the distinct area enclosed by lines of $A_1, A_2, A_3$.

I'd like to formalize the combination for multiple sets $A_i \; (1 \leq i \leq n)$. Then I considered the following expression, but I cannot prove the expression is true.

$$\bigcap_{r \in N} A_r \setminus \bigcup_{s \in N^\complement} A_s \quad (\emptyset\not=N\subseteq\{1,2,\dots,n\}, N^\complement=\{1,2,\dots,n\}\setminus N)$$

If the expression is true, please prove it. If not, please correct the expression to represent all combination of multiple sets.

In addition, I think that the cardinality of union of multiple sets can be represent using the expression as follows;

$$\left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\not=N\subseteq\{1,2,\dots,n\}} \left| \bigcap_{r \in N} A_r \setminus \bigcup_{s \in N^\complement} A_s \right|$$

For the cardinality of union of multiple sets, there is inclusion–exclusion principle.

$$\left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,2,\ldots,n\}}(-1)^{|J|-1} \Biggl|\bigcap_{j\in J} A_j\Biggr|$$

From this, we can have

$$\sum_{\emptyset\not=N\subseteq\{1,2,\dots,n\}} \left| \bigcap_{r \in N} A_r \setminus \bigcup_{s \in N^\complement} A_s \right| = \sum_{\emptyset\neq J\subseteq\{1,2,\ldots,n\}}(-1)^{|J|-1} \Biggl|\bigcap_{j\in J} A_j\Biggr|$$ Is this correct?


Your expression is correct. Given any point $x\in\bigcup_{i=1}^n A_i$, let $N$ be the (necessarily nonempty) set of all $1\le i\le n$ for which $x\in A_i$; then $x$ is in the set $\bigcap_{r\in N} A_r \setminus \bigcup_{s\in N^c} A_s$ for this $$N$ and for none of the others. That proves your disjoint union claim, and the other claims follow quickly from that one.


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.