Yet another corner of the internet

An explicit construction of a $\sigma$-field

$\sigma$-field definition and motivation:

Definition: A $\sigma$-field is a collection of subsets of a set $\Omega$ such that the following hold:

  1. $\Omega \in F$.
  2. if $A \in F$, so is $A^C \in F$.
  3. For any countable collection of sets ${A_i}_{i=0}^\infty$ in $F$ their union is in $F$ as well.

The motivation for this discussion is based on the following problem by Ash:

“Let $A_1,…,A_n$ be arbitraty subsets of $\Omega$. Describe (explicitly) the smallest $\sigma$-field $\mathcal{F}$, containing $A_1,..,A_n$. How many sets are in there $\mathcal{F}$?”

An initial (naive) answer

Indeed, as stated by Ash, given a single subset $A\subset\Omega$ the smallest $\sigma$-field $\mathcal{F}$, containing $A$ is $\set{A, A^c, \Omega,\phi}$.

Following this line - let $A, B$ be subsets of $\Omega$, ofcourse, $\mathcal{F}$ must include their complements $A^c, B^c$ and their intersection - $A\cap{B}=(A^c\cup{B^c})^c$.

How many ways can we generate intersections from sets? Well we can generate intersections of size $1,…,N$ (two, in our case). There are ${N \choose k}$ intersections of size $k$. However in order to generate intersections we may pick $A_i$ or $A_i^c$ so altogether we have $\sum_{i=0}^N{2N \choose i} = 2^{2N-1} + \frac{1}{2}{2N \choose N}$ (Plus another set for $\Omega$).

We note some observations and reflections:

  1. Counting is hard and tedious 😢. Indeed I made a crude mistake while counting the different sets generated. I knew the sum $\sum_{i=0}^{2N}{2N \choose i}$ adds up to $2^{2N}$ so I naively assumed $\sum_{i=1}^N{2N \choose i} = \frac{1}{2}2^{2N}-1=2^{2N-1}-1$. However this is incorrect! As I was uncertain about this assesment I asked GPT and she informed me that indeed the sum is symmetric yet it is symmetric around ${2N \choose N}$! Indeed -

$$ \sum_{i=0}^N{2N \choose i}=\underbrace{{2N \choose 0}+\cdots+{2N \choose N}}_{\text{N terms}}+{2N \choose N}+\underbrace{{2N \choose N+1}+\cdots+{2N \choose 2N}}_{\text{N terms}} $$

Yet since I had added an extra term of ${2N \choose N}$ to the sum it must be accounted for and I must add half of it to the $2^{2N-1}$. The lesson to learn here is when counting sets (Or anything for that matter) dont simply use the statements blindly but reason about the number of terms and if we use some symmetry statement be carefull to take note of how it is used.

  1. The sets generated may not be unique! (e.g. $A\cap{A^c}, B\cap{B^c}$). So the bound reached is rather crude.
  2. The reason why we sum up to $N$ and not $2N$ in the expression above is that (using the “pigeonhole principle”) any intersection containing more than $N$ sets must include both $A_i$ and $A_i^c$ for some integer $1\leq{i}\leq{N}$.

Lets see this line of reasoning in action - First we write our initial sets - $\set{A,B,A^c,B^c}$, their intersections should produce ${4 \choose 1} + {4 \choose 2} + 1 = 4 + 6 + 1 + 1 = 10 + 2 = 12$ sets -

$$ \set{ A,B,A^c,B^c,A\cap{B},A\cap{B^c},A\cap{A^c},B\cap{A^c},B\cap{B^c},A^c\cap{B^c},\Omega,\phi } $$

Similar to the way we generated intersections we can unify these sets in arbitrary ways to create other (larger) sets.

Naively, this is slightly easier to quantify as we can take all subsets of the sets generated previously (we can remove one to account for $\Omega$ and $\phi$) and take their unions to generate these sets. Again, noting that we make create non-unique sets (e.g $A\cup\Omega$, $B\cup\Omega$). Meaning there are $2^{2^{2N-1} + \frac{1}{2}{2N \choose N}-1}$ sets in $\mathcal{F}$. $\square$

GPT Interlude - Everything I wrote above is wrong!! 😢

According to GPT my answer was incorrect because we dont care about “larger” intersections (those with less than $N$ sets) but we only care about the smallest possible (non-empty) intersections of the $N$ sets.

A second interation:

We map an element from the N-set intersection (These are called “atoms” according to GPT) to the binary word of $N$ letters by assigning 0 to an index $i$ if $A_i^c$ appears in the intersection and 1 otherwise. There are $2^N$ such words.

The first thing that came to mind was “These sets are way too small!” - What about the “original” sets we started with (e.g. $A_i$)? - How can they be generated by these “atoms”?

Say we would like to generate $A_i$ from atoms - Indeed suffice to take the following union -

$$ (A_i\cap{}A_1\cap{}A_2\cap\cdots\cap{}A_n)\cup{}(A_i\cap{}A_1^c\cap{}A_2\cap\cdots\cap{}A_n)\cup{}\cdots\cup{}(A_i\cap{}A_1^c\cap{}A_2^c\cap\cdots\cap{}A_n^c) = \\ A_i\cap{}((A_1\cap{}A_2\cap\cdots\cap{}A_n)\cup{}(A_1^c\cap{}A_2\cap\cdots\cap{}A_n)\cup{}\cdots\cup{}({}A_1^c\cap{}A_2^c\cap\cdots\cap{}A_n^c)) = \\ A_i\cap{\Omega}=A_i $$

Why does this work? Since we had had all $2^{N-1}$ atoms of the ($N-1$)-set! By induction - these span $\Omega$ just as well.

Which leads to a bound of $2^{2^N}$. Is this bound tight?

All we need is the intersections to have at least a single unique point in them that way non of the atoms will be empty. So we can build it bottom up! Assume $\Omega=\set{\omega_0,\cdots,w_{2^{N-1}}}$ it would suffice to assign a unique point $\omega_i$ to each of the $2^N$ intersections. Thus by our previous reasoning $|\mathcal{F}| = 2^{2^N}$.

What is $A_i$? from our previous construction it is the union of all the points with one in $i$th bit of their binary expansion!

For example - Lets build our a $\sigma$-field $\mathcal{F}$ on two sets $\set{A_1,A_2}$ such that $|\mathcal{F}|$ will match our bound. Let $\Omega=\set{w_0\cdots{}w_3}$. We assign each point to each of the four intersections $A_1\cap{}A_2,A_1^c\cap{}A_2,A_1\cap{}A_2^c,A_1^c\cap{}A_2^c$ and we map these to the binary strings on two letters as described previously. Thus, as we know from the previous construction $A_1=A_1\cap{A_2^c}\cup{}A_1\cap{A_2}=\set{\omega_1,\omega_3}$. Indeed these are all the sets corresponding to the binary words with one in $i$th bit of their binary expansion!