# The set of ultrafilters on an infinite set

After recently learning about filters and ultrafilters, we looked into further problems and properties. I am having trouble with this one:

If $X$ is an infinite set, then the set of all ultrafilters on $X$ is uncountable.

-
Hint: Any infinite set can be split into two disjoint infinite subsets. You can use this to prove something stronger than what the question asks, namely: if $X$ is an infinite set then there are at least $2^{\aleph_0}$ ultrafilters on $X$. By a more difficult argument you can prove the optimal result, that if $X$ is infinite there are $2^{2^{|X|}}$ ultrafilters on $X$. – Carl Mummert Nov 19 '11 at 1:12
Some references concerning the cardinality of set of ultrafilters are given in this answer: math.stackexchange.com/questions/34838/… – Martin Sleziak Nov 19 '11 at 10:13

A family of sets is said to be almost disjoint if the intersection of any two distinct members of the family is finite.

For each real number $x$ let $\langle q_n(x):n\in\mathbb{N}\rangle$ be a sequence of rational numbers converging to $x$, and let $A_x=\{q_n(x):n\in\mathbb{N}\}$. Let $\mathscr{A}=\{A_x:x\in\mathbb{R}\}$. Suppose that $x,y\in\mathbb{R}$ with $x\ne y$. There is some $\epsilon>0$ such that $(x-\epsilon,x+\epsilon)\cap(y-\epsilon,y+\epsilon)=\varnothing$, and there is an $m\in\mathbb{N}$ such that $q_n(x)\in(x-\epsilon,x+\epsilon)$ and $q_n(y)\in(y-\epsilon,y+\epsilon)$ whenever $n\ge m$. It follows that $A_x\cap A_y\subseteq\{q_n(x):n<m\}\cup\{q_n(y):n<m\}$ and hence that $A_x\cap A_y$ is finite. $\mathscr{A}$ is therefore an almost disjoint family of subsets of $\mathbb{Q}$. Moreover, $|\mathscr{A}|=|\mathbb{R}|=2^\omega=\mathfrak{c}$.

For each $x\in\mathbb{R}$ let $\mathscr{U}_x$ be a non-principal ultrafilter on $A_x$, and let $$\mathscr{V}_x=\{V\subseteq\mathbb{Q}:\exists U\in\mathscr{U}_x[U\subseteq V]\}\;;$$ it’s not hard to check that $\mathscr{V}_x$ is a non-principal ultrafilter on $\mathbb{Q}$. Now suppose that $\mathscr{V}_x=\mathscr{V}_y$ for some $x,y\in\mathbb{R}$. $A_x\in\mathscr{V}_x$ and $A_y\in\mathscr{V}_y=\mathscr{V}_x$ so $A_x\cap A_y\in\mathscr{V}_x$. If $x\ne y$, $A_x\cap A_y$ is finite. But $\mathscr{V}_x$ is a non-principal ultrafilter, so it contains no finite sets, and therefore we must have $x=y$. Thus, $\{\mathscr{V}_x:x\in\mathbb{R}\}$ is a family of $2^\omega=\mathfrak{c}$ distinct non-principal ultrafilters on $\mathbb{Q}$ (and hence certainly an uncountable family).

Now let $S$ be any infinite set. $\mathbb{Q}$ is countable, so $|S|\ge|\mathbb{Q}|$, and there is therefore an injection $\varphi:\mathbb{Q}\to S$. For each $x\in\mathbb{R}$ let $$\mathscr{W}_x=\bigg\{W\subseteq S:\exists V\in\mathscr{V}_x\big[\varphi[V]\subseteq W\big]\bigg\}\;;$$ it’s not hard to check that $\mathscr{W}_x$ is a non-principal ultrafilter on $S$ and that $\mathscr{W}_x=\mathscr{W}_y$ if and only if $x=y$. Thus, $\{\mathscr{W}_x:x\in\mathbb{R}\}$ is a family of $2^\omega=\mathfrak{c}$ distinct non-principal ultrafilters on $S$.

