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

  • 10
    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$.2011-11-19
  • 1
    Some references concerning the cardinality of set of ultrafilters are given in this answer: http://math.stackexchange.com/questions/34838/are-there-uncountably-many-non-homeomorphic-ways-to-topologize-a-countably-infin/34841#348412011-11-19

4 Answers 4

34

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

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

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

  • 2
    There is a complete proof of the optimal result in *Counterexamples in Topology* #111 on the Stone-Cech compactification.2011-11-19
  • 0
    @Brian, this is an amazing proof! Thank you!2011-11-22
  • 0
    The proof you give in the **Added** part is very close to [Hausdorff's original one](http://matwbn.icm.edu.pl/ksiazki/sm/sm6/sm612.pdf). Stefan Geschke has collected a number of arguments and references [in a set of notes here](http://www.hcm.uni-bonn.de/fileadmin/geschke/papers/IndependentFamilies_03.pdf) (see also [this MO thread](http://mathoverflow.net/questions/48914/) $${}$$ 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\}$.2012-03-12
  • 0
    @t.b.: I discovered that later, in another post, though my solution was different: `f\in{^X\{0,1\}}`2012-03-12
  • 0
    @t.b.: I think that I first saw that proof from Ken Kunen.2012-03-12
  • 0
    @BrianM.Scott, not that I can follow your proof, but why is there no mention of the set axioms? According to Herrlich's *AC*, there are no nontrivial ultrafilters on $\mathbb N$ in ZF+AD.2013-01-10
  • 1
    @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.2013-01-10
  • 0
    @BrianM.Scott, Interesting, so what MacLane told Bergman, that UCB mathematicians worship at the temple of ZFC, holds even outside of Berkeley? You seem to be saying that ZF+AD is not a formal systems within which math can be done - after all it precludes Banach-Tarski type decompositions, so it's an advantage in geometry.2013-01-10
  • 1
    @alancalvitti: I said nothing about whether mathematics **can** be done in ZF+AD.2013-01-10
  • 0
    "mathematics, to the extent that it is done within *any* formal system, is done in ZFC." How should I interpret your quantifier2013-01-10
  • 1
    @alancalvitti: The difference between **is** and **can be** seems pretty straightforward.2013-01-10
  • 0
    @BrianM.Scott, good 1. Aren't there other formal systems, like categories and "reverse mathematics" , in addition to multiple set theories?2013-01-10
  • 1
    @alancalvitti: There are quite a few formal systems. Reverse mathematics isn’t one of them, however; it’s a program for determining the strength of ordinary mathematical theorems. Yes, there are areas of mathematics in which a category-theoretic outlook is probably the norm. That, however, has no bearing on this particular answer.2013-01-10
  • 0
    @Brian, could it be, that you have a few typos with cardinalities in Hausdorff's theorem? You claim, that there is an $\mathcal{A}$ with cardinality $2^\kappa$, but you use the theorem to get an $\mathcal{A}$ with cardinality $2^{2^\kappa}$. On the other hand in the proof you claim $|\mathcal{Y}| = 2^{2^\kappa}$ where I think, it should be $2^\kappa$.2013-04-08
  • 0
    @Dune: Thanks very much! I sure did; I’m amazed that no one caught them before. I think that I’ve caught and fixed all of them now; let me know if you find any more.2013-04-08
  • 0
    @Brian, thanks - it looks good now. I just wonder, why $|Y| = |X|$ holds at the end of the proof. I am not very familiar with cardinality calculations. Could you give me a little hint? Does one need Zorn's lemma here or is there an elementary argument?2013-04-08
  • 1
    @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.2013-04-08
  • 0
    @Brian, great - thanks! :)2013-04-08
  • 0
    @Dune: My pleasure! And thanks again for catching those horrible typos.2013-04-08
10

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.

  • 0
    This is indeed very nice!2012-03-12
2

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.

1

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.