The set of ultrafilters on an infinite set is uncountable

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.

Solution 1:

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$.

Solution 2:

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.

Solution 3:

Here are some arguments which are not fundamentally different from the ones in the other answers, but are possibly made more enlightening by being cast in the language of topology.

If $X$ is uncountable, there are uncountably many principal ultrafilters on $X$, so we may assume $X$ is countable. In particular, we can identify $X$ with $\mathbb{Q}$. Now in any topological space $S$, if $D\subseteq S$ and $x\in\overline{S}$, there is an ultrafilter on $D$ which converges to $s$ (proof: take the filter of neighborhoods of $x$ intersected with $D$ and extend it to an ultrafilter). In particular, considering $D=\mathbb{Q}$ and $S=\mathbb{R}$, for each $x\in\mathbb{R}$ there is an ultrafilter on $\mathbb{Q}$ converging to $x$. Since $\mathbb{R}$ is Hausdorff, a filter cannot have more than one limit, and so these ultrafilters corresponding to each point of $\mathbb{R}$ must be distinct. This gives uncountably many distinct ultrafilters on $\mathbb{Q}$.

More generally, the same reasoning shows that if $S$ is a Hausdorff space with a dense subset $D$, then there are at least $|S|$ different ultrafilters on $D$. Given any set $X$, we can take $S=\{0,1\}^X$, and $D$ to be the set of points that are $0$ on all but finitely many coordinates. If $X$ is infinite then $|D|=|X|$, and we conclude that there are at least $|S|=2^{|X|}$ ultrafilters on $X$.

We can use a similar but trickier construction to prove the sharp lower bound of $2^{2^{|X|}}$ ultrafilters. Let $S=\{0,1\}^{\mathcal{P}(X)}$. For each $x\in X$, we have a map $u_x:\mathcal{P}(X)\to \{0,1\}$ given by $u_x(A)=1$ iff $x\in A$. Now let $D$ be the set of functions $\mathcal{P}(X)\to\{0,1\}$ which can be written as a finite pointwise Boolean combination of functions of the form $u_x$. Clearly $|D|=|X|$ if $X$ is infinite, and I claim $D$ is dense in $S$.

To prove this, let $A_1,\dots,A_n\in\mathcal{P}(X)$. We can find a finite subset $X_0\subset X$ such that $A_1\cap X_0,\dots, A_n\cap X_0$ are all distinct. The functions $u_x$ for $x\in X_0$ generate the Boolean algebra of all functions $\mathcal{P}(X_0)\to \{0,1\}$ (the characteristic function of any singleton $\{B\}\subseteq\mathcal{P}(A_0)$ is just the join of all the $u_x$ for $x\in B$ and the negations of the $u_x$ for $x\not\in B$). In particular, we can find a Boolean combination of the $u_x$ for $x\in X_0$ which takes arbitrary specified values on the sets $A_1\cap X_0,\dots,A_n\cap X_0$ and thus will take the same values on $A_1,\dots,A_n$. This exactly proves that $D$ is dense in $S=\{0,1\}^{\mathcal{P}(X)}$ in the product topology. Since $S$ is Hausdorff and has $2^{2^{|X|}}$ points, this shows there are $2^{2^{|X|}}$ ultrafilters on $D$ and hence on $X$. (For more discussion of this construction, see Is $2^{\frak{c}}$ separable?.)

The arguments above are all in the spirit of Brian Scott's answer, just in the language of topology. Here is a topological argument which is instead along the lines of Carl Mummert and Alex Ravsky's answers. Note that the set of nonprincipal ultrafilters on a set $X$ can naturally be identified with the Stone space of the the Boolean algebra $\mathcal{P}(X)/\mathrm{fin}$, where $\mathrm{fin}$ is the ideal of finite subsets of $X$. This Stone space is compact Hausdorff, nonempty if $X$ is infinite, and has no isolated points since $\mathcal{P}(X)/\mathrm{fin}$ is atomless (given an infinite subset of $X$, we can partition it into two infinite subsets). But a nonempty compact Hausdorff space with no isolated points is uncountable, so there are uncountably many nonprincipal ultrafilters if $X$ is infinite.

Solution 4:

Assume to the contrary that $\{\mathcal F_n:n\in\Bbb N\}$ is a sequence of all distinct ultrafilters on the set $X$. Put $F_0=X$ and inductively for each natural $n$ choose any proper infinite subset $F_n\not\in \mathcal F_n$ of $F_{n-1}$ and any point $x_n\in F_n\setminus F_{n-1}$. For each natural $n$ put $F’_n=\{x_m:m\ge n\}$. Then $F’_n\not\in\mathcal F_{n}$. Hence a filter $\mathcal F=\{F’_n:n\in\Bbb N\}$ cannot be contained in any ultrafilter on $X$, a contradiction.