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.

I have been asked to prove that the number of elements in a finite sigma algebra over a set $X$ is $2^n$ for some integer $n$. How do I go about this problem? I have no idea where to start. Thanks in advance for any ideas.

Do I need to prove that given a set $F$, $\sigma(F)$ is actually a power set of some set say $S$?

share|improve this question
    
+1, nice question! –  Salech Alhasov Aug 12 '12 at 6:59

3 Answers 3

Note that a finite $\sigma$-algebra $\mathcal{A}$ has minimal nonempty elements. Show that every element of $\mathcal{A}$ is a union of these minimal elements.

share|improve this answer
    
To clarify: If you manage to prove Arthur Fischer's claim. Then let $A_1$, ..., $A_n$ be these finitely many minimal elements. To each binary sequence $\sigma$ of length associated it with the set $\bigcup_{\sigma(n) = 1} A_n$. So there are $2^n$ elements in this sigma algebra. –  William Aug 12 '12 at 5:34

Here, in page 4 you will find a proof and a efficiant algorithm finding $n$.

Good luck!

share|improve this answer

Let $\Sigma$ be the $\sigma$-algebra. Choose $x \in X$, and define $M_x = \cap_{M \in \Sigma, x \in M} M$. Clearly $M_x \neq \emptyset$, and $M_x \in \Sigma$.

Furthermore, the collection $F = \{M_x \} \subset \Sigma$ is a partition of $X$ (and finite, of course). To see this, suppose $M_x \cap M_y \neq \emptyset$. Then we must have $M_x = M_y$, or else either $M_x \setminus M_y $ or $M_y \setminus M_x $ would be strictly smaller sets contradicting the definition of either $M_x$ or $M_y$.

Furthermore, it is clear that if $M \in \Sigma$, then $M = \cup_{x \in M} M_x$, hence every element of $\Sigma$ is the (disjoint) union of members of $F$ (the empty set taken as the union of no members of $F$), hence $|\Sigma| = 2^{|F|}$.

share|improve this answer

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.