In mathematics, the ultrafilter lemma states that every filter is a subset of some ultrafilter, i.e. some maximal proper filter. This statement is in fact an easy consequence of the Boolean prime ideal theorem that is commonly used in order theory. In contrast, this article will only treat the special case of ultrafilters on a set S, which can be characterized as those filters which, for every subset of S, contain either that set or its complement.

Proving the lemma from the axiom of choice is an application of Zorn's Lemma, and is fairly standard as these things go. The partial ordering is simply that of a subset. The non-trivial part is proving that a maximal filter contains every set or its complement. Let us say F contains neither A nor X \ A. From maximality, that means there is a set B in F such that the intersection of A and B is empty (otherwise, the union of F and {A} would generate a filter). Likewise, there is a C such that the intersection of C and X \ A is empty. The intersection of C and B (let us call it D) is in F. D has empty intersection with both A and X \ A, so it has an empty intersection with X, so it is empty. But a filter cannot contain an empty set.

This proof uses Zorn's Lemma, which is equivalent to the axiom of choice. The Ultrafilter Lemma cannot be proven from ZF (the Zermelo-Fraenkel axioms) alone, and it cannot be used to prove the axiom of choice, so it is properly weaker.

Note: It seems to be quite reasonable to merge this article into other articles: most of all Boolean prime ideal theorem, but the characterization of ultrafilters (maximal filters, prime filters) of Boolean algebras of which the above proof is a special instance, would fit well into Boolean algebra. It would also be helpful to clarify whether this entails the Boolean prime ideal theorem (thus being equivalent) or not.