# Number of elements in a finite $\sigma$-algebra

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

-
+1, nice question! – Salech Alhasov Aug 12 '12 at 6:59

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

-
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$? – mavavilj Dec 17 '15 at 8:02
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$. – copper.hat Dec 17 '15 at 20:48
"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? – mavavilj Jan 6 at 1:37
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. – copper.hat Jan 6 at 5:56
But why does it lead to $|\Sigma|=2^{|\Sigma|}$? Surely one could "partition" in other sizes than 2? – mavavilj Jan 23 at 16:12

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.

-
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. – William Aug 12 '12 at 5:34

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.

-