Borel sigma algebra not containing all subsets of $\mathbb{R}$?

Consider the smallest sigma algebra $\mathscr{B}$ generated by all open subsets of $\mathbb{R}$. One would expect that $\mathscr{B}$ contains all subsets of $\mathbb{R}$, but as it turns out, if we assume the axiom of choice to be true, there are some subsets of $\mathbb{R}$ which don't belong to $\mathscr{B}$. I was hoping if someone could help me out with a proof of the above statement, i.e, $\mathscr{B}$ does not contain all subsets of $\mathbb{R}$.

• This is answered elsewhere on this site, but a short sketch is this: $\aleph_1=\omega_1$, the first uncountable cardinal, is regular (assuming choice), that is, countable unions of countable ordinals result in countable ordinals. This shows that $\mathcal B=\bigcup_{\alpha<\omega_1}\mathcal B_\alpha$, where each $\mathcal B_\alpha$ is the result of considering complements of the sets in the previous stages, and countable unions of such sets, with $\mathcal B_0$ being the collection of open sets. (Regularity is used to argue that this union $\bigcup_{\alpha<\omega_1}\mathcal B_\alpha$ (Cont.) – Andrés E. Caicedo Mar 27 '15 at 16:42
• "One would expect that $\mathscr{B}$ contains all subsets of $\mathbb{R}$": why on Earth would one expect that?! (Sorry for cutting the previous comment in half) – Najib Idrissi Mar 27 '15 at 16:46
• @NajibIdrissi Probably because it is impossible to exhibit a set that is not Borel via an argument that does not invoke the axiom of choice. So, as long as everything one does is "explicit", only Borel sets are reached. – Andrés E. Caicedo Mar 27 '15 at 16:48
• @PhoemueX It is true, I have addressed this topic a few times here and on Mathoverflow, so references should not be hard to find. Anyway, it is consistent with set theory without choice that $\mathbb R$ is a countable union of countable sets, in which case all sets of reals are Borel. – Andrés E. Caicedo Mar 27 '15 at 19:17
• @AndresCaicedo: Yes, sorry, I just read that in the thread I linked. But at least there are (much) weaker forms of choice than AC (like DC) which imply that not all sets are Borel measurable. – PhoemueX Mar 27 '15 at 19:19