As Carl mentioned in the comments, it’s actually possible to show that there are $2^{2^{|X|}}$ ultrafilters on any infinite set $X$, but that takes a bit more work. If I have time, I may add that argument later.

Added: Let $X$ be an infinite set. A family $\mathscr{A}$ of subsets of $X$ is independent if $$\bigcap_{A\in\mathscr{F}}A\cap\bigcap_{A\in\mathscr{G}}(X\setminus A)\ne\varnothing$$ whenever $\mathscr{F}$ and $\mathscr{G}$ are disjoint finite subsets of $\mathscr{A}$.

Theorem: (Hausdorff) Let $\kappa=|X|$; then there is an independent family $\mathscr{A}$ of subsets of $X$ such that $|\mathscr{A}|=2^\kappa$.

Assuming the theorem, it’s not hard to show that there are $2^{2^\kappa}$ ultrafilters on $X$. Let $\mathscr{A}$ be an independent family of subsets of $X$ such that $|\mathscr{A}|=2^\kappa$. For each $f:\mathscr{A}\to\{0,1\}$ and $A\in\mathscr{A}$ let $$\hat f(A)=\begin{cases}A,&f(A)=1\\X\setminus A,&f(A)=0\;,\end{cases}$$ and define $$\mathscr{F}_f=\left\{\bigcap_{A\in\mathscr{G}}:\hat f(A):\mathscr{G}\subseteq\mathscr{A}\text{ is finite}\right\}.$$ Clearly each $\mathscr{F}_f$ is closed under finite intersections and is therefore a filterbase on $X$. For each $f:\mathscr{A}\to\{0,1\}$ let $\mathscr{U}_f$ be an ultrafilter on $X$ extending $\mathscr{F}$. If $f,g:\mathscr{A}\to\{0,1\}$ are distinct, there is an $A\in\mathscr{A}$ such that $f(A)\ne g(A)$ and hence $\hat f(A)\cap \hat g(A)=\varnothing$; since $\hat f(A)\in\mathscr{U}_f$ and $\hat g(A)\in\mathscr{U}_g$, it follows that $\mathscr{U}_f\ne\mathscr{U}_g$. Thus, $$\left\{\mathscr{U}_f:f\in {}^\mathscr{A}\{0,1\}\right\}$$ is a family of $2^{2^\kappa}$ distinct ultrafilters on $X$. (Since every ultrafilter on $X$ is a subset of $\wp(X)$, it’s clear that there can be no more than this.)

Proof of Theorem: Let $Y=\{\langle F,\mathscr{H}\;\rangle:F\subseteq X\text{ is finite and }\mathscr{H}\subseteq\wp(F)\}$ For each $A\subseteq X$ let $$Y_A=\bigg\{\langle F,\mathscr{H}\;\rangle\in Y:A\cap F\in\mathscr{H}\bigg\},$$ and let $\mathscr{Y}=\big\{Y_f:f\in {}^X\{0,1\}\big\}$; clearly $|\mathscr{Y}|=2^{|X|}=2^\kappa$, and I claim that $\mathscr{Y}$ is an independent family of subsets of $Y$.

