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 $\Bbb{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 $P_{n}$




\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 \begin{align} \bigcup_{1\leq j\leq n+1}A_j=\left(\bigcup_{1\leq j\leq n}A_j\right)\cup A_{n+1}\end{align}
Applying the indicator function rule,



\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n+1}A_j}=\Bbb{I}_{\bigcup_{1\leq j\leq n}A_{n}}+\Bbb{I}_{A_{n+1}}-\Bbb{I}_{\bigcup_{1\leq j\leq n}A_{n}}\Bbb{I}_{A_{n+1}}\end{align}
So, we apply $P_n$ 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 $P_{n}$, 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
$$\Bbb{I}_{A_j}\Bbb{I}_{A_{n+1}}

=\Bbb{I}_{A_{j}\cap A_{n+1}}$$

and
$$\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\Bbb{I}_{A_{n+1}}
=\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r}\cap A_{n+1}}.$$

These terms provide the indicator functions of the multiple intersections
of the $A_i$ that involve $A_{n+1}$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...