Exercise 1.4.34 (Inclusion-exclusion principle)

Question

Let $(X,\mathcal{B},\mu)$ be a measure space, and let $A_1,\ldots,A_n$ be a sequence of $\mathcal{B}$-measurable sets with finite measure. Show that
$$\mu\left(\bigcup_{i=1}^{n}A_iight) = \sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \mu\left(\bigcap_{i\in J}A_iight).$$

Elu Thingol · Accepted Answer

We use the equivalent integral formulation of the measure. By \href{./exercise_1-4-33}{Exercise 1.4.33} we have
\begin{align*}
	\mu\left(\bigcup_{i=1}^{n}A_iight) 
	&= \mathrm{Simp}\int_{\mathbb{R}^{d}}x{1_{\bigcup_{i=1}^{n}A_i}}\
\end{align*}
It is easy to verify that $1_{\bigcup_{i=1}^{n}A_i}(x) = 1 - \prod_{i=1}^{n}(1-1_{A_i}(x))$ for any $x\in X$. Thus,
\begin{align*}
	&= \mathrm{Simp}\int_{\mathbb{R}^{d}}x{\left(1 - \prod_{i=1}^{n}1_{A_i}ight)}\
\end{align*}
We now record a useful property $1 - \prod_{i=1}^{n}1_{A_i} = \sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod 1_{A_i}$ (*).
\begin{align*}
	&= \mathrm{Simp}\int_{\mathbb{R}^{d}}x{\left(\sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod 1_{A_i}ight)}\
\end{align*}
This is a sum over a finite number of functions; by  \href{./exercise_1-4-33}{Exercise 1.4.33 (iii, iv)} we employ the finite additivity of the simple integral:
\begin{align*}
	&= \sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \mathrm{Simp}\int_{\mathbb{R}^{d}}x{ \prod 1_{A_i}}\
\end{align*}
It can be verified that $\mu(\bigcap_{i=1}^{n}{A_i}) =\mathrm{Simp}\int_{\mathbb{R}^{d}}x{ \prod 1_{A_i}}$; thus,
\begin{align*}
      &= \sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \mu\left(\bigcap_{i=1}^{n}{A_i}ight)
\end{align*}
as desired.\par

(*) We shortly verify the property $1 - \prod_{i=1}^{n}1_{A_i} = \sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod 1_{A_i}$.
\begin{itemize}
	\item (induction base) We have $(1-1_{A_1})\cdot (1-1_{A_2}) = 1 - 1_{A_1} - 1_{A_2} + 1_{A_1}1_{A_2}$.
  \item (induction step) We have
  \begin{align*}
		\left(1 - \prod_{i=1}^{n}1_{A_i}ight) \cdot \left(1-1_{A_{n+1}}ight) 
		&=  \left(\sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod_{i=1}^{n} 1_{A_i}ight) \cdot \left(1-1_{A_{n+1}}ight)\
		&=\sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod_{i=1}^{n} 1_{A_i} - \sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod_{i=1}^{n} 1_{A_i} \cdot 1_{A_{n+1}}\
		&=\sum_{J\subseteq\{1,\ldots,n\},J 
eq \emptyset} (-1)^{\#J-1} \cdot \prod_{i=1}^{n} 1_{A_i} + \sum_{J'\subseteq\{1,\ldots,n,n+1\},J' 
eq \emptyset} (-1)^{\#J'-1} \cdot \prod_{i=1}^{n+1} 1_{A_i}\
		&=\sum_{J'\subseteq\{1,\ldots,n+1\},J 
eq \emptyset} (-1)^{\#J'-1} \cdot \prod_{i=1}^{n+1} 1_{A_i}
	\end{align*}
	\end{itemize}

Exercise 1.4.34 (Inclusion-exclusion principle)

Answers

Comments

Exercise 1.4.34 (Inclusion-exclusion principle)

Answers

Comments

Add answer