Drawing conclusions by NOT using AC. - MathOverflow

Drawing conclusions by NOT using AC.

2010-05-07T09:04:48Z

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.

Answer by John Stillwell for Drawing conclusions by NOT using AC.

2010-05-07T10:34:00Z

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.

Answer by Pietro KC for Drawing conclusions by NOT using AC.

2010-05-15T23:10:44Z

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?

Answer by T. for Drawing conclusions by NOT using AC.

2010-06-12T18:27:12Z

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.