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 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.
$ \{ 0,1\}$-valued finitely additive measure, Hahn-Banach is equivalent to the existence of a $[0,1]$-valued finitely additive measure.
$\endgroup$
Commented
Feb 25, 2012 at 10:38
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.
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).
