non-measurable sets

[gusl]

Wikipedia says:
<< In 1979, Solovay established that it is consistent with standard set theory, excluding uncountable choice, to assume that there are no non-measurable sets. >>

i.e. you can only construct these monsters by using uncountable choice. Why aren't mathematicians happy with countable choice? I like the idea of countable choice, since it would seem to keep math computational.

Comments

[bhudson.livejournal.com]

Devil's Advocate asks: Why does it matter if math is computational?

[jcreed.livejournal.com]

Could you explain why you think countable choice is more computational?

[rdore.livejournal.com]

Why aren't mathematicians happy with countable choice?

Countable choice is still too weak to do a huge amount of stuff in analysis. What might be a better alternative. Solovay's theorem (and very strong generalizations of it) however, still give dependent choice (DC). You might like that DC is like countable choice but strong enough to actually do a lot more actual mathematics. Of course you still lose important stuff like the Hahn–Banach theorem.

I like the idea of countable choice, since it would seem to keep math computational.

I strongly suspect it's possible to give a computable product of computable sets which still has no computable elements. Maybe I'll try to work one out later.

[jcreed.livejournal.com]

Did you have something like this in mind?

http://www.cs.swan.ac.uk/~csulrich/bib/Berger04.html

[gustavolacerda.livejournal.com]

There's nothing I can tell you that you don't know already, Master jcreed.

I'm associating: countable <=> recursively enumerable.

rdore or quale may have something more meaningful to say.

[rdore.livejournal.com]

I'm associating: countable <=> recursively enumerable.

I think this is a bad idea. These two classes will tend to have very different kinds of closure.

[jcreed.livejournal.com]

yeah I think I agree with richard that your intuition doesn't quite hold up... countable choice postulates the existence of choice functions, which although they have a reasonable domain (a countable set) to be candidates for being computable or R.E., are in no way actually guaranteed to BE computable or R.E. just because some axiom says they exist as functions.

[easwaran.livejournal.com]

Countable choice doesn't prove that the reals have a basis as a vector space over the rationals.

It looks like someone fixed the Wikipedia line since you quoted it - Solovay's proof assumes the consistency of an inaccessible (which seems like an eminently reasonable assumption, but still, most people would want to explicitly mention that assumption). I believe Solovay's method starts with a model of ZFC+"there is 1 Inaccessible", collapses the inaccessible using forcing, and takes some inner model, and shows that the resulting model has no unmeasurable sets, but satisfies countable choice.

A more interesting approach is instead of using ZFC, to use ZF+DC+Axiom of Determinacy, which proves not only that all reals are Lebesgue measurable, but has lots of other nice consequences. It turns out that if countably many Woodin cardinals plus a measurable cardinal on top is consistent, then L(R) (the universe built up by the definable powerset operation, the way Godel's L is built up from the emptyset, but starting with R instead of the emptyset) satisfies ZF+DC+AD. So this theory is quite nice, and also almost certainly consistent.

But countability and computability are far apart. If computable means recursive, then in fact we know that there are countably many recursive reals, but they are not recursively countable, because you can just recursively diagonalize.

[rdore.livejournal.com]

I believe Solovay's method starts with a model of ZFC+"there is 1 Inaccessible", collapses the inaccessible using forcing, and takes some inner model, and shows that the resulting model has no unmeasurable sets, but satisfies countable choice.

Yea, you Levy collapse the inaccessible to omega1 (so everything smaller than the inaccessible becomes countable). Then I believe you just look at L(R) of that model. Then you do some messing around names of sets of reals and the homogeneity of the forcing interacts with the L-ness and that lots of stuff is now looks countable. Somewhere in there you need to understand measurability, which is the primary impediment to me having a chance of remembering how to do this. This model also has DC and not just countable choice. In addition to the lower consistency strength, the analysis required in the Solovay Model is much less than having to prove determinacy plus that determinacy implies measurability (not hard, but more of a mess than most basic determinacy results). Of course determinacy is interesting and nice for a whole host of other reasons.

[psifenix.livejournal.com]

I find countable choice intuitively more believable, but it's a mathematician's job to prove theorems from axioms, and as long as no one is lying about the axioms, there should be no problem. Making things "more computational" is certainly not an ignoble goal, but it is not the ultimate goal of mathematics.