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 $X$ is a nonempty set with $m$ members . How many $\sigma$ -algebra can we make on this set?

share|improve this question
1  
I think number of $\sigma$-algebra is less than $2^{n}$ where $n$ is the number of $X$. –  Vahid May 11 '12 at 8:38
add comment

1 Answer 1

Let $\mathcal A$ be the collection of all the algebras over $X$, and let $\Pi$ be all the partitions of $X$ (which consist of non-empty sets). There is a bijective correspondence between $X$ and $\Pi$. Indeed, for a partition $P\in \Pi$, consider $\mathfrak A_{\Pi}$ the algebra generated by $\{A_1,\ldots,A_k\}$, the elements of $P$, i.e. $\mathfrak A_{\Pi}$ consists of the set $\bigcup_{j\in J}A_j$, where $J\subset \{1,\ldots,k\}$. To see that this correspondence is bijective, given an algebra $\mathfrak A$, you can define for all $x\in X$ the set $A_x:=\bigcap_{A\in \mathfrak A,x\in A}A$ (it's a finite intersection), and that will give you an unique partition.

Indeed, define the equivalence relation $x\sim y$ if and only if $A_x=A_y$. It gives a partition, and it's the unique one. If $P=\{S_1,\ldots,S_m\}$ works, then $A_x=S_{i(x)}$ for some $i(x)$, and you can check that this partition consists of the equivalence classes of $\sim$.

So the problem is to enumerate the number of partitions of a set which has $m$ elements. You will have to use Bell's numbers.

share|improve this answer
    
Why is this correspondence bijective? –  saeed sani May 11 '12 at 11:44
    
I've added the details. –  Davide Giraudo May 11 '12 at 15:47
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.