32
$\begingroup$

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.

$\endgroup$
2
  • 13
    $\begingroup$ 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$. $\endgroup$ Nov 19, 2011 at 1:12
  • 1
    $\begingroup$ Some references concerning the cardinality of set of ultrafilters are given in this answer: math.stackexchange.com/questions/34838/… $\endgroup$ Nov 19, 2011 at 10:13

5 Answers 5

39
$\begingroup$

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 distinct 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}=\{Y_A:A\subseteq X\}$; 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\notin\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\notin\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$.

$\endgroup$
21
  • 2
    $\begingroup$ There is a complete proof of the optimal result in Counterexamples in Topology #111 on the Stone-Cech compactification. $\endgroup$ Nov 19, 2011 at 14:00
  • 2
    $\begingroup$ @alancalvitti: Because mathematics, to the extent that it is done within any formal system, is done in ZFC. This is not something that needs to be mentioned. And anyone who really cares about such matters should certainly know that the ultrafilter extension theorem requires some of the strength of the axiom of choice. $\endgroup$ Jan 10, 2013 at 16:31
  • 2
    $\begingroup$ @alancalvitti: I said nothing about whether mathematics can be done in ZF+AD. $\endgroup$ Jan 10, 2013 at 19:31
  • 2
    $\begingroup$ @alancalvitti: The difference between is and can be seems pretty straightforward. $\endgroup$ Jan 10, 2013 at 19:35
  • 2
    $\begingroup$ @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. $\endgroup$ Apr 8, 2013 at 21:32
13
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is indeed very nice! $\endgroup$
    – t.b.
    Mar 12, 2012 at 12:03
4
$\begingroup$

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{D}$, 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)$ be distinct. 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.

$\endgroup$
3
  • $\begingroup$ What does "finite pointwise Boolean combination" mean? Using just $\sup$, $\inf$, negation, and finite amount of functions of the form $u_x$? $\endgroup$
    – Jakobian
    Jun 4, 2023 at 15:00
  • $\begingroup$ Thank you for this answer, I was wondering how to motivate the proof that there's $2^{2^{|X|}}$ ultrafilters on infinite set $X$ a little better. $\endgroup$
    – Jakobian
    Jun 4, 2023 at 15:19
  • $\begingroup$ That's correct. If you like, you could also say $D$ is the subring of $\{0,1\}^\mathcal{P(X)}$ (identifying $\{0,1\}$ with $\mathbb{Z}/2$) generated by the elements $u_x$. $\endgroup$ Jun 4, 2023 at 15:26
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The complement $\beta\mathbb N \setminus \mathbb N$ is a perfect set (and therefore uncountable), by the lemma below.

Lemma (courtesy of Alex Kruckman). $\beta\mathbb N \setminus \mathbb N$ is perfect.

It suffices to show that the set of non-principal ultrafilters has no isolated points. Equivalently, every basic open set in $\beta\mathbb{N}$ which contains a non-principal ultrafilter in fact contains more than one non-principal ultrafilter. Such a basic open set $U$ is the set of all ultrafilters containing some set $X\subseteq \mathbb{N}$. This set $X$ must be infinite (else it is not contained in any non-principal ultrafilter). Now pick an infinite and coinfinite subset $Y\subset X$ and find non-principal ultrafilters containing $Y$ and $X\setminus Y$ respectively. These are distinct elements of $U$, as desired.

$\endgroup$
2
  • $\begingroup$ @AlexKruckman, Nice argument! Do you mind if I include this in my answer? $\endgroup$ Dec 28, 2023 at 13:40
  • $\begingroup$ I don't mind at all. $\endgroup$ Dec 28, 2023 at 13:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .