In my maths notebook, it says that if $A$, $B$, and $C$ are finite sets then: $$ n(A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C) $$ However I don't know how this works properly. It does seem to work based on the previous identities on union of sets (i.e. $n(A ∪ B) = n(A) + n(B) – n(A ∩ B)$). However when I try to visualize it in Venn Diagram form, it just doesn't seem to work. I'm guessing this is because of my misconception between area and count of elements, but I still don't know why it does work. Any sort of help that helps me understand how to think of this equation will be greatly appreciated.
Asked
Active
Viewed 1,114 times
2
-
This is called the inclusion–exclusion principle. – PM 2Ring Jan 05 '20 at 00:37
-
1Use that $A\cup B\cup C=(A\cup B)\cup C$, so apply the formula of $n(X\cup Y)=n(X)+n(Y)-n(X\cup Y)$, where $X=A\cup B$ and $Y=C$. – manooooh Jan 05 '20 at 00:39
2 Answers
7
Here is a $3$ circle Venn diagram. Starting from top to bottom, left to right, I will label the colors:
- $|A ∩ B' ∩ C'|$ ($A$ and nothing else): blue
- $|A ∩ B ∩ C'|$: dark green
- $|A' ∩ B ∩ C'|$ ($B$ and nothing else): green
- $|A ∩ B' ∩ C|$: red
- $|A ∩ B ∩ C|$: brown
- $|A' ∩ B ∩ C|$: orange
- $|A' ∩ B' ∩ C|$ ($C$ and nothing else): pink
For the union of all of these sets, we can only have exactly one of each region.
Notice that: $$ \begin{align} |A| &= \text{blue} + \text{dark green} + \text{red} + \text{brown}\\ |B| &= \text{green} + \text{dark green} + \text{orange} + \text{brown} \\ |C| &= \text{pink} + \text{red} + \text{orange} + \text{brown} \\ |A| + |B| + |C| &= \text{blue} + \text{green} + \text{pink} + 2(\text{dark green} + \text{orange} + \text{red}) + 3\text{brown} \end{align} $$
We need to subtract the overlaps of two circles. $$ \begin{align} |A∩B| &= \text{dark green} + \text{brown}\\ |B∩C| &= \text{orange} + \text{brown} \\ |A∩C| &= \text{red} + \text{brown} \\ |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| &= \text{blue} + \text{green} + \text{pink} + \text{dark green} + \text{orange} + \text{red} \end{align} $$
We need to add that last brown region back.
zhuli
- 2,561
2
Use Venn diagram. First sum $n(A)$, $ n(B)$ and $n(C)$ as you did. Then their intersections in pairs are counted twice, so substract each of them once, i.e. substract $n(A\cap B), n(A\cap C)$ and $ n(B\cap C)$ . Initially you added the triple intersection three times, and later substracted it three times. So you have to add it again, $n(A\cap B\cap C)$.
