# Ultra Filter and Axiom of Choice

Some person said me: "The fact that Ultra Filters exist is equivalent to the Axiom of choice".

Thanks

-
The statement that non-principal ultrafilters of every set exist is implied by (but as far as I know not equivalent to) the Axiom of Choice. –  Henning Makholm Oct 12 '12 at 12:17

The axiom of choice implies that every filter can be extended to an ultrafilter. However the implication cannot be reversed.

In Cohen's first model the axiom of choice fails badly: the real numbers cannot be well-ordered, and the axiom of countable choice fails. However in that model the ultrafilter lemma holds.

It should be mentioned that the ultrafilter lemma is equivalent to many useful theorems of ZFC: compactness theorem in logic; completeness theorem in logic; Tychonoff theorem for Hausdorff spaces; and more. However it is still weaker than the full axiom of choice.

You can get a tiny bit of choice from the ultrafilter lemma, though. The ultrafilter lemma implies that every set can be linearly ordered. Therefore if $\cal A$ is a family of non-empty finite sets, you can fix a linear ordering of $\bigcup\cal A$ and choose the minimal from every $A\in\cal A$. However this is all that you can provably do.

In fact, the existence of free ultrafilters is even weaker than the ultrafilter lemma. Namely, there is a model in which every infinite set has a free ultrafilter, but there are filters which cannot be extended to ultrafilters.

I'm not sure whether this still implies that every set can be linearly ordered, and therefore it might not imply choice for finite sets.

Four excellent resources for the axiom of choice related topics:

1. Herrlich, H. Axiom of Choice. Lecture Notes in Mathematics, Springer, 2006.

2. Jech, T. The Axiom of Choice. North-Holland (1973).

3. Howard, P. and Rubin, J.E. Consequences of the Axiom of Choice. American Mathematical Soc. (1998). Also see the online database for the book.

4. Moore, G. H. Zermelo's Axiom of Choice. Springer-Verlag (1982).

-
You've strongly implied that the statement "there are no free ultrafilters" is consistent with ZF, but you haven't actually said so. Is the non-existence of free ultrafilters indeed consistent with ZF? –  Tanner Swett May 7 '13 at 21:30
Yes, @Tanner. This was proved by Blass. See here for brief details. –  Asaf Karagila May 7 '13 at 22:01

No, it is not correct. The ultrafilter theorem is implied by, but does not imply, the axiom of choice. See p. 75 of Jech, Set Theory.

Theorem (ZFC) Every filter can be extended to an ultrafilter.

In fact the ultrafilter theorem is a choice principle weaker than AC: it is equivalent, over ZF, to the Boolean Prime Ideal Theorem.

Theorem (ZFC) Every ideal on a boolean algebra $B$ can be extended to a prime ideal.

This equivalence has some interest in mathematical logic since these theorems are equivalent, again over ZF, to two classical results: the completeness theorem and the compactness theorem for first-order predicate calculus.

-

It is not true. First, there are always principal (or fixed) ultrafilters: if $S$ is any non-empty set, and $s\in S$, $\{U\subseteq S:s\in U\}$ is a principal (or fixed) ultrafilter on $S$. Note that in this case $\bigcap\mathscr{U}=\{s\}$.

An ultrafilter $\mathscr{U}$ on a set $S$ is free if $\bigcap\mathscr{U}=\varnothing$. There are no free ultrafilters on any finite set. The existence of free ultrafilters on infinite sets requires some amount of choice, but less than the full axiom of choice. Specifically, the assertion that every filter can be extended to an ultrafilter is equivalent to the Boolean prime ideal theorem, which is independent of ZF but, by a result of Halpern and Levy, strictly weaker than the axiom of choice.

-