# Non-principal ultrafilters on ω

I thought I had heard or read somewhere that the existence of a non-principal ultrafilter on $\omega$ was equivalent to some common weakening of AC. As I searched around, I read that this is not the case: neither countable choice nor dependent choice are strong enough.

This leads me to two questions:

Where would I find a proof that DC is not strong enough to prove the existence of a non-principal ultrafilter on $\omega$?

Is the assumption that there exists a non-principal ultrafilter on $\omega$ strong enough to show DC or countable choice? I.e. is "there exists a non-principal ultrafilter on $\omega$" stronger than either of countable or dependent choice?

-
Spelling nitpick (which I've fixed): "principal" means "important" and "principle" means "rule." But kudos on spelling "dependent" correctly; mathematicians and CS people tend to be bad at that one. –  Qiaochu Yuan Feb 20 '10 at 5:28
Eep! Thanks... Not sure how I missed that. –  Cory Knapp Feb 20 '10 at 5:32
I added the ultrafilters tag. –  Joel David Hamkins Feb 20 '10 at 5:35

See the Prime ideal theorem.

The existence of ultrafilters on every Boolean algebra (which implies non-principal ultrafilters on ω, since these come from ultrafilters on the Boolean algebra P(ω)/Fin) is a set-theoretic principle that follows from AC and is not provable in ZF (if ZF is consistent), but which does not imply full AC. Thus, it is an intermediate weaker choice principle.

Your statement about ultrafilters on ω appears to be even weaker, since it is such a special case of the Prime Ideal Theorem.

Nevertheless, I believe that the method of forcing shows that it is consistent with ZF that there are no non-principal ultrafilters on ω. I believe that some of the standard models of ¬AC, built by using symmetric names for adding Cohen reals, have DC, and hence also ACω, but still have no nonprincipal ultrafilters on ω. In this case, neither DC nor ACω would imply the existence of such ultrafilters.

I'm less sure about finding models that have ultrafilters on ω, but not on all Boolean algebras. But I believe that this is likely the case. These models would show that your principle is strictly weaker even than the Prime Ideal Theorem.

-
Thanks. The article led me in exactly the direction I was looking. –  Cory Knapp Feb 20 '10 at 5:26
A model of DC without ultrafilters on omega was produced by David Pincus and Bob Solovay in Definability of measures and ultrafilters (J. Symb. Logic 42, 1977). I think models without ultrafilters were produced earlier by Andreas Blass, but I don't recall the status of DC in that case. –  François G. Dorais Feb 20 '10 at 5:49
Thanks, François! Do Pincus and Solovay use an inaccessible cardinal in that model (i.e. "the Solovay model")? Or can one do it starting just from ZFC? And do you know models that have ultrafilters on omega, but not on higher cardinals? –  Joel David Hamkins Feb 20 '10 at 6:00
Thanks, indeed, François. That gives a more solid answer to my first question. –  Cory Knapp Feb 20 '10 at 6:38
@Joel: No, they don't use large cardinals. –  François G. Dorais Feb 20 '10 at 22:17

As Joel points out, actually this existence statement is weaker than AC. You absolutely need AC to prove this maximality claim. On a completely different note, the question whether a non principal ultrafilter on a certain set exists is unsettled (and probably can't be settled at all) in New Foundations since AC is false there.

-

There is a nice class of problems that are equivalent to the existence of a non-principal ultrafilter. One such, if I remember correctly, is the existence of a colouring of the infinite subsets of the natural numbers in such a way that no infinite set has all its infinite subsets of the same colour. The obvious proof is to colour the sets in such a way that if you add or take away a single element then you change its colour. To make this proof work, you define two sets to be equivalent if their symmetric difference is finite, and do the colouring in each equivalence class separately. But to get it started you have to pick a set in each equivalence class, and for that the obvious thing to do is use AC.

But you can in fact do it with a non-principal ultrafilter as follows. Given an infinite subset A, define its counting function f(n) to be the cardinality of the intersection of A with {1,2,...,n}. Then take a non-principal ultrafilter α and define F(A) to be the limit along α of $(-1)^{f(n)}$. If you add an element m to A, then f(n) is unchanged up to m and then adds 1 thereafter, so its parity is changed everywhere except on a finite set, which implies that F(A) changes. So F gives you your colouring.

I've never actually thought about the other direction (getting from such a colouring to a non-principal ultrafilter) so I don't know how hard it is. I'm not even 100% sure that it's true, but I'm pretty sure I remember hearing that it was.

-
To show the existence of such colouring it is enough to assume the existence of a non-meager filter on $\omega$. There are models with non-meager filters and with no ultrafilters. –  Ramiro de la Vega Feb 20 '13 at 19:55