Non-principal ultrafilters on ω - MathOverflow

Non-principal ultrafilters on ω

2010-02-20T05:00:08Z

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?

Answer by Joel David Hamkins for Non-principal ultrafilters on ω

2010-02-20T05:12:18Z

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.

Answer by alephomega for Non-principal ultrafilters on ω

2010-02-20T05:21:42Z

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.

Answer by gowers for Non-principal ultrafilters on ω

2010-02-20T12:30:59Z

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.