Saturday, September 26, 2015

measure theory - Proof of Poincare's Inclusion-Exclusion Indicator Function Formula by Induction



The Poincare's inclusion exclusion formula is given by



\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n}A_j}=\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
where I represents the indicator function. I want to prove this formula by induction. Below is my work



MY TRIAL



Assume true for n, that is for Pn




\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n}A_j}=\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
Now 1jn+1Aj=(1jnAj)An+1
Applying the indicator function rule,



I1jn+1Aj=I1jnAn+IAn+1I1jnAnIAn+1
So, we apply Pn to get



\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n+1}A_j}=&\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1\\=&\sum_{1\leq j\leq n+1}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
\end{align}

Again, applying Pn, to the last term, we get



\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n+1}A_j}=&\sum_{1\leq j\leq n+1}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1\\=&\sum_{1\leq j\leq n+1}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1\end{align}
From here, I'm not sure how to continue. Any help please? Thanks!


Answer



At your last line observe that
IAjIAn+1=IAjAn+1
and
IAi1Ai2AirIAn+1=IAi1Ai2AirAn+1.
These terms provide the indicator functions of the multiple intersections
of the Ai that involve An+1.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...