|||
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). }$
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-4 21:13
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社