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](https://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice), but I was unable to really prove it. 



Non-completeness of the Borel-Lebesgue measure and countable choice
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.


Once you know that every Borel set has a Borel code, this gives you a surjection from the reals onto the Borel sets, and so by Cantor's theorem there must be a non-Borel set of reals, since every Borel code is coded by a real, but the reals do not surject onto the power set of the reals. 