To see this, suppose that $\mathscr{F}$ and $\mathscr{G}$ are disjoint finite subsets of $\mathscr{Y}$, say $\mathscr{F}=\{Y_{A_1},\dots,Y_{A_m}\}$ and $\mathscr{G}=\{Y_{A_{m+1}},\dots,Y_{A_{m+n}}\}$. To show that $$Y_{A_1}\cap\dots\cap Y_{A_m}\cap (Y\setminus Y_{A_{m+1}})\cap\dots\cap(Y\setminus Y_{A_{m+n}})\ne\varnothing\;,$$ we must find $\langle F,\mathscr{H}\;\rangle\in Y$ such that $A_k\cap F\in\mathscr{H}$ for $k=1,\dots,m$ and $A_k\cap F\ne\mathscr{H}\;$ for $k=m+1,\dots,m+n$. The sets $A_k$ are all distinct, so for each pair of indices $\langle i,k\rangle$ such that $1\le i<k\le m+n$ there is an $x(i,k)\in X$ that belongs to exactly one of $A_i$ and $A_k$. Let $F=\{x(i,k):1\le i<k\le m+n\}$, and let $\mathscr{H}=\{A_k\cap F:1\le k\le m\}$; clearly $\langle F,\mathscr{H}\;\rangle\in Y$, and $A_k\cap F\in\mathscr{H}\;$ for $k=1,\dots,m$. Moreover, the choice of $F$ ensures that the sets $A_k\cap F$ ($k=1,\dots,m+n$) are all distinct, so $A_k\cap F\ne\mathscr{H}\;$ for $k=m+1,\dots,m+n$. Thus, $\mathscr{Y}$ is indeed independent.

To complete the proof, note that $|Y|=|X|=\kappa$, so there is a bijection $\varphi:Y\to X$. Let $\mathscr{A}=\{\varphi[S]:S\in\mathscr{Y}\}$; clearly $\mathscr{A}$ is an independent family of subsets of $X$ of cardinality $2^\kappa$.

-
There is a complete proof of the optimal result in Counterexamples in Topology #111 on the Stone-Cech compactification. – Carl Mummert Nov 19 '11 at 14:00
@Brian, this is an amazing proof! Thank you! – josh Nov 22 '11 at 22:02
The proof you give in the Added part is very close to Hausdorff's original one. Stefan Geschke has collected a number of arguments and references in a set of notes here (see also this MO thread $${}$$ A small TeX-remark: If you write f \in ^X \{0,1\} the X becomes a superscript of the \in symbol. To make this look a little better, use f \in {}^X \{0,1\}. Compare $f \in ^X \{0,1\}$ and $f \in {}^X \{0,1\}$. – t.b. Mar 12 '12 at 12:38
@t.b.: I discovered that later, in another post, though my solution was different: f\in{^X\{0,1\}} – Brian M. Scott Mar 12 '12 at 14:23
@Dune: Elementary. If $X$ is infinite, and $\mathscr{F}$ is the set of finite subsets of $X$, then $|\mathscr{F}|=|X|$. $\wp(F)$ is finite for each $F\in\mathscr{F}$, so the set of pairs $\langle F,\mathscr{H}\rangle$ with $\mathscr{H}\subseteq F$ is finite. Thus, $|Y|\le|X|\cdot\omega=|X|$, and obviously $|Y|\ge|X|$, so we get equality. – Brian M. Scott Apr 8 at 21:32
The idea is to build an embedding $E$ of the upside-down tree of all finite sequences of 0s and 1s into the collection of infinite subsets of $X$ in such a way that if sequences $\sigma$ and $\tau$ are incompatible then $E(\sigma)$ and $E(\tau)$ are disjoint, and if $\sigma$ is an initial segment of $\tau$ then $E(\tau)\subseteq E(\sigma)$.
The embedding is constructed inductively. Let $E$ send the empty sequence to $X$. Assuming $E$ is defined on a sequence $\sigma$ we divide $E(\sigma)$ into two disjoint infinite pieces, and let $E(\sigma + \langle 0\rangle)$ be one of them and $E(\sigma + \langle 1 \rangle)$ be the other. It can be verified without much work that $E$ has the desired properties.
Now any poset into which we can embed a binary tree in this way has to have at least $2^{\aleph_0}$ ultrafilters. Each $f \colon \mathbb{N} \to \{0,1\}$ gives a path through the infinite binary tree, and via $E$ that path becomes a decreasing sequence $E(f)$ in the poset. Any such sequence extends to an ultrafilter on the poset. On the other hand, two distinct paths $f,g$ must give distinct ultrafilters, because there will be a pair $p,q$ of incompatible elements of the poset such that $p \in E(f)$ and $q \in E(g)$. This $p,q$ can be found by looking at the place where $f$ and $g$ diverge in the binary tree.