Is it possible to prove the noncompleteness of the BorelLebesgue 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 NonBorel sets without axiom of choice, but I was unable to really prove it.

$\begingroup$ 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 nonBorel subset of the Cantor set, which is null and hence Lebesgue measurable. $\endgroup$ – Nate Eldredge Mar 25 '16 at 5:09
Countable choice is sufficient to prove that there is a nonBorel set, since under countable choice, the collection of sets of reals with a Borel code (which is a wellfounded 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 countablechoice 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 nonBorel 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.

$\begingroup$ To complete the argument about the noncompleteness of the measure, this implies there is a subset of the Cantor set which is not Borel, and therefore the measure is not complete. $\endgroup$ – Asaf Karagila Mar 25 '16 at 9:17

$\begingroup$ Great answer yet again. Just a supplementary question : how can this implies that there is a nonBorel set included in the Cantor set ? $\endgroup$ – Michael Mar 25 '16 at 23:38

$\begingroup$ 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. $\endgroup$ – Joel David Hamkins Mar 26 '16 at 0:11