Question

I'm not sure if this question is appropriate for mathoverflow, but I can't help but think that other people have wondered about it as well. When anyone first learns about the axiom of choice, the standard example used to convince the listener as to its necessity is the problem of finding a choice function on $\mathscr{P}(\mathbb{R})\backslash\{\emptyset\}$, the powerset of the reals, without the emptyset. I have always wondered: Is the axiom of choice really necessary to construct the function? In other words, is it possible to prove that without the axiom of choice, no such choice function exists. Or, if it is possible to directly construct a choice function on $\mathscr{P}(\mathbb{R})\backslash\{\emptyset\}$, are there any good examples?

Answer 1

Quiaochu Yuan and Gerald Edgar have given correct answers based on Solovay's theorem that ZF cannot prove the existence of a Lebesgue non-measurable set. I'd like to add that one doesn't need anything as high-powered as Solovay's model. Cohen's original model for ZF and the negation of AC will do the job. It contains a non-well-orderable set of reals and therefore (by Zermelo's proof) has no choice function on the set of nonempty subsets of the reals.

Answer 2

A choice function on $\mathcal{P}(\mathbb{R}) \backslash \{ \emptyset \}$ lets you construct a well-ordering of $\mathbb{R}$, and a well-ordering of $\mathbb{R}$ lets you construct a non-measurable subset of $\mathbb{R}$ (such as the Vitali set). But Solovay constructed a model of ZF in which all subsets of $\mathbb{R}$ are measurable. So it is consistent with ZF that no such choice function exists.

Edit: Apparently this came up on math.SE as well. I now see that you were asking a slightly different question from what I thought you were asking. In the linked thread F.G. Dorais states that "there is a definable well-ordering on $\mathbb{R}$" and AC are independent of each other and of ZF.

Answer 3

Using such a choice function, we get the most common construction of a set that is not Lebesgue measurable. (Pick one point from each equivalence class of $\mathbb{R}/\mathbb{Q}$) Of course existence of non-measurable set cannot be done without AC. So even choice from countable subsets of $\mathbb{R}$ cannot be established in ZF.

Answer 4

It seems as if you're interested in the question: "Does there exist a model of ZF in which there is a choice function on the reals but in which the axiom of choice is false?" I don't know how to prove it precisely but there does.

The axiom of global choice is an axiom of Gödel-Bernays (NBG) set theory (sets & classes) which states that there exist choice functions on proper classes as well as sets. NBG canonically uses the axiom of limitation of size instead, which implies global choice.

Now a Grothendieck universe is a set in the context of ZF whose rank is an inaccessible cardinal (the existence thereof is independent of ZF). I believe ZF plus the assertion that such a cardinal exists is formally equivalent to NBG minus global choice. Thus, we would by using a Grothendieck universe have a model of ZF onto which we could add the stipulation that there exist choice functions for all sets of rank less than that of the given inaccessible cardinal; choice for the sets of larger rank would not be guaranteed; although I don't know how to prove this, either.