Ultrafilter lemma

Every proper filter on a set is contained in an ultrafilter. Order its proper filter extensions by inclusion, use Zorn lemma to obtain a maximal extension, and observe that maximality forces it to contain exactly one of every set and its complement.

Let $S$ be a nonempty set and $\mathcal{P}\subseteq \mathcal{P}(S)$ be upward closed. An ultrafilter all of whose members lie in $\mathcal{P}$ exists exactly when every finite set partition of $S$ has a cell in $\mathcal{P}$. For sufficiency, the complements of sets outside $\mathcal{P}$ have the finite intersection property: a finite cover by such sets could be disjointified into a partition with no cell in $\mathcal{P}$. The ultrafilter lemma extends the generated proper filter. Necessity follows because an ultrafilter selects exactly one cell of every finite partition. This criterion requires partition richness of the whole ground set; it does not assert that the complement family is closed under unions.