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

## 4 Answers

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 '16 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 '16 at 5:56
• But why does it lead to $|\Sigma|=2^{|\Sigma|}$? Surely one could "partition" in other sizes than 2? – mavavilj Jan 23 '16 at 16:12

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.

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

I think all the above answers are wrong, since, in adittion to all the unions and intersections, you have to count all the possible differences and symmetric differences as well as their complements. For instance, for n=2, you will have 16 sets instead of 4. I think it should be 2^{2^n} instead of 2^n.