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?
 A: 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$).
A: It is easy to prove that the $\sigma$-algebra is either finite or has cardinality at least $2^{\aleph_0}$.
One way to prove that it has cardinality at most $2^{\aleph_0}$, without explicitly using transfinite recursion, is the following.
It is easy to see that it is enough to prove this upper bound for a "generic" $\sigma$-algebra, e.g., for the Borel $\sigma$-algebra of $\{0,1\}^{\omega}$, or for the Borel $\sigma$-algebra of the Baire space $\mathcal{N} = \omega^{\omega}$.
Note that $\mathcal{N}$ is a Polish space, so we can talk about analytic subsets of $\mathcal{N}$.
Every Borel subset is an analytic subset of $\mathcal{N}$ (in fact, $A \subseteq \mathcal{N}$ is Borel if and only if $A$ and $X \setminus A$ are both analytic).
So it is enough to prove that $\mathcal{N}$ has $2^{\aleph_0}$ analytic subsets.
Now use the theorem stating that every analytic subset of $\mathcal{N}$ is the projection of a closed subset of $\mathcal{N} \times \mathcal{N}$.
Since $\mathcal{N} \times \mathcal{N}$ has a countable basis of open subsets, it has $2^{\aleph_0}$ open subsets, so it has $2^{\aleph_0}$ closed subsets.
So $\mathcal{N}$ has $2^{\aleph_0}$ analytic subsets.
The proof using transfinite recursion might be simpler, but I think the analytic subset description gives a slightly different, kind of direct ("less transfinite") view on the Borel sets, that could be useful to know.
