The goal of this post is to prove the inclusion-exclusion principle left as an exercise in (Klenke, 2020), Theorem 1.33.

Theorem: Let $\mathcal{A}$ be a ring and let $\mu$ be a content on $\mathcal{A}$. Let $n \in \mathbb{N}$ and $A_{1}, \dots, A_{n} \ \in \mathcal{A}$ such that $\mu(A_{1} \cup \dots \cup A_{n}) < \infty$. Then the following inclusion and exclusion formulas hold:

\begin{equation} \mu({A_{1} \cup \dots \cup A_{n}}) = \sum_{k=1}^{n} (-1)^{k-1} \sum_{\{i_{1}, \dots, i_{k}\} ⊆ \{1, \dots, n\}} \mu(A_{i_{1}} \cap \dots \cap A_{i_{k}}) \end{equation}

\begin{equation} \mu({A_{1} \cap \dots \cap A_{n}}) = \sum_{k=1}^{n} (-1)^{k-1} \sum_{\{i_{1}, \dots, i_{k}\} ⊆ \{1, \dots, n\}} \mu(A_{i_{1}} \cup \dots \cup A_{i_{k}}) \end{equation}

Here the summation in over all subsets of $\{1, \dots, n \}$ with $k$ elements.

In this post we only prove the first formula (for unions). The proof for the second formula is very similar.

Before going into the proof, I would like to introduce the following notation for the set of all subsets of a set with length $k$.

Definition (k-subset): Let $[n] = \{1, 2, \dots , n\}$. We define $[n]^{k}$ to be the set of all subsets of $[n]$ of size $k$, i.e.: \begin{equation} [n]^{k} ≔ \{X ⊆ [n] \ : \ |X| = k\} \end{equation}

where $|X|$ is the cardinality of $X$. Also note that it is shown in (Klenke, 2020, Lemma 1.31 (i)) that for two sets $A, B \in \mathcal{A}$ such that $\mu(A), \ \mu(B) < \infty$, we have \begin{equation} \mu(A \cup B) = \mu(A) + \mu(B) - \mu(A \cap B) \end{equation}

we shall make use of this in the induction step.

Furthermore, the condition $\mu(A_{1} \cup \dots \cup A_{n}) < \infty$ ensures that all the sets $μ$ operates on in the above formulae have finite content (in the sense, $μ(\cdot) < \infty$), Since content functions on rings are monotone (Klenke, 2020, Lemma 1.31 (ii)).

Proof (using induction on n):

We want to show that: \begin{equation} \mu\biggl(\bigcup\limits_{i \in [n]} A_{i}\biggr) = \sum_{k=1}^{n} (-1)^{k-1} \sum_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \end{equation}

Base step. We prove that the theorem holds for $n = 1$.

\begin{align} \mu\biggl(\bigcup\limits_{i \in [1]} A_{i}\biggr) &= \mu(A_{1}) \\ &= (-1)^{(1-1)} \sum_{I \in [1]^{1}} \mu \biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \\ &= \mu \biggl(\bigcap\limits_{i \in \{1\}} A_{i}\biggr) \\ \end{align}

Induction step. Under the induction hypothesis $\mu\biggl(\bigcup\limits_{i \in [n]} A_{i}\biggr) = \sum\limits_{k=1}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr)$, we must prove $\mu\biggl(\bigcup\limits_{i \in [n + 1]} A_{i}\biggr) = \sum\limits_{k=1}^{n + 1} (-1)^{k-1} \sum\limits_{I \in [n + 1]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr)$

\begin{align} \mu\biggl(\bigcup\limits_{i \in [n + 1]} A_{i}\biggr) &= \mu\biggl(\biggl(\bigcup\limits_{i \in [n]} A_{i}\biggr) \cup A_{n+1}\biggr) \\ &= \mu\biggl( \bigcup_{i \in [n]} A_{i} \biggr) + \mu(A_{n+1}) - \mu\biggl(\biggl(\bigcup_{i \in [n]} A_{i}\biggr)\cap A_{n+1}\biggr) \\ &= \mu\biggl( \bigcup_{i \in [n]} A_{i} \biggr) + \mu(A_{n+1}) - \mu\biggl(\bigcup_{i \in [n]} \biggl(A_{i}\cap A_{n+1}\biggr)\biggr) \\ \end{align}

Where the second to last equality is due to (Klenke, 2020, Lemma 1.31 (i)).

Applying the induction hypothesis:

