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
    The idea is that there are subsets ('atoms') that cannot be 'separated' by elements of the $\sigma$-algebra.2017-04-24
8

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