Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
1  
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
2  
@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
1  
@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
show 2 more comments

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.