\begin{align} \mu\biggl(\bigcup\limits_{i \in [n + 1]} A_{i}\biggr) &= \sum\limits_{k=1}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \\ & \quad + \ \mu(A_{n+1}) \\ & \quad - \sum\limits_{k=1}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i} \cap A_{n + 1}\biggr)\biggr) \\ &= -1^{(1-1)} \sum_{I \in [n]^{1}} \mu\biggl(\bigcap_{i \in I} A_{i}\biggr) + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \quad (\text{split the sum for into two: } k = 1, k= 2, \cdots ,n) \\ & \quad + \ \mu(A_{n+1}) \\ & \quad - \sum\limits_{k=1}^{n} (-1)^{k-1} \sum\limits_{I \in [n + 1]^{k+1} \setminus [n]^{k+1}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) \quad (\text{summing over } [n + 1]^{k+1} \setminus [n]^{k} \text{ allows us to take out the intersection with } A_{n+1})\\ &= -1^{(1-1)} \sum_{I \in [n+1]^{1}} \mu\biggl(\bigcap_{i \in I} A_{i}\biggr) + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \quad (\text{combine the first expression with the third}) \\ & \quad + \sum\limits_{k=1}^{n} (-1)^{k} \sum\limits_{I \in [n + 1]^{k+1} \setminus [n]^{k+1}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) \quad ((-1) \times (-1)^{k-1} = (-1)^{k})\\ &= -1^{(1-1)} \sum_{I \in [n+1]^{1}} \mu\biggl(\bigcap_{i \in I} A_{i}\biggr) + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \\ & \quad + \sum\limits_{k=2}^{n+1} (-1)^{k-1} \sum\limits_{I \in [n + 1]^{k} \setminus [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) \quad (\text{reindex start } k \text{ at 2})\\ &= -1^{(1-1)} \sum_{I \in [n+1]^{1}} \mu\biggl(\bigcap_{i \in I} A_{i}\biggr) + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \\ & \quad + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n + 1]^{k} \setminus [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) + (-1)^{(n+1) - 1} \sum\limits_{I \in [n + 1]^{n+1} \setminus [n]^{n+1}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) \quad (\text{split the sum over } k=1 \dots n \text{ and } k = n+1)\\ &= -1^{(1-1)} \sum_{I \in [n+1]^{1}} \mu\biggl(\bigcap_{i \in I} A_{i}\biggr) + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \\ & \quad + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n + 1]^{k} \setminus [n]^{k}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) + (-1)^{(n+1) - 1} \sum\limits_{I \in [n + 1]^{n+1}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr) \quad ([n]^{n+1} = \emptyset )\\ &= -1^{(1-1)} \sum_{I \in [n+1]^{1}} \mu\biggl(\bigcap_{i \in I} A_{i}\biggr) + \sum\limits_{k=2}^{n} (-1)^{k-1} \sum\limits_{I \in [n+1]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr)\\ & \quad + (-1)^{(n+1) - 1} \sum\limits_{I \in [n + 1]^{n+1}} \mu\biggl(\bigcap\limits_{i \in I} \biggl(A_{i}\biggr)\biggr)\\ \end{align}

where in the last step we summed the second and third expressions for $k=2$. Note that $([n+1]^{k}\setminus[n]^{k}) \cup [n]^{k} = [n+1]^{k}$ and they are disjoint.

The three remaining expressions correspond to $k=1, \ k=2$ and $k=n+1$. So it follows that,

\begin{equation} \mu\biggl(\bigcup\limits_{i \in [n + 1]} A_{i}\biggr) =\sum\limits_{k=1}^{n + 1} (-1)^{k-1} \sum\limits_{I \in [n + 1]^{k}} \mu\biggl(\bigcap\limits_{i \in I} A_{i}\biggr) \end{equation}

or equivalently, \begin{equation} \mu({A_{1} \cup \dots \cup A_{n+1}}) = \sum_{k=1}^{n+1} (-1)^{k-1} \sum_{\{i_{1}, \dots, i_{k}\} ⊆ \{1, \dots, n+1\}} \mu(A_{i_{1}} \cap \dots \cap A_{i_{k}}) \end{equation}

which means that if our statement is true for $n$, it is true for $n+1$ as well. This proves the statement is true for natural numbers $n$. $$\tag*{$\blacksquare$}$$

References 

Klenke, A. (2020). Probability theory: A comprehensive course. Springer Nature.