Axiom of choice: ultrafilter vs. Vitali set 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.
 A: 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.
A: Here is a tentative (negative) answer to the question of whether the existence of an $E_{0}$ (Vitali) selector implies the existence of a nonprincipal ultrafilter on $\omega$. I need to check some of the details (I'll say where below) but it seems ok to me. I'm posting this now in hope that someone has any ideas for an easier solution. 
Let $P$ be the partial order consisting of countable partial $E_{0}$ selectors, ordered by inclusion. Let (a) be the statement (meant to be applied in the context of Choice) that whenever $D$ is a dense subset of $P$ in $L(\mathbb{R})$ and $F \subseteq P$ is a filter of cardinality less than the continuum ($\mathfrak{c}$), $F$ can be extended to a filter containing a member of $D$. If (a) holds, the continuum is regular, and $|\mathcal{P}(\mathbb{R}) \cap L(\mathbb{R})| = \mathfrak{c}$ (which holds if a measurable cardinal exists, for instance), then one can build $L(\mathbb{R})$-generic filters for $P$. 
For all I know, (a) is a consequence of ZFC plus suitable large cardinals. It is clearly a consequence of the Continuum Hypothesis, but that doesn't seem to be of much use. Assuming that the theory of $L(\mathbb{R})$ is fixed by set forcing (which happens for instance if there exist proper class many Woodin cardinals; this hypothesis can be fine-tuned for our purposes), you would get that forcing with $P$ over $L(\mathbb{R})$ does not add a nonprincipal ultrafilter, if you knew that each of the following statements could be forced along with (a) + `$\mathfrak{c}$ is regular" : (1) for every nonprincipal ultrafilter $U$ on $\omega$ there is a Ramsey ultrafilter in $L(\mathbb{R})[U]$; (2) there are no Ramsey ultrafilters. Each of (1) and (2) is forceable along with $\mathfrak{c}= \aleph_{2}$. I'm not sure who showed this; my guess is Blass in the first case, and Kunen in the second.
I don't know anything about producing models of (a) by forcing over models of ZFC, but (a) holds in the $\mathbb{P}\mathrm{max}$ extension of any model of $\mathrm{AD}^{+}$ (such as $L(\mathbb{R})$, if there exist infinitely many Woodin cardinals below a measurable cardinal). This does not seem to give much information on the original question, either, though it shows (via a $\Delta$-system argument) that if $G \subseteq \mathbb{P}\mathrm{max}$ is an $L(\mathbb{R})$-generic filter, then in $L(\mathbb{R})[G]$ there are $L(\mathbb{R})$-generic filters for $P$ whose extensions do not contain any ultrafilter on $\omega$ generated by a tower of length $\omega_{2}$ from the point of view of $L(\mathbb{R})[G]$. 
It seems to me that there are natural variations of $\mathbb{P}\mathrm{max}$ for producing models in which the cardinal characteristic $\mathfrak{u}$ is equal to $\aleph_{1}$ (I believe that Woodin has done this, in fact). In these models, (a) seems to hold, and the cardinal characteristic $\mathfrak{g}$ should be $\aleph_{2}$, which gives statement (1), by results of Laflamme. 
More importantly, it gives Near Coherence of Filters (NCF), the statement that any two nonprincipal ultrafilters on $\omega$ are finite-to-one reducible to a common ultrafilter.  I don't know about getting (2)+(a) with a $\mathbb{P}\mathrm{max}$ variation. However, if there is a $P$-name for an nonprincipal ultrafilter on $\omega$, then one can map this name to two (continuum many, in fact) independent parts of $P$, and thus show that NCF cannot hold in the $P$-extension of $L(\mathbb{R})$ unless there are no nonprincipal ultrafilters there. 
This argument seems to have nothing to do with $E_{0}$. If it is correct, then it should show, for instance, that if $L(\mathbb{R}^{\#}) \models \mathrm{AD}^{+}$, then for any Borel action on the reals by a countable group, the partial order which adds a choice function for the orbits, with countable conditions, does not add a nonprincipal ultrafilter on $\omega$.   
I expect that this argument is more complicated than necessary in more than one way. One would expect the proof to go though a determinacy-style $\Delta$-system lemma, but I don't see how to do that. 
