It is well known that proving the existence of measurable sets or functions requires the axiom of choice, which means that it is consistent with ZF that all functions $\mathbb R \to \mathbb R$ are measurable. However, in this answer it is argued that there are only continuum many measurable functions, an apparent contradiction as the set of all functions $\mathbb R \to \mathbb R$ has a cardinality greater than the continuum.

Clearly there's some use of axiom of choice somewhere here that resolves the apparent contradiction, but I really don't see it. Where is AoC used and what's going on?

  • 1
    $\begingroup$ Point of order: ZF + "all functions $\mathbb{R} \to \mathbb{R}$ are Lebesgue measurable" is equiconsistent with ZF + "an inaccessible cardinal exists". So it is strictly stronger than ZF in terms of consistency strength. $\endgroup$ Dec 1, 2021 at 21:07
  • 2
    $\begingroup$ You have to distinguish between different types of measurability: Borel-measurability is rather narrow, and $\mathsf{ZF}$ does in fact prove that there are non-Borel-measurable functions (as long as the right notion of "Borel" is used here - see this old answer of mine). $\endgroup$ Dec 1, 2021 at 21:11
  • $\begingroup$ @NoahSchweber Do you want to make an answer from that? $\endgroup$
    – Alice Ryhl
    Dec 2, 2021 at 10:58
  • $\begingroup$ Does this answer your question? There is a $\Sigma^1_1$ universal set and this is not Borel. Where did we use the axiom of choice? $\endgroup$
    – Peter O.
    Dec 28, 2021 at 2:46

1 Answer 1


Belatedly turning my comment into an answer, per the OP's request:

There are different types of measurability. While it is consistent with $\mathsf{ZF}$ (relative to large cardinals) that every function is measurable in the Lebesgue sense, the result you cite is about Borel measurability. Indeed, $\mathsf{ZF}$ proves that there are non-Borel-measurable functions.

... As long as we define "Borel" in the right way. There are two obvious notions of Borel-ness: "element of the smallest $\sigma$-algebra containing the open sets" and "having an explicit Borel code." $\mathsf{ZF}$ proves that most sets of reals are not Borel in the latter sense, but is consistent with all sets being Borel in the former sense. See this old answer of mine (and note that the terminology used there is nonstandard).


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.