## Drawing conclusions by NOT using AC.

The existence of non-measurable subsets and functions on $\mathbb{R}$ require the use of the axiom of choice. That is, there exist models of ZF in which all subsets of (and hence all functions defined on) $\mathbb{R}$ are measurable. Does this mean that if I can define a subset or function on $\mathbb{R}$ without invoking the axiom of choice, it must be measurable?

Let's say I fully accept AC and am just looking for a quick and dirty way of proving a function is measurable.

-

With some difficulty, you can define a set of reals which is measurable under one extra-ZF assumption (the axiom of determinacy) and nonmeasurable under another (V=L). Under V=L you have a definable well-ordering of the reals, and this enables you to define any of the nonmeasurable functions you normally get using the axiom of choice. On the other hand, under the axiom of determinacy, every real function is measurable.

That's the strict answer. However, I think that any subset or function you are likely to define will be Borel, and hence provably measurable in ZF.

-
There is a widely believed thesis, known as Church's Thesis for Real Mathematics, which says that explicit sets and maps on $\mathbb{R}^{n}$ are Borel. – Simon Thomas May 7 2010 at 11:11
What? We can define a non-Borel (analytic) set easily... – Gerald Edgar May 7 2010 at 15:08
There is a difference between explicit and definable ... – Simon Thomas May 8 2010 at 1:02
Very interesting. Thanks! – Kevin Ventullo May 8 2010 at 6:34

Hi Kevin, welcome to MO! (I know you've been here a while, but I only just saw one of your questions.) I just want to expand a little on the thing about models, because I've asked myself similar questions to yours. Say you've defined a function without using Choice. Explicitly, this means you've defined a set f of ordered pairs, the first components of which come from a set A, and the second from a set B.

Each model of ZF has its own version of the function. This is like defining a function x |--> x^2, which only needs the concept of a binary operation, but in each concrete example the function will look quite different. Actually it's worse, because in the case of ZF you also need to specify the domain of your function. So a more accurate example would be defining the function above but only on the "set of cubes" (relative to the unspecified binary operation). Now the function looks even more different each time: it's just "doubling" in Z/5Z, but in Z/6Z it's the zero map on {0,3}.

So while your function might be measurable in a model where "every set is measurable", when you pass to another model, the ZF-definition may define a different function, which turns out not to be measurable. For example, different models of ZF may have "extra real numbers". (Just as different magmas have distinct sets of cubes.) If your ZF-definition has domain(f) = reals, this will carry over to all the different models, and in each one f will have a different domain. (Hence, more often than not, a different range.)

So you see the situation is quite chaotic a priori. And this is to say nothing of the fact that in each model of ZF "measurability" means something different.

Here's one last, somewhat strained, analogy. Suppose you were looking at structures satisfying the ring axioms (ZF in the analogy), but still interested in our map g above, x |--> x^2, defined on the set of cubes (a ZF-definable map). The ring axioms are silent about whether there are multiplicative inverses for nonzero elements (whether Choice holds). Suppose now someone found an example of a ring, not a field (where Choice failed), s.t. the image of g is exactly the set of fourth powers (is measurable). (E.g. Z/35Z.) Would you be able to conclude that, because your definition of g didn't use inverses (Choice), its range would always be the fourth powers, in any ring?

-

Solovay showed in the 1960's the consistency of ZF + axiom of Dependent Choice (for countable sets) + "every set of reals is Lebesgue measurable". .

This is a formal justification of the idea that any set of reals that can be proved to exist in ZFC without making uncountably many choices ---- i.e., a set that can be constructed in ZF + DC ---- cannot be proved to be non-measurable.

There are also theorems of Shelah, coming out of the analysis of determinacy (AD, Woodin cardinals, etc) to the effect that "any reasonably defined set is Lebesgue measurable".

So it is impossible to produce a Lebesgue non-measurable set without specifically looking for it in the wilds of uncountable AC.

It would be interesting to know what the state of the art is for metatheorems on how broad a range of constructions can be used in ZF+DC, that are guaranteed to stay within the world of provably Lebesgue measurable sets.

-
It's not true that any construction in ZF + DC is guaranteed to stay within the realm of provably Lebesgue measurable sets. A simple example is a nonmeasurable set in L; the reason why it is measurable in Solovay's model is that every such set is countable in that model. – François G. Dorais Jun 12 2010 at 18:42
@FGD: +1 ! But are there any results on what constructions do stay inside the provably-measurable world? – T. Jun 12 2010 at 19:02
Such assumptions, like L(R) satisfies AD, have very high consistency strength. – François G. Dorais Jun 12 2010 at 19:20
I think you are referring to Shelah+Woodin, "Large cardinals imply that every reasonably definable set of reals is Lebesgue measurable", Israel J Math 70 (1990) 381-394 showing that $AD_{L(R)}$ follows from supercompact cardinals. How does this relate to provable measurability rather than measurability per se? – T. Jun 12 2010 at 20:28