It is well known that from a free (non-principal) ultrafilter on $\omega$ one can define a non-measurable set of reals. The older example of a non-measurable set is the Vitali set,
a set of representatives for the equivalence classes of the relation on the reals "the same modulo a rational number". Is it known whether you can have one without the other?
I.e., is ZF consistent with the existence of a set of representatives for the Vitali equivalence relation without having a free ultrafilter on $\omega$?
What about the other direction? I thought I had convinced myself that using an ultrafilter, you can choose representatives for the Vitali equivalence relation, but right now that does not seem clear to me anymore.
Best Answer
Stefan, "low" cardinalities do not change by passing from $L({\mathbb R})$ to $L({\mathbb R})[{\mathcal U}]$, so the answer to the second question is that the existence of a nonprincipal ultrafilter does not imply the existence of a Vitali set.
More precisely: Assume determinacy in $L({\mathbb R})$. Then $2^\omega/E_0$ is a successor cardinal to ${\mathfrak c}$ (This doesn't matter, all we need is that it is strictly larger. That it is a successor is a result of Richard Ketchersid and I in our forthcoming paper on $G_0$-dichotomies, though it was long suspected. It is my understanding that it also follows from unpublished work by Foreman and Magidor).
Force with ${\mathcal P}(\omega)/Fin$ to add a Ramsey ultrafilter, so you are in the model studied by Di Prisco-Todorcevic. (The model was first studied by J.M. Henle, A.R.D. Mathias, and W.H. Woodin, in "A barren extension", in Methods in Mathematical Logic, Lecture Notes in Mathematics 1130, Springer-Verlag, 1985, pages 195-207, where they show for example that no new sets of ordinals are added in this extension.)
In their forthcoming paper on "Borel cardinals and Ramsey ultrafilters" by Ketchersid, Larson, and Zapletal, the question of how the (non-well-ordered) cardinality structure changes by going to this model is studied. I believe there are still many questions left, but one of the problems they have settled is in showing that $2^\omega/E_0$ is still strictly larger than ${\mathfrak c}$. This means we cannot pick representatives of the Vitali classes, of course (if $\sim$ is the Vitali equivalence relation, then ${\mathbb R}/\sim$ and $2^\omega/E_0$ are ``Borel isomorphic''), or else we would have that $2^\omega/E_0$ and $2^\omega$ have the same size by Schroeder-Bernstein.