In this post,I prove inclusion-exclusion principle inductively.This principle can be found at Exercise 33 in Terence Tao's post 245A, Notes 3: Integration on abstract measure spaces, and the convergence theorems.

 

 (Inclusion-exclusion principle) Let $ {(X, {\mathcal B}, \mu)}$ be a measure space, and let $ {A_1, \ldots, A_n}$ be $ {{\mathcal B}}$-measurable sets of finite measure. Show that

$ {\displaystyle \mu\left( \bigcup_{i=1}^n A_i \right) = \sum_{J \subset \{1,\ldots,n\}: J \neq \emptyset} (-1)^{|J|-1} \mu\left( \bigcap_{i \in J} A_i \right).}$

Proof: Prove by induction.When $ n=1$,the identity clearly holds.Suppose when $ n=k$,the identity also holds.Then when $ n=k+1$,let's see sets $ A_1,\cdots,A_n,A_{n+1}$,we know that

$ {\displaystyle \mu\left( \bigcup_{i=1}^n A_i \right) = \sum_{J \subset \{1,\ldots,n\}: J \neq \emptyset} (-1)^{|J|-1} \mu\left( \bigcap_{i \in J} A_i \right). }$

And clearly,

$ {\displaystyle \mu\left(\bigcup_{i=1}^{n+1}A_i\right)=\mu\left(\bigcup_{i=1}^nA_i\right)+\mu\left(A_{n+1}\right)-\mu\left(A_{n+1}\bigcap\left(\bigcup_{i=1}^nA_i\right)\right). }$

Now we calculate $ \mu\left(A_{n+1}\bigcap(\bigcup_{i=1}^nA_i)\right)$.According to the Morgan law,we have

$ {\displaystyle A_{n+1}\bigcap \left(\bigcup_{i=1}^nA_i\right)=\bigcup_{i=1}^n\left(A_i\bigcap A_{n+1}\right). }$

And

$ {\displaystyle \mu\left(\bigcup_{i=1}^n\left(A_i\bigcap A_{n+1}\right)\right)=\sum_{J\subset\{1,\cdots,n\};J\neq\emptyset}(-1)^{|J|-1}\mu\left(\bigcap_{i\in J}\left(A_i\bigcap A_{n+1}\right)\right). }$

So

$ {\displaystyle \mu\left(A_{n+1}\bigcap\left(\bigcup_{i=1}^nA_i\right)\right)=\sum_{J\subset\{1,\cdots,n\};J\neq\emptyset}(-1)^{|J|-1}\mu\left(\bigcap_{i\in J}\left(A_i\bigcap A_{n+1}\right)\right). }$

So

$ {\displaystyle \mu\left(\bigcup_{i=1}^{n+1}A_i\right)=\mu\left(\bigcup_{i=1}^nA_i\right)+\mu(A_{n+1})-\sum_{J\subset\{1,\cdots,n\};J\neq\emptyset}(-1)^{|J|-1}\mu\left(\bigcap_{i\in J}\left(A_i\bigcap A_{n+1}\right)\right), }$

i.e,

$ {\displaystyle \mu\left(\bigcup_{i=1}^{n+1}A_i\right)=\sum_{J \subset \{1,\ldots,n\}: J \neq \emptyset} (-1)^{|J|-1} \mu\left( \bigcap_{i \in J} A_i \right)+\mu(A_{n+1})-\sum_{J\subset\{1,\cdots,n\};J\neq\emptyset}(-1)^{|J|-1}\mu\left(\bigcap_{i\in J}\left(A_i\bigcap A_{n+1}\right)\right)=\sum_{J \subset \{1,\ldots,n,n+1\}: J \neq \emptyset} (-1)^{|J|-1} \mu\left( \bigcap_{i \in J} A_i \right). }$