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?



Choice Function on the Powerset of the Reals
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.


