叶卢庆的博客分享 http://blog.sciencenet.cn/u/Yaleking 这个博客不再更新.我的新博客在 blogmath.org

博文

A proof of inclusion-exclusion principle

已有 3145 次阅读 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://wap.sciencenet.cn/blog-604208-816700.html

上一篇:线性映射的复合
下一篇:最小二乘法
收藏 IP: 183.138.205.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-4 21:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部