5
$\begingroup$

So for two and three sets I have: $$|A\cup B| = |A| +|B| - |A \cap B|,$$

$$|A\cup B\cup C| = |A| + |B| +|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.$$

What is the general solution for $n$ sets? Thank you!

For example if I want to find the area for n overlapping rectangles (at different angles or radii etc). what is the general formula? I want to know what combinations I need to add and subtract to achieve this.

overlapping rectangles

$\endgroup$
  • $\begingroup$ This formula is about the number of elements, not the sets themselves. $\endgroup$ – Bernard Aug 27 '19 at 22:15
  • 3
    $\begingroup$ What you mean is the principle of exclusion and inclusion, I guess: en.wikipedia.org/wiki/… To build the union of sets alone, you do not need a formula. $\endgroup$ – Cornman Aug 27 '19 at 22:16
  • $\begingroup$ What do you mean "calculate for overlapping rectangles at different angles"? $\endgroup$ – R. Burton Aug 27 '19 at 22:17
6
$\begingroup$

The general formula is known as Poincaré's formula or inclusion-exclusion formula. It is an alternating sum which goes like this (the sum is finite since $r\le n$): $$\biggl|\bigcup_{i=1}^n A_i\biggr|=\sum_{i=1}^n\bigl|A_i\bigr|-\sum_{1\le i<j\le n}^n\bigl|A_i\cap A_j\bigr|+\dots+(-1)^r\mkern -1.5em\sum_{\substack{1\le i_1<\dots<i_r\le n}}^n\mkern -1.5em\bigl|A_{i_1}\cap\dots\cap A_{i_r}\bigr|+\dotsm$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Calling $[n]=\{m\in \mathbb{N}\mid 1\le m\le n\}$ where $n\in \mathbb{N}$ then $$|\bigcup_{i\in [n]}A_i |=\sum_{J\subseteq [n]}(-1)^{|J |+1 }|\bigcap_{j\in J}A_j|$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Note: This uses nonstandard, but natural, notation for indicator functions. I show this more to show how the formula may be derived from a simple observation.


If we start with a given universe $U,$ which is just a set such that every $A_i$ is a subset of it, then this is just a consequence of $$\left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c$$ or in words, an element is not in the union of all the sets exactly when it is in none of the sets.

At the level of indicator functions, this is $$1 - \bigcup_{i=1}^n A_i = \left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c = \prod_{i=1}^n (1-A_i) \\ \implies \\ \bigcup_{i=1}^n A_i = 1 - \prod_{i=1}^n (1-A_i)$$ which expands to give you precisely the inclusion-exclusion formula quoted by others, but in terms of indicators.

| cite | improve this answer | |
$\endgroup$

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.