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 NumberOfUltrafilters 2013-03-22 15:51:49 2013-03-22 15:51:49 yark (2760) yark (2760) 14 yark (2760) Theorem msc 03E99