# Non-completeness of the Borel-Lebesgue measure and countable choice

Is it possible to prove the non-completeness of the Borel-Lebesgue measure on $\mathbb{R}$ (restricted to the Borel $\sigma$-algebra) without the full axiom of choice, but still with Countable Choice ? It seems to be the case when I read Non-Borel sets without axiom of choice, but I was unable to really prove it.

• Surely all you have to do is prove that not all sets are Borel. The same proof will go through for the Cantor set, so you get a non-Borel subset of the Cantor set, which is null and hence Lebesgue measurable. – Nate Eldredge Mar 25 '16 at 5:09

Countable choice is sufficient to prove that there is a non-Borel set, since under countable choice, the collection of sets of reals with a Borel code (which is a well-founded countable tree labeled with the instructions for building a Borel set, so that leaves are labeled with basic open sets and other nodes are labeled with instructions for taking a countable union or a complement) is a $\sigma$-algebra containing the open sets. One uses countable choice to prove that this collection is closed under countable unions, because if each $A_n$ has a Borel code, you can use countable-choice to pick a code $b_n$ for $A_n$ and then glue these codes to together to make a code for $\bigcup_n A_n$. Thus, under countable choice, every Borel set has a Borel code.
• The Cantor set is equinumerous with the reals, and so they have the same size power set. Since we can map the reals surjectively onto the Borel subsets of the Cantor set, but not onto the full power set, there must be ($2^{\mathfrak c}$) many subsets of the Cantor set that are not Borel. – Joel David Hamkins Mar 26 '16 at 0:11