27
$\begingroup$

Let $X$ is a nonempty set with $m$ members . How many $\sigma$ -algebra can we make on this set?

$\endgroup$
  • 2
    $\begingroup$ I think number of $\sigma$-algebra is less than $2^{n}$ where $n$ is the number of $X$. $\endgroup$ – Vahid May 11 '12 at 8:38
  • $\begingroup$ @Alizter I see you opened a bounty because the question has not received enough attention. Do you want my answer to be more detailed? $\endgroup$ – Davide Giraudo Apr 14 '15 at 12:27
  • $\begingroup$ @DavideGiraudo I think that would be a good idea. I also think that this question is applicable to a greater audience so perhaps some simpler notation and explanation may be in order. Thank you for responding :) $\endgroup$ – Ali Caglayan Apr 14 '15 at 16:31
22
$\begingroup$

Short answer. You can make as much $\sigma$-algebras as partitions on $X$.

Formal verification. 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 $\mathcal A$ 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 is a finite intersection), and that will give you a unique partition.

Indeed, define the equivalence relation $x\sim y$ if and only if $A_x=A_y$. It gives a partition, and it is 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.

$\endgroup$
  • $\begingroup$ Why is this correspondence bijective? $\endgroup$ – saeed sani May 11 '12 at 11:44
  • $\begingroup$ I've added the details. $\endgroup$ – Davide Giraudo May 11 '12 at 15:47
  • 2
    $\begingroup$ What about when X is countably infinite? Does it still work? That intersection of elements of the sigma-algebra would no longer be finite, correct? $\endgroup$ – sloth Sep 11 '15 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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