nLab
ultrafilter theorem

Context

(0,1)(0,1)-Category theory

Foundations

The ultrafilter theorem

Idea

In classical mathematics, the ultrafilter theorem is a theorem about ultrafilters, proved as a standard application of Zorn's lemma. In the foundations of mathematics, however, it is interesting to consider which results are implied by it or equivalent to it (very few imply it without being equivalent, other than those that imply the full axiom of choice itself).

Statement and proof

Ultrafilter theorem

Given a set XX, every proper filter on XX may be extended to an ultrafilter (that is, a maximal proper filter) on XX.

Standard proof

Given a proper filter FF on XX, consider the poset of proper filters that refine (contain) FF, ordered by inclusion (reverse refinement). Of course, FF is in this poset. Given a chain 𝒞\mathcal{C} of proper filters that refine FF, the union F𝒞F \cup \bigcup \mathcal{C} is a proper filter that refines FF and is an upper bound of 𝒞\mathcal{C}. By Zorn's lemma, there is a proper filter maximal among those that refines FF, which is therefore maximal among all proper filters.

Although this proof uses Zorn’s lemma, the statement itself is weaker. In particular, it is weaker than the axiom of choice (even assuming the principle of excluded middle).

Strength and weakness as a “choice principle”

Although the ultrafilter theorem is weaker than the axiom of choice, it can be used to prove quite a few results that are traditionally proved using Zorn's lemma (or some other thing equivalent to the axiom of choice). For example, it can be used to prove

as a partial list. An enlightening discussion of the things one might expect to be able to prove using the ultrafilter theorem is given here at MO.

However, in other respects, the ultrafilter theorem is very weak as a “choice principle”. For example, it is too weak to prove the axiom of countable choice (so for example, it cannot prove that a countable union of countable sets is countable), a fact exhibited in Cohen’s first model for the failure of the axiom of choice (where even countable choice fails but the ultrafilter theorem holds). It therefore cannot prove the axiom of dependent choice either.

It can prove some traditional applications of dependent choice. For example, it can be used to linearly order any set. From there it can be used to prove that a countable union of nonempty finite sets is countable, which in turn can be used to establish the weak König lemma; see here.

In constructive mathematics, the ultrafilter principle also implies De Morgan's law, which means that the poset of truth values Ω\Omega is a De Morgan Heyting algebra. Any topos with an internal ultrafilter principle is thus a De Morgan topos.

Other formulations

Here are several statements equivalent (internal to an arbitrary topos) to the ultrafilter theorem.

The first three are, if you work through the definitions, almost direct rephrasings of the theorem above:

These basic results in logic are equivalent to the ultrafilter theorem:

Various characterisations of compact spaces are equivalent to the ultrafilter theorem:

These classical results in analysis are equivalent to the ultrafilter theorem in a Boolean topos with natural numbers object:

Failures

Of course, since the ultrafilter theorem is independent of ZF, there are models in which it fails. More strongly, however, there are apparently models of ZF in which every ultrafilter (on every set) is principal. See this MO answer.

References

Various equivalences with the ultrafilter theorem are stated and proved (in ZF) in

See a summary (in GIF!): page 1 and page 2.

It's possible that I've made some mistakes above in deciding which of these use excluded middle or the existence of a natural numbers object. (I very much doubt that any of them use replacement.)

For the ultrafilter principle in constructive mathematics: