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?

  • $\begingroup$ 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. $\endgroup$ – Martin Sleziak Oct 8 '11 at 16:02
  • 6
    $\begingroup$ @Martin, that $\sigma$-algebra doesn't look countable to me. Are you forgetting to close under complementation? $\endgroup$ – user83827 Oct 8 '11 at 16:14
  • 1
    $\begingroup$ Thanks for the correction @ccc. $\endgroup$ – 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$).

  • $\begingroup$ is there a good exposition on the transfinite induction proof? $\endgroup$ – Syang Chen Oct 8 '11 at 21:15
  • 1
    $\begingroup$ 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. $\endgroup$ – user83827 Oct 8 '11 at 23:05
  • $\begingroup$ Thanks! So it seems impossible to prove it without the axiom of choice? $\endgroup$ – Syang Chen Oct 9 '11 at 17:15
  • 1
    $\begingroup$ @Xianghong: For the hierarchy to be longer than $\omega_2$ you would need both $\omega_1$ and $\omega_2$ to be singular. This is approximately a Woodin cardinal in consistency strength. $\endgroup$ – Asaf Karagila Oct 21 '11 at 9:02
  • 2
    $\begingroup$ When is induction done over all ordinals and when over countable ordinals only? $\endgroup$ – Rudy the Reindeer Jan 16 '12 at 14:36

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.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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