# 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 '13 at 21:32

Here is the first argument I alluded to in my comments. I think it may convey a little more of the way I look at these things.

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.

I personally find this method very visual, and easier to follow than some other methods. It shows concretely how the structure of the poset itself is reflected in the collection of ultrafilters.

-
This is indeed very nice! –  t.b. Mar 12 '12 at 12:03