MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
Axiom of choice and non measurable set

I am told somebody has shown the equivalence of the Axiom of Choice with existence of non-measurable Lebesgue sets on the real line, please, if any body knows the reference, i would like to have it.

share|cite|improve this question

marked as duplicate by Joel David Hamkins, Benjamin Steinberg, Anton Petrunin, Asaf Karagila, Andrés E. Caicedo May 19 '12 at 19:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Here is a reason why statements of this form are never equivalent to full choice: Choice is a global principle (For all sets...). These are "local statements" (there is a set...). By the technique of forcing, we can destroy choice at our leisure affecting only sets of size much larger than those sets verifying the local statement. – Andrés E. Caicedo May 18 '12 at 18:22
Duplicate question:… – Joel David Hamkins May 19 '12 at 0:51
To the moderators: if this question gets closed as a duplicate, is it possible to fold the answers here into the previous question? – Joel David Hamkins May 19 '12 at 1:13

In this paper (PDF) Sierpinski constructed a non-measruable set from an ultrafilter on $\mathbb{N}$. The existence of ultrafilters on $\mathbb{N}$ is weaker than the Axiom of Choice.

share|cite|improve this answer

The existence of a non-measurable set is completely too weak to prove the axiom of choice.

  1. It is consistent with ZF (without large cardinals at all) that the real numbers are a countable union of countable sets, in such model every set is Borel and therefore measurable.

  2. It is consistent with ZFC+The existence of an inaccessible cardinal that there is a model in which ZF+DC holds, but there are no non-measurable sets. DC is a form of strong countable choice.

  3. It is consistent with ZF that the real numbers are well-orderable but the axiom of choice fails in every acute way possibly imaginable at points far enough above the real line. So we can have sets without free ultrafilters; sequence of pairs without a choice function; and so on. However all those counterexamples entered the universe of set theory at a stage so far above the real numbers that they have no influence on Lebesgue measurability whatsoever.

The first two tells us that it is consistent that all sets are measurable and therefore ZF itself cannot prove the existence of non-measurable sets, but it cannot prove they do not exist either - we need further assumptions on the universe.

The third thing tells us about the same thing Andres Caicedo wrote in his comment: the axiom of choice is a very global statement, while the measurability of subsets of the real numbers is a very local statement. We can further have the following situation:

In ZFC if $\kappa$ is an inaccessible cardinal then $V_\kappa$ is a model of ZFC. Suppose that we have such cardinal, now add (via forcing) sets which violate the axiom of choice severely (e.g. Dedekind finite sets, amorphous sets, sequence of pairs without a choice function, etc.) but add all those sets without adding any sets to $V_\kappa$.

The result is that $V_\kappa$ is a model of ZFC in which the real numbers live happily but $V$ is an end-extension of $V_\kappa$ in which the axiom of choice fails.

share|cite|improve this answer
For statement 1, when the reals are a countable union of countable sets, it is deeply questionable whether there is such a thing as a Lebesgue measure at all, since so many things about the measure go wrong. For example, if the measure is countably additive, then if the reals are a countable union of countable sets, it follows that every set would have measure zero, which would contradict the requirement that the measure should give intervals the right measure. So I would prefer to say that there is no theory of the Lebesgue meausure when the reals are a countable union of countable sets. – Joel David Hamkins May 19 '12 at 0:48

(I believe this material is in Jech's giant set theory book, but I don't have it in front of me right now.)

I am almost entirely certain that the existence of a non-measurable set of reals is not equivalent to the full axiom of choice, but rather to some weakened choice principle. It certainly follows from the well-orderability of $\mathbb{R}$; I suspect it requires substantially less, but I am not sure.

[Meta-edit: Below I originally had a paragraph of bad explanation of why a nonmeasurable set doesn't imply choice. I've replaced it with a better explanation.]

EDIT: Here's why full choice is overkill. Take a model of ZFC (so there is a set of reals which is nonmeasurable), and consider a forcing over this model which is countably closed, so it adds no new reals. In particular, the ground model had a well-ordering of the reals, and since no new reals are added, and well-orderedness is absolute between forcing extensions, the reals in the extension are still well-ordered.

Now take a symmetric submodel of the generic extension by this forcing in which choice fails. Since the reals in the extension are well-orderd, we can still build a non-measurable set. In essence, what we've done is to add a failure of choice "way high up" in the cumulative hierarchy, where it doesn't affect sets of reals. The resulting model will be a model of $ZF+\neg AC+$``There exists a non-measurable set of reals," and so the existence of a non-measurable set of reals can't be equivalent to the full AC.

A natural question at this point is to ask whether a nonmeasurable set implies the axiom of choice for $\mathbb{R}$; the answer is still no, for pretty much the same reason. In general, a purely existential property (``there is a non-measurable set") which only talks about objects of a bounded rank in the cumulative hierarchy has no chance of implying full choice.

However, it is true that the existence of a non-measurable set requires some amount of the axiom of choice: we can build models of ZF+ Every subset of $\mathbb{R}$ is measurable," so the existence of a nonmeasurable set requires _some_ amount of choice. Even this statement, though, is not completely straightforward, since it implies the consistency of ZFC. So one thing we can ask is what the consistency strength ofZF doesn't prove that there is a non-measurable set" is.

Certainly the axiom of determinacy implies that every set of reals is measurable, but this is overkill in terms of consistency strength. The most famous model in which every set of reals is measurable is called the Solovay model, and is a model of ZF+DC (so something more than dependent choice is required to prove the existence of a non-measurable set). The construction of the Solovay model assumed an inaccessible cardinal (much weaker than what is needed for AD), and Saharon Shelah later proved that the consistency of one inaccessible cardinal is implied by the consistency of "every set of reals is measurable."

So the current situation is a dichotomy: either inaccessible cardinals are inconsistent with ZFC, or some amount of choice greater than dependent choice is required to ensure the existence of a non-measurable set. Given that much much larger large cardinals are generally thought to be consistent with ZFC, the consensus is that ZF does not prove the existence of a non-measurable set of reals. However, I do not know of any reasonably natural choice principle which is exactly equivalent to the existence of a non-measurable set. I hope this answers your question!

share|cite|improve this answer
Noah: It is not that it is the consensus, but ZF itself does not prove the existence of non-measurable sets even if all large cardinal axioms are inconsistent. In the Feferman-Levy model which begins from $L$ (and no large cardinals assumptions) has the property that every set is Borel. If you want to involve large cardinals then you need to require some way to ensure that there are non-Borel sets, some countable choice or so. – Asaf Karagila May 18 '12 at 18:49
I was under the impression that Shelah's paper "Can you take Solovay's inaccessible away?" showed that $\Sigma^1_3$-measurability implies that $\aleph_1$ is inaccessible in $L$, which would seem to contradict what you say. Is this not true? – Noah Schweber May 18 '12 at 20:06
Noah, in the Feferman-Levy model there are no $\Sigma^1_3$ sets which are not already Borel. Shelah's theorem is true, but in a very vacuous way. – Asaf Karagila May 18 '12 at 22:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.