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 

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