# 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.

-
It may be worth pointing out that Stefan's question is a strengthening of this one: mathoverflow.net/questions/21031/ultrafilters-vs-well-orderings –  John Stillwell Jul 6 '11 at 10:49
Regarding your first question: It is clear that a Vitali set exists as soon as the axiom of choice for countable families $C_\omega$ [not to be confused with the countable axiom of choice $AC_\omega$] holds. However, I have not so far found a model of $ZF+ C_\omega$ which has no free ultrafilter. Perhaps one can force a generic Vitali set over a Solovay model, and then show that no free ultrafilter appears in the generic extension. –  Ali Enayat Jul 6 '11 at 17:02
Thanks Stefan for asking this. I am curious about the same question with regards to Bernstein sets instead of Vitali sets. Further, can one have Vitali sets without Bernstein? Don't know whether to ask this as a separate question... –  George Lazou Jul 9 '11 at 16:32
Ali, thank you for the comment. I will try this. –  Stefan Geschke Jul 16 '11 at 5:59
@George: Go ahead, ask a seperate question. –  Stefan Geschke Jul 16 '11 at 6:00

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 negative.

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.

-
Andres, thank you for this nice answer. I was suspecting that people knowing more about desciptive set theory than myself could say something about this, but it didn't occur to me that the question might actually be related to very recent research. I am waiting a little bit before accepting the answer in case someone answers the first question. –  Stefan Geschke Jul 6 '11 at 18:53

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.

-
Dear Paul, I only came across your answer now. Thanks! Unfortunately this is much deeper than what I had hoped for. But you seem to share my feeling that there might be an easier solution. –  Stefan Geschke Apr 19 '13 at 8:45
Thanks, Stefan. I agree that there should be a simpler solution. One interesting thing about this one is that it gives another example (like Shelah-Zapletal 952) where forcings that preserve selective ultrafilters give information about inner models of determinacy. –  Paul Larson Apr 24 '13 at 18:52
Jindra has recently found a simpler proof. –  Paul Larson Oct 21 '14 at 13:50