Does constructing non-measurable sets require the axiom of choice?

The classic example of a non-measurable set is described by wikipedia. However, this particular construction is reliant on the axiom of choice; in order to choose representatives of $\mathbb{R} /\mathbb{Q}$.

"Since each element intersects [0,1], we can use the axiom of choice to choose a set containing exactly one representative out of each element of R / Q."

Is it possible to construct a non-measurable set (in $\mathbb{R}$ for example) without requiring the A.o.C.?

-
In a sense, no. This is a very popular question on the mathematical internet. Look up en.wikipedia.org/wiki/Solovay%27s_model –  Pietro KC Oct 14 '10 at 21:37
There is an interesting discussion on: math.niu.edu/~rusin/known-math/99/AD_AC –  Hany Oct 15 '10 at 8:46
Of course. Well, it depends on the measure. Did you mean to say "Lebesgue measurable"? –  Kevin O'Bryant Oct 17 '10 at 16:50
@Kevin: Clearly, Lebesgue measurable. There is a subtlety: There are (consistently) measures defined on all sets of reals that, when restricted to the Lebesgue measurable sets, coincide with Lebesgue measure. This is not an innocuous assumption: It contradicts CH, and implies the Lebesgue measurability of the sets that the descriptive-set theorists call $\Delta^1_3$. Neither of these facts holds without additional assumptions. –  Andres Caicedo Oct 17 '10 at 20:25

In the 1960's, Bob Solovay constructed a model of ZF + the axiom of dependent choice (DC) + "all sets of reals are Lebesgue measurable." DC is a weak form of choice, sufficient for developing the "non-pathological" parts of real analysis, for example the countable additivity of Lebesgue measure (which is not provable in ZF alone). Solovay's construction begins by assuming that there is a model of ZFC in which there is an inaccessible cardinal. Later, Saharon Shelah showed that the inaccessible cardinal is really needed for this result.

-

As other answers point out, yes, one needs choice. The popular/natural examples of models of ZF+DC where all sets of reals are measurable are models of determinacy, and Solovay's model. They are related in deep ways, actually, through large cardinals. (Under enough large cardinals, $L({\mathbb R})$ of $V$ is a model of determinacy and (something stronger than) elementarily equivalent to a Solovay model.)

An interesting question that this does not settle, is how much choice is required to produce a non-Lebesgue measurable set. It is enough to have a well-ordering of ${\mathbb R}$, by Vitali's construction. But this is too much: The existence of a non-principal ultrafilter on $\omega$ is not enough to well-order the reals, but suffices to give non-measurable sets.

In a slightly different direction, Matt Foreman and Friedrich Wehrung showed a while ago that an appropriate instance of the Hahn-Banach theorem suffices as well. (This is in "The Hahn-Banach theorem implies the existence of a non-Lebesgue measurable set", Fund. Math. 138 (1991), no. 1, 13--19.) Actually, Hahn-Banach can be understood as a choice principle in its own right. Unfortunately, I do not know any references for this in English, but see Xavier Caicedo-Germán Enciso. "El teorema de Hahn-Banach como principio de eleccion", Revista de la Academia Colombiana de Ciencias Vol. 28 (106) (2004), 11-20. For example, from the abstract:

The Hahn–Banach theorem implies the axiom of choice for families of closed convex sets in reflexive spaces and for more general families of convex sets in locally convex spaces.

-
one could interpret your 2nd paragraph as "no, one does not need choice (at least not all of it)" :) Existence of a non-principal ultrafilter only needs the boolean prime ideal theorem, strictly weaker than AC (but not a theorem of ZF) –  uunknown Oct 15 '10 at 10:20
Hehe. But seriously, whenever when asks if choice implies some property A, the actual question should be to identify the weakest choice-like principle that is equivalent to A. Of course, it may be a silly enterprise to do this sometimes, but interesting results can be found that way. –  Andres Caicedo Oct 15 '10 at 14:05
I agree. So it seems that ZF+BPI is enough to give non-measurable sets (and therefore AC is sufficient but not necessary). I wonder if any weaker extension of ZF can construct them... –  uunknown Oct 15 '10 at 14:28
Also, Janusz Pawlikowski showed that Hahn-Banach implies the Banach-Tarski paradox, which of course implies the existence of non-measurable sets. I seem to recall that Hahn-Banach is equivalent to a weak version of BPI. While BPI says that on every Boolean algebra there is a $\{ 0,1\}$-valued finitely additive measure, Hahn-Banach is equivalent to the existence of a $[0,1]$-valued finitely additive measure. –  Goldstern Feb 25 '12 at 10:38

Yes, it requires the axiom of choice (and so No, it's not possible without), in the sense that Zermelo-Fraenkel set theory without choice (ZF) is not enough. ZF together with the Axiom of Determinacy (AD) proves that there are no non-measurable subsets of $\mathbb R$. ZF+AD is believed to be consistent (of course this is not provable, by Gödel's theorem).

-

To add to the answer about what is the weakest choice-like principle required: let me take this opportunity to mention Consequences of the Axiom of Choice by Rubin and Howard. This is form 93 in the book and no known exact equivalents are listed for it. An extensive implication table is available.

For instance, as pointed out, the existence of a non-trivial ultrafilter on $\omega$ is sufficient, and BPI (the boolean prime ideal theorem) implies the existence of such an ultrafilter. According to the book, neither of these implications is reversible.

Another intermediate principle the book mentions is the sock selection principle (every family of pairs has a choice function). This is implied by BPI and implies the existence of a non-measurable set, and neither of these is reversible.

-
I think to recall that, years ago, Alf Onshuus found for any $n$ an argument from "every family of sets of size $n$ has a choice function". This is probably classic as well. –  Andres Caicedo Oct 17 '10 at 20:21