$C$ is a collection of subsets of $\Omega$ of cardinality $|C| = n$. Show that $|\sigma(C)| \leq 2^{2^n}$

62 Views Asked by At

The question is the following:

For an arbitrary set $\Omega$, assume that $\mathcal{C}$ is a collection of subsets of $\Omega$ of cardinality $|\mathcal{C}| = n$. Show that $|\sigma(\mathcal{C}) |\leq 2^{2^n}$

Also, there is a provided hint saying that

Assume first that the events in $\mathcal{C}$ are disjoint and cover $\Omega$.

and I can't get this hint. Any help is appreciated!!

1

There are 1 best solutions below

2
On BEST ANSWER

Suppose $\mathcal{C} = \{C_1, C_2, \ldots, C_n\}.$ Then there are at most $2^n$ sets of the form $$A_1 \cap A_2 \cap \ldots \cap A_n$$ where $A_i$ is either $C_i$ or $\Omega\setminus C_i.$ Importantly, these sets are disjoint, they cover $\Omega,$ and the [sigma] algebra generated by them is $\sigma(\mathcal{C}).$ [You should show all three of these points, none should take long]

For practical reasons, let's collect these $A_1\cap\cdots\cap A_n$ into a new set $$\mathcal{B} = \{B_1, B_2, \ldots, B_m\}$$ where we have noted that $m\leq 2^n,$ the elements of $\mathcal{B}$ are disjoint and cover $\Omega,$ and $\sigma(\mathcal{B}) = \sigma(\mathcal{C}).$ Further, we may assume $\emptyset \not\in \mathcal{B},$ as this won't change $\sigma(\mathcal{B}).$

Now I'll leave it to you to show that in this scenario (where $\mathcal{B}$ is a partition of $\Omega$) the elements of $\sigma(\mathcal{B})$ are unions of elements of $\mathcal{B}.$ That is, you need to show $$X \in \sigma(\mathcal{B}) \iff \exists I \subseteq \{1,2,\ldots,m\} \text{ such that } X = \bigcup_{i\in I} B_i$$

This allows us to conclude $$|\sigma(\mathcal{C})| = |\sigma(\mathcal{B})| = 2^m \leq 2^{2^n}$$