Take some
maximal filter U and
set X⊆A. Want to show that either
X∈U or
A−X∈U.
(Proof sketch—assume not; extend
U to include
X; contradiciton with
maximality)
WLOG assume
X is nonempty.
Now assume that both
X∈/U and
A−X∈/U. Then let the extension
U′=U∪{a⊆A∣a⊇X}. and then
U⋆={⋂nTn∣T∈(U′)<ω}. Essentially we are doing the
minimal extension of
U to
U′ to include the
set X. By construction
U⋆ is closed upwards and
closed under finite intersection. Additionally, we know that
∅∈/U⋆. Say
∅∈U⋆. Then, loosely, since
∅∈/U and all
a⊇X are nonempty, then it must have come from a
⋂nTn term, which mean we would have some
set S∈U⋆ for which
S∩X=∅. This is only satisfied by some
S⊆A−X, which would imply that
A−X∈U⋆; contradiction. So
∅∈/U⋆, and hence
U⋆ is an ultrafilter.
Thus
U is an ultrafilter. And
X is in
U⋆ but not
U, so
U is not
maximal; contradiction.