Cardinality of Borel sigma algebra

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?

-
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

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

-
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