I want to generate the smallest $\sigma-$algebra which contains the sets $A_{1},A_{2},…,A_{n}$ which are n arbitrary subsets of $\Omega$ . Also I want to try and estimate the number of sets in the $\sigma-$algebra
My thinking:-
Let us call it $\mathcal{A}$.
Then $\mathcal{A}$ should contain $\phi$ and $\Omega$. these are 2 elements
It should contain each of $A_{i}$ and $A_{i}^{c}$ . So that gives us another $2\cdot \binom{n}{1}=2n$ elements.
Then we have to think about unions of two elements and their complements . Which are of the form $A_{i}\cup A_{j}$ and $(A_{i}\cup A_{j})^{c}$ and also $A_{i}^{c}\cup A_{j}^{c}$ and $(A_{i}^{c}\cup A_{j}^{c})^{c}$ . Which gives me $4\cdot \binom{n}{2}$ sets.
Now I am having trouble as to how to proceed with union of 3 sets. And also after 3 .
Can you please provide me with a method to generate such a sigma algebra such that I can estimate the number of sets ( Many could be double counted , but atleast what we would get is an upper bound).
Edit:- If I mindlessly proceed with the method above . I should get $4\cdot\binom{n}{3}$ elements .
So proceeding this way:-
I should get
$2+2n+4\cdot\binom{n}{2}+4\cdot\binom{n}{3}+…+4\cdot\binom{n}{n-1}+4\cdot\binom{n}{n}$ elements. Is my reasoning at all correct?. Would this be a suitable upper bound?. And would a collection made like this at all be the smallest $\sigma-$algebra ?
Best Answer
Every element $\omega$ of $\Omega$ can be uniquely determined by a binary tuple of length $n$ that tells use whether $\omega$ belongs or not to each of the $n$ sets.
This determines $2^n$ sets that partition $\Omega$, although some of them may be empty, assume there are $s$ that are not-empty.
The smallest $\sigma$-algebra that contains each of the $A_i$ is precisely the sigma-algebra that is formed by the $2^s$ different unions of some of those $s$ subsets.
It is not hard to see that set is a $\sigma$-algebra, since its simply the $\sigma$-algebra induced by that partition.
On the other hand it is not hard to see that each of those $s$ non-empty subsets must be in any $\sigma$-algebra that contains the $A_i$, as each of them is formed by the intersections of $n$ sets, each of which is either $A_i$ or its complement, and since each of those $s$ sets must be in the sigma-algebra we must have that their $2^s$ distinct unions are also in the $\sigma$-algebra.