Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It seems it's well known that if a sigma algebra is generated by countably many sets, then the cardinality of it is either finite or $c$ (the cardinality of continuum). But it seems hard to prove it, and actually hard to find a proof of it. Can anyone help me out?

share|improve this question
I am not sure I understand the statement of your question. The $\sigma$-algebra on $[0,\infty)$ generated by all sets of the form $[0,n]$, $n\in\mathbb N$ is countable.\\You have mentioned Borel algebra in the title (but not in the body of you're question), so this is probably not what you want. –  Martin Sleziak Oct 8 '11 at 16:02
@Martin, that $\sigma$-algebra doesn't look countable to me. Are you forgetting to close under complementation? –  user83827 Oct 8 '11 at 16:14
Thanks for the correction @ccc. –  Martin Sleziak Oct 8 '11 at 16:54

1 Answer 1

up vote 21 down vote accepted

Let's say the $\sigma$-algebra on $X$ is generated by the sets $A_i \subseteq X$. For each subset $I$ of the natural numbers, consider the set $B_I = \bigcap_{i \in I} A_i \cap \bigcap_{i \notin I} (X \setminus A_i)$. For distinct sets $I$ and $J$, the corresponding sets $B_I$ and $B_J$ are disjoint. Now take cases: either only finitely many of the $B_I$ are nonempty, or infinitely many are. This will show that the $\sigma$-algebra is either finite or has cardinality at least that of the continuum.

To show that the $\sigma$-algebra cannot have cardinality strictly above that of the continuum is a bit more involved. I can't come up with an approach avoiding transfinite induction up the Borel hierarchy. Here's a sketch of what I have in mind:

We build an increasing family $S_\alpha$ of subsets of the power set of $X$, as $\alpha$ ranges over the countable ordinals. In the end, $\bigcup_{\alpha < \omega_1} S_\alpha$ will be a $\sigma$-algebra of size at most continuum containing our countably many generators (in fact, it will be the $\sigma$-algebra they generate, but that's just an added bonus). We start by setting $S_0$ to equal the (countable) set of generators. Given $S_\alpha$, we let $S_{\alpha+1}$ be the collection of subsets which can be written as countable unions of the form $\bigcup_i A_i \cup \bigcup_j (X \setminus B_j)$, where $A_i$ and $B_j$ are chosen from $S_\alpha$. Note that if $|S_\alpha| \leq 2^{\aleph_0}$, then $|S_{\alpha+1}| \leq 2^{\aleph_0}$ as well (since there are only continuum many choices of ways to write the union: this is essentially the cardinal equality $(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}$). For limit ordinals $\lambda$, let $S_\lambda = \bigcup_{\alpha < \lambda} S_\alpha$. This will again satisfy $|S_\lambda| \leq 2^{\aleph_0}$ provided each $S_\alpha$ in the union does.

Finally, we see $\bigcup_{\alpha<\omega_1} S_\alpha$ has cardinality at most that of the continuum, since $\aleph_1 \cdot 2^{\aleph_0} = 2^{\aleph_0}$. Moreover, it is closed under the $\sigma$-algebra operations since any countable sequence of elements is accounted for in some $S_\alpha$ (with $\alpha < \omega_1$).

share|improve this answer
is there a good exposition on the transfinite induction proof? –  Syang Chen Oct 8 '11 at 21:15
I don't have the references on hand, but surely this appears in either Kechris' or Srivastava's text on descriptive set theory (possibly as an exercise). In the meantime I will sketch the argument I have in mind in the answer. –  user83827 Oct 8 '11 at 23:05
Thanks! So it seems impossible to prove it without the axiom of choice? –  Syang Chen Oct 9 '11 at 17:15
Well certainly some amount of choice is required, since (modulo large cardinals) it's consistent with ZF that the usual Borel $\sigma$-algebra on the reals is equinumerous with $2^{2^{\aleph_0}}$ (see, e.g., Gitik's model in which everything is singular). I'm not sure whether, say, uncountable choice principles are really required, even though I tacitly used them in the sketch above. –  user83827 Oct 9 '11 at 20:12
When is induction done over all ordinals and when over countable ordinals only? –  Rudy the Reindeer Jan 16 '12 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.