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?

3$\begingroup$ You should say "the powerset $\mathcal{P}(\mathcal{R})$ without the empty set", otherwise there is no choice function because you can't choose anything from the empty set. $\endgroup$ – Andrej Bauer Nov 8 '10 at 14:27

1$\begingroup$ ... which is $\mathscr{P}(\mathbb{R})\backslash\{\emptyset\}$ not $\mathscr{P}(\mathbb{R})\backslash\emptyset$. $\endgroup$ – Gerald Edgar Nov 8 '10 at 22:09
Quiaochu Yuan and Gerald Edgar have given correct answers based on Solovay's theorem that ZF cannot prove the existence of a Lebesgue nonmeasurable set. I'd like to add that one doesn't need anything as highpowered as Solovay's model. Cohen's original model for ZF and the negation of AC will do the job. It contains a nonwellorderable set of reals and therefore (by Zermelo's proof) has no choice function on the set of nonempty subsets of the reals.

$\begingroup$ Cohen's original model is not particularly nice for analysis (DC fails, for example). We can get relatively decent models where the reals are not wellorderable, without using Solovay's result. For example, Shelah has shown that ZF is equiconsistent with ZF+DC+all sets of reals have the property of Baire. $\endgroup$ – Andrés E. Caicedo Nov 8 '10 at 23:45
A choice function on $\mathcal{P}(\mathbb{R}) \backslash \{ \emptyset \}$ lets you construct a wellordering of $\mathbb{R}$, and a wellordering of $\mathbb{R}$ lets you construct a nonmeasurable 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 wellordering on $\mathbb{R}$" and AC are independent of each other and of ZF.

1$\begingroup$ Just to be nitpicky: $\mathcal{P}(\mathbb{R}) \backslash \{\emptyset\}$. $\endgroup$ – Asaf Karagila Nov 8 '10 at 19:58

$\begingroup$ You might want to try and use \{ for the braces in math mode :) $\endgroup$ – Asaf Karagila Nov 8 '10 at 20:24

$\begingroup$ Qiaochu: If there is a choice function as indicated, then there is a wellordering of ${\mathbb R}$. Conversely, a wellordering gives you a choice function. So this is essentially the same question. $\endgroup$ – Andrés E. Caicedo Nov 8 '10 at 23:40

$\begingroup$ @Andres: yes, I know. What I meant is that I read "without AC" as "in ZF." $\endgroup$ – Qiaochu Yuan Nov 9 '10 at 0:10

$\begingroup$ @Qiaochu: Gotcha. You may be interested in the comment I made to Andreas Blass' answer. The point is that the Lebesgue measurability of all sets of reals requires (consistencywise) an inaccessible cardinal. $\endgroup$ – Andrés E. Caicedo Nov 9 '10 at 0:32
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 nonmeasurable set cannot be done without AC. So even choice from countable subsets of $\mathbb{R}$ cannot be established in ZF.
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ödelBernays (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.

$\begingroup$ @Daniel : It is easy by the technique of forcing to produce examples where we have a choice function on the reals, but not on the powerset of the reals, or in general, where we have a choice function on some very large objects, but not beyond. Also, there is a little mistake in what you say: NBG minus global choice is equiconsistent with ZF, which is strictly weaker than the existence of inaccessible cardinals. $\endgroup$ – Andrés E. Caicedo Nov 8 '10 at 23:43

$\begingroup$ I took a look back at "Set Theory for Category Theory" by Michael Shulman and realized I had misremembered what I'd read. "One should think of the classes in NBG and MK as corresponding to the large sets of rank (or cardinality) $≤\kappa.$ In fact, one can make this precise. If $\kappa$ is inaccessible, we obtain a model of MK (and hence NBG) by taking $V_\kappa$ for the sets and $V_{\kappa+1} = \mathcal{P}V_\kappa$ for the classes. (Note that this means we can prove Con(MK) in ZFC+I, so ZFC+I is strictly stronger than mk.)" In particular, I had forgot what was in the parentheses. $\endgroup$ – Daniel Briggs Nov 9 '10 at 16:36