Proving a more general variant of the inclusion-exclusion principle

combinatoricsinclusion-exclusion

There are several questions and answers about the inclusion-exclusion principle, e.g. here, here or here.
Similarly, I found a lot of proofs, e.g. induction, comparing both sides, … . There is another approach, however, that I grapple with at the moment:

Let $(\Omega, \mathcal{F}, P)$ be a probability space and $A_i \in \mathcal{F}, i \in I = \{1, \ldots, n\}$. For $J \subset I$ define
$$S_J = \bigcap_{j \in J} A_j \cap \bigcap_{j \in I\setminus J} A_j^c$$

Apparently, one can show now that $\bigcap_{k \in K} A_k = \dot{\bigcup}_{K \subset J \subset I} S_J$ for all $K \subset I$.
This relation, especially the disjointness of the $S_J$ is not immediately clear to me formally.

Building on this result, one can then show that for all $J \subset I$ it holds that

$$ P(S_J) = \sum\limits_{K: J \subset K \subset I} (-1)^{\vert K \setminus J \vert} P(\bigcap_{k \in K} A_k) $$

Then, setting $J = \emptyset$, we recover the usual inclusion-exclusion principle.

Besides the clarification on the disjointness of the $S_J$, I would like to better grasp what is going on here in terms of intuition or visual representation.
The usual inclusion-exclusion principle is nicely illustrated with the help of Venn diagrams, for example, and how many times elements are counted on both sides of the equation.
In the above approach, I don't yet see visually how the definition of the $S_J$ fits in this framework of intersections and unions.

Best Answer

For each $\omega\in\Omega$ let $J(\omega)=\{j\in I:\omega\in A_j\}$, and note that $\omega\in S_{J(\omega)}$. In fact, $J(\omega)$ is the unique $J\subseteq I$ such that $\omega\in S_J$. To see this, let $J$ be any subset of $I$ different from $J(\omega)$, and suppose first that there is a $j\in J(\omega)\setminus J$. Then $\omega\in A_j$, so $\omega\notin\Omega\setminus A_j$; and by definition $S_J\subseteq\Omega\setminus A_j$, so $\omega\notin S_J$. Now suppose that there is a $j\in J\setminus J(\omega)$. Then $S_J\subseteq A_j$, but $\omega\in\Omega\setminus A_j$, so again $\omega\notin S_J$. Thus, $\omega\in J$ iff $J=J(\omega)$, and the sets $S_J$ are pairwise disjoint.

In fact each $S_J$ corresponds to one of the atomic regions in the Venn diagram. $S_\varnothing$, for instance, is the region outside all of the sets, and $S_I$ is the intersection of all of the sets. In a simple Venn diagram with $3$ sets, $A_1,A_2$, and $A_3$, $S_{\{1,3\}}$ is the set of points inside $A_1\cap A_3$ but outside $A_2$. Each of the atomic regions is uniquely identified by the collection of sets containing it: it is inside all of those and outside all of the rest.

Now suppose that $\omega\in\bigcap_{k\in K}A_k$. Then $K\subseteq J(\omega)$, and $\omega\in S_{J(\omega)}\subseteq\bigsqcup_{K\subseteq J\subseteq I}S_J$. Conversely, if $\omega\in\bigsqcup_{K\subseteq J\subseteq I}S_J$, then $K\subseteq J(\omega)$, and $\omega\in\bigcap_{k\in K}A_k$. Thus, $\bigcap_{k\in K}A_k=\bigsqcup_{K\subseteq J\subseteq I}S_J$.

Related Question