In a set Omega of points, n subsets A_i (i=1,2,...,n) are…

In a set $\Omega$ of points, $n$ subsets $A_i$ $(i=1,2,\dots,n)$ are distinguished. For any set $C$ define its characteristic function $\chi_C$ by $\chi_C(\omega)=1$ if $\omega\in C$ and $\chi_C(\omega)=0$ otherwise. Prove that using the $A_i$ one can construct sets $B_k$ $(k=1,2,\dots,2^n)$ such that for any bounded function \[ F(\omega)=F\big(\chi_{A_1}(\omega),\dots,\chi_{A_n}(\omega)\big) \] there are constants $C_k$ with \[ F(\omega)=\sum_{k} C_k\,\chi_{B_k}(\omega). \]

Step 1: The answer pattern of a point

For every point $\omega$ form the string

\[ \big(\chi_{A_1}(\omega),\ \chi_{A_2}(\omega),\ \dots,\ \chi_{A_n}(\omega)\big)\in\{0,1\}^n. \]

Its $i$-th entry is $1$ if $\omega\in A_i$ and $0$ if $\omega\notin A_i$. There are $2\cdot2\cdots2=2^n$ possible strings. Number them $\varepsilon^{(1)},\dots,\varepsilon^{(2^n)}$ in any order.

Step 2: Construct the sets $B_k$

For the pattern $\varepsilon=(\varepsilon_1,\dots,\varepsilon_n)$, let $B_\varepsilon$ be the set of points having exactly this pattern:

\[ \boxed{B_\varepsilon = A_1^{\varepsilon_1}A_2^{\varepsilon_2}\cdots A_n^{\varepsilon_n}, \qquad\text{where } A_i^{1}=A_i,\ \ A_i^{0}=\overline{A_i}.} \]

For example, for $n=2$:

Step 3: The sets $B_k$ split $\Omega$

• No overlaps. Two different patterns differ in some position $i$; one of the sets contains the factor $A_i$ and the other $\overline{A_i}$, so their intersection lies in $A_i\overline{A_i}=\varnothing$.
• Everything is covered. Every point $\omega$ has some pattern, namely $(\chi_{A_1}(\omega),\dots,\chi_{A_n}(\omega))$, and it belongs to the set of that pattern.

So every point lies in exactly one $B_k$, which means

\[ \sum_{k=1}^{2^n}\chi_{B_k}(\omega) = 1 \quad\text{for every }\omega. \]

(Some $B_k$ may be empty; this does no harm.)

Step 4: $F$ is constant on each $B_k$

If $\omega\in B_k$, where $B_k$ has pattern $\varepsilon^{(k)}$, then $\chi_{A_i}(\omega)=\varepsilon^{(k)}_i$ for every $i$. Hence

\[ F(\omega) = F\big(\varepsilon^{(k)}_1,\dots,\varepsilon^{(k)}_n\big) =: C_k, \]

a number that depends only on $k$, not on which point of $B_k$ we took.

Step 5: The representation

Define $C_k=F(\varepsilon^{(k)})$ as in Step 4. Take any point $\omega$ and let $B_j$ be the unique set containing it. In the sum, $\chi_{B_j}(\omega)=1$ and all other $\chi_{B_k}(\omega)=0$, so

\[ \sum_{k=1}^{2^n}C_k\chi_{B_k}(\omega) = C_j = F(\omega). \]

\[ \boxed{F(\omega)=\sum_{k=1}^{2^n}F\big(\varepsilon^{(k)}\big)\,\chi_{B_k}(\omega).} \quad\blacksquare \]

The function $F$ takes at most $2^n$ values, so it is automatically bounded; the word "bounded" in the statement is not really needed.

Step 6: An example with $n=2$

Let $F(\omega)$ = the number of the sets $A_1$, $A_2$ that contain $\omega$, i.e. $F=\chi_{A_1}+\chi_{A_2}$. Its values on the four pieces are $0,1,1,2$, so

\[ \chi_{A_1}+\chi_{A_2} = 0\cdot\chi_{\overline{A_1}\,\overline{A_2}} + 1\cdot\chi_{A_1\overline{A_2}} + 1\cdot\chi_{\overline{A_1}A_2} + 2\cdot\chi_{A_1A_2}. \]

Similarly, $\chi_{A_1+A_2} = \chi_{A_1\overline{A_2}}+\chi_{\overline{A_1}A_2}+\chi_{A_1A_2}$ and $\chi_{A_1\triangle A_2}=\chi_{A_1\overline{A_2}}+\chi_{\overline{A_1}A_2}$.

Step 7: Why this matters in probability

The sets $B_k$ are the smallest "building blocks" (atoms) that can be made from $A_1,\dots,A_n$: every event built from the $A_i$ by sums, products and complements is a sum of some of the $B_k$. And every random variable that depends only on which of the events $A_i$ occurred is a simple random variable $\sum C_k\chi_{B_k}$ — this is the starting point for defining expected values.