# A proof of inclusion-exclusion principle

ÒÑÓÐ 2577 ´ÎÔÄ¶Á 2014-8-2 22:48 |¸öÈË·ÖÀà:²â¶ÈÂÛ|ÏµÍ³·ÖÀà:¿ÆÑÐ±Ê¼Ç| space, measure, inclusion-exclusion

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

https://blog.sciencenet.cn/blog-604208-816700.html

ÉÏÒ»Æª£ºÏßÐÔÓ³ÉäµÄ¸´ºÏ
ÏÂÒ»Æª£º×îÐ¡¶þ³Ë·¨
ÊÕ²Ø IP: 183.138.205.*| ÈÈ¶È|

Êý¾Ý¼ÓÔØÖÐ...