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. 
 A: 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. 
