Proving a more general variant of the inclusion-exclusion principle

Question

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.

Answer 1

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$.

Answer 2

Note added: This is exactly what Alexander explained in his comment, which I saw after posting my answer.

Here’s a way to think about the sets $S_J$.

First, buy a huge number of stickers with numbers $1$ through $n$ on them. Then go through each $x\in\Omega$ and put an $i$ sticker on $x$ for each event $A_i$ where $x\in A_i$. Call the “sticker-set” of $x$ the set of sticker numbers you put on $x$.

For a set of numbers $J$, the set $S_J$ contains those elements of $\Omega$ whose “sticker-set” is precisely $J$. This follows directly from the definition: $S_J$ contains (via the left intersection) only those elements $x$ that do have $j$-stickers on them for each $j\in J$ and (via the right intersection) that do not have $j$-stickers on them for each $j\notin J$.

The $S_J$ are disjoint, because each $x$ has a well-defined sticker-set.

The “apparently” equality is intuitive: The left side, $\bigcap_{k \in K} A_k$, is the set of $x$ that have a sticker for every $k\in K$ (but possibly some additional stickers). In other words, $\bigcap_{k \in K} A_k$ comprises the elements of $\Omega$ whose sticker-set is $K$ or a superset of $K$. That’s what the right hand side expresses.