# Prove the inclusion-exclusion formula

We just touched upon the inclusion-exclusion formula and I am confused on how to prove this: $|A ∪ B ∪ C| =|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$

We are given this hint: To do the proof, let’s denote $X = A ∪ B$, then $|(A ∪ B) ∪ C| = |X ∪ C|$, and we can apply the usual subtraction rule (you will have to apply it twice).

That just made me even more confused. I was hoping someone can guide me through this, or explain

$|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|$

Now, $|A\cup B|=|A|+|B|-|A\cap B|$

$$\text{and }|(A\cup B)\cap C|=|(A\cap C)\cup (B\cap C)|=|(A\cap C)|+|(B\cap C)|-|(A\cap C)\cap (B\cap C)|=|(A\cap C)|+|(B\cap C)|-|A\cap B\cap C|$$

The "subtraction rule" is the inclusion-exclusion principle for two sets: $$|A\cup B| = |A| + |B| - |A\cap B|$$ Just apply the hint without thinking: \begin{align*} |A\cup B\cup C| & = |X\cup C| = |X| + |C| - |X\cap C| \\ & = |A\cup B| + |C| - |(A\cup B) \cap C| \\ & = |A| + |B| - |A\cap B| + |C| - |(A\cap C) \cup (B\cap C)| \\ & = |A| + |B| + |C| - |A\cap B| - (|A\cap C| + |B\cap C| - |(A\cap C) \cap (B\cap C)|) \end{align*} can you finish? (These were actually three applications of said rule).

• $=|(A∩C)|+|(B∩C)|−|A∩B∩C|$, but where does the $X=A∪B$ come into this proof besides the begining Commented Apr 23, 2015 at 16:44
• @Csci319 Nowhere. It only servers as a start to make the first application of IEP for two sets more obvious. Commented Apr 23, 2015 at 16:54
• ok, thanks. Was my final answer correct? Commented Apr 23, 2015 at 17:21
• @Csci319 Not quite. Your term is what the parentheses expand to. The final result will be the given formula, of course. Commented Apr 23, 2015 at 17:44
• am I just one step away? Commented Apr 23, 2015 at 17:53