Inclusion Exclusion Probability Proof Using a Partition of the Space

Question

Let $A_1, A_2, \dots, A_n \subset \Omega$ be arbitrary subsets of a probability space. Let $P$ be a probability measure on $(\Omega, \mathscr{P}(\Omega))$Denote: $$ s_1=\sum\limits_{i=1}^{\infty} P(A_i), \ s_2=\sum\limits_{1\leq i<j }^{\infty} P(A_i \cap A_j), \ s_3=\sum\limits_{1\leq i < j< k }^{\infty} P(A_i \cap A_j \cap A_k), \dots $$

Prove the inclusion-exclusion formula: $$ P(A_1 \cup A_2 \cup \dots \cup A_n)=s_1 - s_2 + s_3 - \dots + (-1)^{n+1} s_n, $$ using the following.

Partition $\Omega$ into sets $A_1'\cap A_2' \cap \dots \cap A_n'$ where each $A_i'$ is either $A_i$ or $A_i^c$. Then count the number of times a set in the partition occurs in an $s_i$. For example, if $n=2$ the set $A_1\cap A_2$ occurs twice in $s_1$ and once in $s_2$. The following identity will be useful in the proof: $$ \sum\limits_{i=0}^{k} (-1)^i {{n}\choose i} = (-1)^k {{n-1}\choose k}, 1\leq k \leq n. $$

I've looked at a couple of proofs for inclusion-exclusion, but none of the ones that I have found seem to be similar to this approach. I am not sure how this partition could be helpful in calculating $P(A_1\cup A_2 \cup \dots \cup A_n).$

The idea I have so far is the following.

$P(A_1 \cup A_2 \cup \dots \cup A_n)=\sum\limits_j P(A_j^*)$ where $A_j^*$ denotes a set in the collection of the partition that includes all the partition sets, but $A_1^c \cap A_2^c \cap \dots \cap A_n^c$.

Now I believe I somehow want to count the number of times each of the partition sets appears in each $s_i$. I am not sure how to go about this for general $n$.

Any help would be much appreciated.

Answer 1

Claim: $\qquad P(A_1 \cup A_2 \cup \dots \cup A_n)=s_1 - s_2 + s_3 - \dots + (-1)^{n+1} s_n \qquad\qquad\qquad\qquad(1)$

Take any set $B$ in the partition composed of the intersection of $k$ of the $A_i$ sets and $n-k$ of the $A_i^c$ sets, for some $0\leq k\leq n$. It's easy to see that the set $B$ will occur in $s_1\; \binom{k}{1}$ times, in $s_2\; \binom{k}{2}$ times, $\ldots$, and in $s_k\; \binom{k}{k}$ times, and $0$ times in the other values: $s_{k+1},\ldots,s_n$.

Thus, for $k=0$ (which means $B=A_1^c\cap\cdots\cap A_n^c$) set $B$ is counted in the RHS of $(1)\; 0 $ times, and for $1\leq k\leq n,$ the count is:

$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots +(-1)^{k+1}\binom{k}{k} = \binom{k}{0} - (1-1)^k = 1.$$

On the LHS of $(1)$ we have same count: $B$ is counted exactly once if it has at least one of the $A_i$ sets in it, and is counted zero times if it has none of the $A_i$ sets. This proves the result.