number of ultrafilters

Theorem.

Let $X$ be a set. The number (http://planetmath.org/CardinalNumber) of ultrafilters (http://planetmath.org/Ultrafilter) on $X$ is $|X|$ if $X$ is finite (http://planetmath.org/Finite), and $2^{2^{|X|}}$ 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 $\Phi$ be the set of all finite subsets of $F$ .

For each $A\subseteq X$ define $B_{A}=\{(f,\phi)\in F\times\Phi\mid A\cap f\in\phi\}$ , and $B_{A}^{\complement}=(F\times\Phi)\setminus B_{A}$ . For each ${\cal S}\subseteq\mathcal{P}(X)$ define ${\cal B}_{\cal S}=\{B_{A}\mid A\in{\cal S}\}\cup\{B_{A}^{\complement}\mid A% \notin{\cal S}\}$ .

Let ${\cal S}\subseteq\mathcal{P}(X)$ , and suppose $A_{1},\dots,A_{m}\in\cal S$ and $D_{1},\dots,D_{n}\in\mathcal{P}(X)\setminus\cal S$ , so that we have $B_{A_{1}},\dots,B_{A_{m}},B_{D_{1}}^{\complement},\dots,B_{D_{n}}^{\complement% }\!\!\!\in{\cal B}_{\cal S}$ . For $i\in\{1,\dots,m\}$ and $j\in\{1,\dots,n\}$ let $a_{i,j}$ be such that either $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}\neq D_{j}$ . Let $f=\{a_{i,j}\mid 1\leq i\leq m,\,1\leq j\leq n\}$ , and put $\phi=\{A_{i}\cap f\mid 1\leq i\leq m\}$ . Then $(f,\phi)\in B_{A_{i}}$ , for $i=1,\dots,m$ . If for some $j\in\{1,\dots,n\}$ we have $D_{j}\cap f\in\phi$ , then $D_{j}\cap f=A_{i}\cap f$ for some $i\in\{1,\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\phi$ , and therefore $(f,\phi)\in B_{D_{j}}^{\complement}$ . So $(f,\phi)\in B_{A_{1}}\cap\cdots\cap B_{A_{m}}\cap B_{D_{1}}^{\complement}\cap% \cdots\cap B_{D_{n}}^{\complement}$ . This shows that any finite subset of ${\cal B}_{\cal S}$ has nonempty intersection, and therefore ${\cal B}_{\cal S}$ can be extended to an ultrafilter ${\cal U}_{\cal S}$ .

Suppose ${\cal R},{\cal S}\subseteq\mathcal{P}(X)$ are distinct. Then, relabelling if necessary, ${\cal R}\setminus{\cal S}$ is nonempty. Let $A\in{\cal R}\setminus{\cal S}$ . Then $B_{A}\in{\cal U}_{\cal R}$ , but $B_{A}\notin{\cal U}_{\cal S}$ since $B_{A}^{\complement}\in{\cal U}_{\cal S}$ . So ${\cal U}_{\cal R}$ and ${\cal U}_{\cal S}$ are distinct for distinct $\cal R$ and $\cal S$ . Therefore $\{{\cal U}_{\cal S}\mid{\cal S}\subseteq\mathcal{P}(X)\}$ is a set of $2^{2^{|X|}}$ ultrafilters on $F\times\Phi$ . But $|F\times\Phi|=|X|$ , so $F\times\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 $\mathcal{P}(\mathcal{P}(X))$ . ∎

Corollary.

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

Proof.

Let $X$ be an infinite set. By the theorem, there are $2^{2^{|X|}}$ ultrafilters on $X$ . If $\mathcal{U}$ is an ultrafilter on $X$ , then $\mathcal{U}\cup\{\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 $\mathcal{P}(\mathcal{P}(X))$ . ∎

Title	number of ultrafilters
Canonical name	NumberOfUltrafilters
Date of creation	2013-03-22 15:51:49
Last modified on	2013-03-22 15:51:49
Owner	yark (2760)
Last modified by	yark (2760)
Numerical id	14
Author	yark (2760)
Entry type	Theorem
Classification	msc 03E99