## You are here

Homenumber of ultrafilters

## Primary tabs

# number of ultrafilters

###### Theorem.

Let $X$ be a set. The number of ultrafilters on $X$ is $|X|$ if $X$ is finite, and $2^{{2^{{|X|}}}}$ if $X$ is 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))$. ∎

## Mathematics Subject Classification

03E99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia