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.

  • $\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 non-Borel subset of the Cantor set, which is null and hence Lebesgue measurable. $\endgroup$ Mar 25, 2016 at 5:09

1 Answer 1


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.

  • $\begingroup$ To complete the argument about the non-completeness 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, 2016 at 9:17
  • $\begingroup$ Great answer yet again. Just a supplementary question : how can this implies that there is a non-Borel set included in the Cantor set ? $\endgroup$
    – Michael
    Mar 25, 2016 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$ Mar 26, 2016 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.