number of ultrafilters

Theorem.

Let $X$ be a set.The number (http://planetmath.org/CardinalNumber) of ultrafilters (http://planetmath.org/Ultrafilter) on $X$ is $\mathrm{|}X\mathrm{|}$ if $X$ is finite (http://planetmath.org/Finite),and ${\mathrm{2}}^{{\mathrm{2}}^{\mathrm{|}X\mathrm{|}}}$ if $X$ is infinite (http://planetmath.org/Infinite).

Proof.

If $X$ is finite then each ultrafilter on $X$ is principal,and so there are exactly $|X|$ ultrafilters.In the rest of the proof we will assume that $X$ is infinite.

Let $F$ be the set of all finite subsets of $X$,and let $\mathrm{\Phi }$ be the set of all finite subsets of $F$.

For each $A\subseteq X$ define$B_A=\{(f,\varphi )\in F\times \mathrm{\Phi }\mid A\cap f\in \varphi \}$,and $B_A^{\mathrm{\complement }}=(F\times \mathrm{\Phi })\setminus B_A$.For each $𝒮\subseteq 𝒫(X)$define ${ℬ}_{𝒮}=\{B_A\mid A\in 𝒮\}\cup \{B_A^{\mathrm{\complement }}\mid A\notin 𝒮\}$.

Let $𝒮\subseteq 𝒫(X)$,and suppose $A_1,\mathrm{\dots },A_m\in 𝒮$and $D_1,\mathrm{\dots },D_n\in 𝒫(X)\setminus 𝒮$,so that we have$B_{A_1},\mathrm{\dots },B_{A_m},B_{D_1}^{\mathrm{\complement }},\mathrm{\dots },B_{D_n}^{\mathrm{\complement }}\in {ℬ}_{𝒮}$.For $i\in \{1,\mathrm{\dots },m\}$ and $j\in \{1,\mathrm{\dots },n\}$let $a_{i,j}$ be such thateither $a_{i,j}\in A_i\setminus D_j$ or $a_{i,j}\in D_j\setminus A_i$.This is always possible, since $A_i\ne D_j$.Let $f=\{a_{i,j}\mid 1\le i\le m,\mathrm{\hspace{0.17em}1}\le j\le n\}$,and put $\varphi =\{A_i\cap f\mid 1\le i\le m\}$.Then $(f,\varphi )\in B_{A_i}$, for $i=1,\mathrm{\dots },m$.If for some $j\in \{1,\mathrm{\dots },n\}$ we have $D_j\cap f\in \varphi$ ,then $D_j\cap f=A_i\cap f$ for some $i\in \{1,\mathrm{\dots },m\}$,which is impossible,as $a_{i,j}$ is in one of these sets but not the other.So $D_j\cap f\notin \varphi$,and therefore $(f,\varphi )\in B_{D_j}^{\mathrm{\complement }}$.So $(f,\varphi )\in B_{A_1}\cap \mathrm{\cdots }\cap B_{A_m}\cap B_{D_1}^{\mathrm{\complement }}\cap \mathrm{\cdots }\cap B_{D_n}^{\mathrm{\complement }}$.This shows that any finite subset of ${ℬ}_{𝒮}$has nonempty intersection,and therefore ${ℬ}_{𝒮}$can be extended to an ultrafilter ${𝒰}_{𝒮}$.

Suppose $ℛ,𝒮\subseteq 𝒫(X)$ are distinct.Then, relabelling if necessary, $ℛ\setminus 𝒮$ is nonempty.Let $A\in ℛ\setminus 𝒮$.Then $B_A\in {𝒰}_{ℛ}$,but $B_A\notin {𝒰}_{𝒮}$ since $B_A^{\mathrm{\complement }}\in {𝒰}_{𝒮}$.So ${𝒰}_{ℛ}$ and ${𝒰}_{𝒮}$ are distinctfor distinct $ℛ$ and $𝒮$.Therefore $\{{𝒰}_{𝒮}\mid 𝒮\subseteq 𝒫(X)\}$ isa set of $2^{2^{|X|}}$ ultrafilters on $F\times \mathrm{\Phi }$.But $|F\times \mathrm{\Phi }|=|X|$,so $F\times \mathrm{\Phi }$ has the same number of ultrafilters as $X$.So there are at least $2^{2^{|X|}}$ ultrafilters on $X$,and there cannot be more than $2^{2^{|X|}}$as each ultrafilter is an element of $𝒫(𝒫(X))$.∎

Corollary.

The number of topologies on an infinite set $X$ is ${\mathrm{2}}^{{\mathrm{2}}^{\mathrm{|}X\mathrm{|}}}$.

Proof.

Let $X$ be an infinite set.By the theorem, there are $2^{2^{|X|}}$ ultrafilters on $X$.If $𝒰$ is an ultrafilter on $X$,then $𝒰\cup \{\mathrm{\varnothing }\}$ is a topology on $X$.So there are at least $2^{2^{|X|}}$ topologies on $X$,and there cannot be more than $2^{2^{|X|}}$as each topology is an element of $𝒫(𝒫(X))$.∎