54A20-ProofThatEveryFilterIsContainedInAnUltrafilter.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{ProofThatEveryFilterIsContainedInAnUltrafilter}
\pmcreated{2013-03-22 14:41:44}
\pmmodified{2013-03-22 14:41:44}
\pmowner{rspuzio}{6075}
\pmmodifier{rspuzio}{6075}
\pmtitle{proof that every filter is contained in an ultrafilter}
\pmrecord{17}{36305}
\pmprivacy{1}
\pmauthor{rspuzio}{6075}
\pmtype{Proof}
\pmcomment{trigger rebuild}
\pmclassification{msc}{54A20}

\endmetadata

% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here
\begin{document}
Let $Y$ be the set of all non-empty subsets of $X$ which are not contained in $\mathcal{F}$.  By Zermelo's well-orderding theorem, there exists a relation `$\succ$' which well-orders $Y$.  Define $Y' = \{0\} \cup Y$ and extend the relation `$\succ$' to $Y'$ by decreeing that $0 \prec y$ for all $y \in Y$.

We shall construct a family of filters $S_i$ indexed by $Y'$ using transfinite induction.  First, set $S_0 = \mathcal{F}$.  Next, suppose that, for some $j \in Y$, $S_i$ has already been defined when $i \prec j$.  Consider the set $\bigcup_{i \prec j} S_i$; if $A$ and $B$ are elements of this set, there must exist an $i \prec j$ such that $A \in S_i$ and $B \in S_i$; hence, $A \cap B$ cannot be empty.  If, for some $i \prec j$ there exists an element $f \in S_i$ such that $f \cap j$ is empty, let $S_j$ be the filter generated by the filter subbasis $\bigcup_{i \prec j} S_i$.  Otherwise $\{ j \} \cup \bigcup_{i \prec j} S_i$ is a filter subbasis; let $S_j$ be the filter it generates.

Note that, by this definition, whenever $i \prec j$, it follows that $S_i \subseteq S_j$; in particular, for all $i \in Y'$ we have $\mathcal{F} \subseteq S_i$.  Let $\mathcal{U} = \bigcup_{i \prec j} S_i$.  It is clear that $\emptyset \notin \mathcal{F}$ and that $\mathcal{F} \subseteq \mathcal{U}$.

It is easy to see that $\mathcal{U}$ is a filter.  Suppose that $A \cap B \in \mathcal{U}$.  Then there must exist an $i \in Y'$ such that $A \cap B \in S_i$.  Since $S_i$ is a filter, $A \in S_i$ and $B \in S_i$, hence $A \in \mathcal{U}$ and $B \in \mathcal{U}$.  Conversely, if $A \in \mathcal{U}$ and $B \in \mathcal{U}$, then there exists an $i \in Y'$ such that $A \in S_i$ and $B \in S_i$.  Since $S_i$ is a filter, $A \cap B \in S_i$, hence $A \cap B \in \mathcal{U}$.  By the alternative characterization of a filter, $\mathcal{U}$ is a filter.

Moreover, $\mathcal{U}$ is an ultrafilter.  Suppose that $A \in \mathcal{U}$ and $B \in \mathcal{U}$ are disjoint and $A \cup B = X$.  If either $A \in \mathcal{F}$ or $B \in \mathcal{F}$, then either $A \in \mathcal{U}$ or $B \in \mathcal{U}$ because $\mathcal{F} \subset \mathcal{U}$.  If $A \in Y$ and $A \in S_A$, then $A \in \mathcal{U}$ because $S_A \subset \mathcal{U}$.  If $A \in Y$ and $A \notin S_A$, there must exist $x \in \mathcal{U}$ such that $A \cap x$ is empty.  Because $B$ is the complement of $A$, this means that $x \subset B$ and, hence $B \in \mathcal{U}$.

This completes the proof that $\mathcal{U}$ is an ultrafilter --- we have shown that $\mathcal{U}$ meets the criteria given in the alternative characterization of ultrafilters.
%%%%%
%%%%%
\end{document}