#REDIRECT [[Ultrafilter on a set#The ultrafilter lemma]]
An [[ultrafilter]] is a maximal [[Mathematical filter|filter]] -- for every set, either that set or its complement is in the filter. The '''Ultrafilter Lemma''' says that every filter is a subset of some ultrafilter.
Proving the lemma from the [[axiom of choice]] is an application of [[Zorns lemma|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. QED
This proof uses Zorn's Lemma, which is equivalent to the axiom of choice. The Ultrafilter Lemma cannot be proven from [[Set theory|ZF]] (the Zermelo-Fraenkel axioms) alone, and it cannot be used to prove the axiom of choice, so it is properly weaker.
