Most functions are measurable

Question

My professor once said that if you did not use the axiom of choice to build a function $f : \mathbb{R}^n \to \mathbb{R}^m$, then it is Lebesgue measurable. To what extent this is true?

Answer 1

It is not strictly true from a rigid formal viewpoint. Consider the following property: $$ \psi(x) \equiv (\mathrm{AC} \land x\text{ is a Vitali set}) \lor (\neg\mathrm{AC} \land x = \mathbb R) $$ where $\rm AC$ is the formal statement of the Axiom of Choice. ZF proves $\exists x.\psi(x)$, so let $A$ be some set such that $\psi(A)$, and define $f$ to be its indicator function.

We have now defined $f$ without assuming that the axiom of choice is true, but $f$ is not guaranteed to be measurable nevertheless.

Of course, this definition smells strongly of cheating, and your professor's claim is for practical purposes true in the sense that if you refrain from such deliberate cheating, then you won't be able to define a non-measurable function without appealing to the Axiom of Choice. However, it turns out to be extremely hard to define rigorously what "cheating" means here (there are less blatant ways of cheating than the above, which we also need to exclude), in a way that would allow the professors claim to be formally proved.

---

If someone objects that the above $\psi$ does not determine $A$ (and hence $f$) uniquely, we can instead take $$ \bar\psi(x) \equiv (\mathbf V=\mathbf L \land x\text{ is the first Vitali set}) \lor (\mathbf V\ne\mathbf L \land x=\mathbb R) $$ where $\mathbf V=\mathbf L$ is Gödel's Axiom of Constructibility, and "first" means first according to the standard definable well-ordering of $\mathbf L$. Then ZF proves $\exists! x.\bar\psi(x)$.

Answer 2

As Henning said, formally speaking, this is not quite true. We can define sets, without using the axiom of choice, which we cannot prove that they are measurable.

For example, every universe of set theory has a subuniverse satisfying the axiom of choice, in a very canonical way, called $L$. We can look at a set of reals which is a Vitali set in $L$, or any other non-measurable set that lives inside $L$. The axiom of choice is not needed for defining this set, however under some assumptions, this set will be an actual Vitali set, and thus non-measurable; and under other assumption it might be a countable set and therefore measurable.

What your professor really meant to say, is that it is consistent that the axiom of choice fails, and every set is Lebesgue measurable. This was proved by Solovay in 1970. So in most cases if you just write a definition of a "reasonable" set, it is most likely measurable. But nonetheless, this is not formally correct. As far as analysis go, though, it is usually the case that "explicitly defined sets" are measurable.

Answer 3

First, consider that constructing a non-measurable function is equivalent to constructing a non-measurable set (using indicator functions).

Second, what you are looking for appears to be Solovay's Theorem:

• https://mathoverflow.net/questions/42215/does-constructing-non-measurable-sets-require-the-axiom-of-choice
• https://en.wikipedia.org/wiki/Solovay_model

Basically, the idea is, as your professor claimed, we need to use the axiom of choice to construct sets which are not Lebesgue measurable (or equivalently non-Lebesgue measurable functions).

Answer 4

Well you need axiom of choice to construct a non measurable set (see https://mathoverflow.net/questions/42215/does-constructing-non-measurable-sets-require-the-axiom-of-choice).

If you construct a function without the axiom of choice then it must be measurable because otherwise we could then construct a non measurable set (as the inverse image of some measurable set).