14
$\begingroup$

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$?

3 Answers 3

15

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|}$.

  • 0
    How many sets do you mean to include in $M_x = \cap_{M \in \Sigma, x \in M} M$. I.e. are there many $M$s? What is the set $M_x$?2015-12-17
  • 0
    I'm not sure what you are asking. The set $M_x$ is, as above, the intersection of all sets in $\Sigma$ that contain $x$.2015-12-17
  • 0
    "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". Why is this true? Why is every element of $\Sigma$ an union of of some elements?2016-01-06
  • 0
    By definition, if $x \in M$, then $x \in M_x \subset M$. Hence $M \subset \cup_{x \in M} M_x \subset M$. Since the $M_x$ form a partition of $X$, the union is disjoint.2016-01-06
  • 0
    But why does it lead to $|\Sigma|=2^{|\Sigma|}$? Surely one could "partition" in other sizes than 2?2016-01-23
  • 0
    The number of distinct subsets of a set of size $n$ is $2^n$.2016-01-23
  • 0
    Where can I find a proof for that?2016-01-23
  • 0
    It is combinatorial, there are $\binom{n}{k}$ sets of size $k$, so the total is $\sum_{k=0}^n \binom{n}{k} = (1+1)^n = 2^n$.2016-01-23
  • 0
    It's weird that one doesn't need to consider the (closure under) complements and unions (part of the def. of $\sigma$-algebra) at all, merely some abstract elements?2016-01-23
  • 0
    All $\sigma$-algebras are closed under countable unions and intersections, why would that be weird? The only trick here is to find the 'atoms' of the $\sigma$-algebra.2016-01-23
  • 0
    Could you expand on the explanation that the sets must be disjoint? I'm finding it hard to see why the set difference being strictly smaller would contradict the definition of $M_x$ or $M_y$.2017-04-22
  • 0
    If $M_x,M_y$ overlap but are not the same then by construction there is some set that contains $x$ but not $y$ (or vice versa) which is a contradiction.2017-04-22
  • 0
    Thank you, much clearer now.2017-04-24
  • 0
    Although, why is this a contradiction? Why does the definition of $M_x$ or $M_y$ dictate that there cannot be an element of $M_x$ that isn't in $M_y$?2017-04-24
  • 0
    It doesn't, it says that they are either disjoint or the same. If they overlap, they must be the same, if not there would be a smaller element that contains $x$ (or $y$) which would contradict the definition of $M_x$ (or $M_y$).2017-04-24
  • 0
    The idea is that there are subsets ('atoms') that cannot be 'separated' by elements of the $\sigma$-algebra.2017-04-24
7

Here's a different argument. Suppose $\mathcal{B}$ is a $\sigma$-algebra of subsets of some set $X$, or even just an algebra. Define an addition operation on $\mathcal{B}$ by $A+B=(A\setminus B)\cup(B\setminus A)$ (this operation is also known as "symmetric difference"). Straightforward computations show that this operation is commutative and associative, has the empty set as an identity, and satisfies $A+A=\emptyset$ for all $A\in\mathcal{B}$. This operation thus makes $\mathcal{B}$ an abelian group, and it is in fact a vector space over the field $\mathbb{Z}/2$ since $A+A=\emptyset$ for all $A$.

Now we just use linear algebra. Every vector space over $\mathbb{Z}/2$ has a basis. If $\mathcal{B}$ is finite, the basis is finite, so $\mathcal{B}$ is isomorphic to the vector space $(\mathbb{Z}/2)^n$ for some $n$. In particular, $\mathcal{B}$ has $2^n$ elements.

4

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.

  • 0
    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.2012-08-12