# Most functions are measurable

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?

• Commented Jul 3, 2016 at 15:33
• I feel like the right notion here is not "did not use choice" but "used analysis-flavored constructions rather than delve into pure set theory", but I don't know how to express it. Maybe the internal logic of the topos of sheaves on the topological space whose lattice of open sets is (isomorphic to) the measurable subsets of $R$?
– user14972
Commented Jul 3, 2016 at 19:19
• Even assuming that what the professor says is true, why does this imply that most functions are measurable? Commented Jul 3, 2016 at 20:16
• @Hurkyl: I'd imagine some sufficiently rich language of analysis with $\Bbb R$, or $\Bbb C^n$, or something like that, as some "base universe" and Henkinization of a bunch of high-order stuff, which includes integration, measure, the Lebesgue sets, and some other things too, perhaps. I think that it's a good thing that we can't quite put our finger on this. Some extra-mathematical intuition should remain extra-mathematical. If we can formalize everything, then what good is that people---and not computers---do mathematics? (See also my recent blog post about automated proof search.) Commented Jul 3, 2016 at 22:06
• Actually, on further thought, I think what I suggested might actually work out well. By the usual nonsense, the only subsets of the base space you can define inside the topos are the open ones, and since "all" measure spaces are isomorphic this one topos should cover everything. It's even a boolean topos, so it obeys the laws of classical logic (although not a two-valued logic; the truth values would be the lattice of measurable subsets of $\mathbb{R}$). And being a topos, you can do all "elementary" set theory within it. Now I'm really curious about this category!
– user14972
Commented Jul 3, 2016 at 23:11

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)$.

• What about $\psi(x) \equiv (x\text{ is the first Vitali set of the inner model }\mathbf{L})$?
– user14972
Commented Jul 3, 2016 at 11:12
• @Hurkyl: Yes, that is one of the "less blatant ways of cheating" I alluded to. Commented Jul 3, 2016 at 11:20
• I like this answer alot. It's a remarkably simple approach to a tricky question. Commented Jul 3, 2016 at 12:53
• @Hurkyl: And also this is what I essentially suggested in my answer (although you don't even need "the first", even though this gives you an explicit set, and you just can't prove whether or not it is measurable or not). Commented Jul 3, 2016 at 14:26

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.

• Relevant: Large Cardinals Imply That Every Reasonably Definable Set of Reals Is Lebesgue Measurable by Saharon Shelah and Hugh Woodin. Commented Jul 3, 2016 at 9:28
• @Martín-Blas: Well, that is a different flavor of "reasonably definable". But also, yes, and Shelah's work in "Can You Take Solovay's Inaccessible Away?" had shown that if every "reasonably definable" set is measurable, then some large cardinals hide in inner models. But again, this is not the same as an analyst saying that a set is "reasonably definable". Commented Jul 3, 2016 at 11:00

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:

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).

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).

• "The axiom of choice is false" and "there exist nonmeasurable subsets of the reals" are consistent with each other....
– user14972
Commented Jul 3, 2016 at 19:14