# Number of distinct sets in a $\sigma$-algebra

Let $F = \{E_1, E_2, ..., E_n\}$ be a collection of $n$ subsets of a set $X$, where $n$ is a positive integer. How many distinct sets could there be in $\sigma(F)$?

Here are my thoughts: the largest that $\sigma(F)$ could be would be the power set of $F$, with $2^n$ elements.
This doesn't satisfy me (and is probably wrong!) because a) our prof said that the answer is much larger than $2^n$, and b) this doesn't use the hypothesis about the sets $E_i$ in any way.
How can I begin to wrap my head around this?

-
Have you looked at small cases, like $n = 2$? Here $2^n$ is correct if $E_1$ and $E_2$ are disjoint, but in general... – Qiaochu Yuan Aug 31 '11 at 16:27
As far as I can tell, $X$ and the sets $E_i$ are arbitrary. So they might not be disjoint. I'll keep brainstorming some concrete examples where they are not disjoint. Thanks, guys. – The Chaz 2.0 Aug 31 '11 at 16:39
You seem to be a bit confused. $\sigma(F)$ is a subset of the power set of $X$, not of the power set of $F$, so the number of elements is not necessarily bounded by the size of the poweer set of $F$. – Arturo Magidin Aug 31 '11 at 17:04
@The Chaz: Indeed we are. I had written up a mostly complete answer when I noticed the homework tag, so I pared it down to an indication of the steps rather than proofs. If you need more fleshed-out arguments, let me know. – Arturo Magidin Aug 31 '11 at 18:05
@Qiaochu: Even $E_1$ and $E_2$ are disjoint and $n=2$, the answer need not be $2^n=4$. For example, if $X=\{1,2,3\}$, $E_1 = \{1\}$, $E_2=\{2\}$, $\sigma(F)$ contains at least $X$, $\emptyset$, $\{1\}$, $\{2\}$, and $\{1,2\}$, which already gives you 5 elements, more than $2^2$. Here, you have $8$ elements in $\sigma(F)$. If $E_1$ and $E_2$ are disjoint and their union is all of $X$, though, then you would be correct that $\sigma(F)$ would have $2^2$ elements. – Arturo Magidin Aug 31 '11 at 19:47

For each $x\in X$, consider the function $\chi_x\colon \mathcal{P}(X)\to \{0,1\}$ given by the "membership function"; that is, $\chi_x(E) = 1$ if $x\in E$, and $\chi_x(E)=0$ if $x\notin E$.

Define a relation on $X$ by $x\sim y$ if and only if $\chi_x(E_i)=\chi_y(E_i)$ for $i=1,\ldots,n$. It is easy to see that this is an equivalence relation.

Question. If $x\sim y$, will $\chi_x(E) = \chi_y(E)$ for all $E\in\sigma(F)$?

To see that the answer is "yes", let $M(x,y)\subseteq \mathcal{P}(X)$ be the set of all subsets of $X$ on which $\chi_x$ and $\chi_y$ agree. Clearly, $F\subseteq M(x,y)$. Prove that $M(x,y)$ is a $\sigma$-algebra.

Then show that we can consider the question in $X/\sim$ instead of $X$ (intuitively: if the sets in $F$ cannot distinguish between $x$ and $y$, then neither can the sets in $\sigma(F)$, so you may as well consider $x$ and $y$ "the same point"). This set has at most $2^n$ elements (the possible values of the membership function on $F$). What does that tell you about $\sigma(F)$? Since it is a subset of $\mathcal{P}(X)$, it has at most $2^{2^n}$ elements.

To verify that this is indeed the best you can say, try to construct a set $X$ with $2^n$ elements, and an $F$ with $n$ such that $\sigma(F)$ is all of $\mathcal{P}(X)$. Hint: Take $X=\{0,1,\ldots,2^{n}-1\}$, and think binary expansion.

-
Many thanks. What is X / ~ ? Also, would it be correct to say that we are reducing the problem to the sigma-algebra of a set with $2^n$ elements? – The Chaz 2.0 Aug 31 '11 at 18:31
@The Chaz: If $A$ is a set and $\sim$ is an equivalence relation, then $A/\sim$ is the set of all equivalence classes of $A$ under $\sim$; basically, one element for every equivalence class. It's called the "quotient of $A$ modulo $\sim$. When we go to $X/\sim$, we are reducing the problem to a set $X$ with at most $2^n$ elements (it could have fewer). – Arturo Magidin Aug 31 '11 at 18:42