0
$\begingroup$

If given some finite family of finite sets on a finite set $X$, can we say something about the number of $\sigma$-algebras containing that family?

I've seen plenty of examples of $\sigma$-algebras but not much about how many there actually are. For infinite cases, I've always just assumed there were infinitely many, but this may not hold true for the finite case described above?

$\endgroup$
2
  • $\begingroup$ @BLAZE: Not every question involving sets is a question about set theory. $\endgroup$ – Asaf Karagila Sep 26 '15 at 9:12
  • $\begingroup$ Well, since a sigma algebra is determined by the set if contains, it is atleast bounded by $|P(P(X))|=2^{2^{|X|}}$, which shows that the number is not infinite. Infact, by closure under complements, it suffices to determine sets of size less or equal to $|X|/2$, and we can ignore the empty set, so that the bound $2^{2^{|X|/2-1}}$ is better. This fixes two axioms, the only one left being closure under union, for which the combinatorics is harder. $\endgroup$ – max Sep 26 '15 at 9:12
3
$\begingroup$

You can show that every $\sigma$-algebra on a finite set is defined by a partition (and it is isomorphic to $\mathcal P(S)$, where $S$ is the defining partition).

The way you do it is by showing that if $B$ is a $\sigma$-algebra on $X$, then below every non-zero element, there is a minimal positive element (or an atom in the technical jargon). You can then show that the set of atoms is a partition, and that there is a canonical isomorphism between $B$ and $\mathcal P(S)$, where $S$ is the set of atoms.

So the question is how many partitions a finite set has. And the answer is not pretty in the form of Bell numbers.

So in order to count how many $\sigma$-algebras contain a certain family of subsets, you need to ask yourself what partitions can be used to generate the family of sets. I am not aware of any "pretty" combinatorial term for this, but it can't be pretty.

$\endgroup$
9
  • $\begingroup$ @ Asaf Karagila Can you please tell how to prove the arguments you used or suggest somr source where it could be found ie how to prove - 1. every sigma algebra on a finite set is defined by a partition which is isomorphic to P(S) , where S is defining partition. 2 . How to prove that below every non zero element there is a minimal positive element called atom. $\endgroup$ – Tim Oct 2 '19 at 15:11
  • 1
    $\begingroup$ The first thing follows immediately from the second, which follows immediately from the fact that every finite partial order has a minimal element. $\endgroup$ – Asaf Karagila Oct 2 '19 at 21:49
  • $\begingroup$ @ Asaf Karagila can you please tell how 1st will follow from 2nd $\endgroup$ – Tim Oct 10 '19 at 19:31
  • $\begingroup$ Every set in your $\sigma$-algebra is the union of the atoms below it. $\endgroup$ – Asaf Karagila Oct 10 '19 at 19:33
  • 1
    $\begingroup$ I am not "sir". And this is not about combinatorics, but rather writing out the definition. I already told you, every set in a finite $\sigma$-algebra is a union of the atoms below it. $\endgroup$ – Asaf Karagila Oct 10 '19 at 19:45

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.