Prove the inclusion-exclusion formula

Question

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

Answer 1

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

Answer 2

$|(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|$$