MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

ZF (if consistent) has models where $\omega$ supports no non-principal ultrafilters and others where it supports $2^c$ such. Can other cardinals occur? Or does the existence of just one somehow entail the existence of $2^c$.

share|cite|improve this question
up vote 10 down vote accepted

Much of the following is David Feldman's argument in one of the comments, but with the topology replaced by combinatorics. There is, however, one slightly tricky point, arising from the fact that, in the absence of choice, the existence of a surjection from one set to another does not imply that the former set has at least the same cardinality as the latter.

Without any form of choice, we can get a family $X$ of $c$ independent subsets of $\omega$ (where "independent" means that the intersection of any finitely many of these sets and the complements of any finitely many others is infinite). Then any subfamily $Y$ of $X$ gives rise to the filter $F(Y)$ generated by the sets in $Y$ and the complements of the sets in $X-Y$. These filters are pairwise incompatible (i.e., the union of any two contains two complementary subsets of $\omega$), so no ultrafilter extends more than one of the $F(Y)$'s. Thus, we have a function $f$ assigning to each ultrafilter $U$ on $\omega$ the unique $F(Y)$ included in $U$ (or some fixed $F(Y)$, say $F(X)$, if $U$ includes no $F(Y)$).

Now if we assume the Boolean Prime Ideal Theorem (without which we're not guaranteed any nontrivial ultrafilters), we can extend each $F(Y)$ to an ultrafilter and thereby conclude that $f$ maps onto the whole set of $F(Y)$'s, a set of size $2^c$. By itself, that doesn't yet ensure that there are at least $2^c$ ultrafilters on $\omega$; existence of a surjection from one set to another does not in general (without choice) imply existence of an injection in the other direction.

In this case, however, it seems that BPIT enables us to select, for each $Y\subseteq X$, one ultrafilter extending $F(Y)$. That will give a one-to-one map from the set of $2^c$ $Y$'s into the set of ultrafilters. To prove that BPIT gives the desired selection, proceed as follows. Let $P$ be the product of $2^c$ copies of $\omega$, indexed by the subsets $Y$ of $X$; let $p_Y$ be the projection from $P$ to the $Y$'th factor $\omega$. For each $Y$, the filter $F(Y)$ can be "cylindrified" to produce the filter $F'(Y)$ on $P$ generated by the sets ${p_Y}^{-1}(A)$ for $A\in F(Y)$. These filters $F'(Y)$, for all $Y\subseteq X$, are coherent; their union generates a filter $F''$ on $P$. By BPIT, there is an ultrafilter $U$ on $P$ extending $F''$. The projections $p_Y(U)=\{A\subseteq\omega:{p_Y}^{-1}(A)\in U\}$ are ultrafilters on $\omega$ extending the corresponding $F(Y)$.

Conclusion: BPIT implies the existence of $2^c$ ultrafilters on $\omega$.

share|cite|improve this answer
@Andreas : Nice idea! – Andrés E. Caicedo Dec 20 '10 at 23:33
I just want to point out, provided I understand correctly, that since you must use BPIT on that large Boolean algebra, you still stand by your first comment below. – David Feldman Dec 20 '10 at 23:49
@David: Yes, I still stand by my earlier comment. – Andreas Blass Dec 21 '10 at 0:09
@David : As Andreas, I also think that what we usually simply call $L({\mathbb R})[U]$ has precisely ${\mathfrak c}$ ultrafilters on $\omega$. You may consider asking S. Thomas, who has thought about this model before. – Andrés E. Caicedo Dec 21 '10 at 0:46

Let me start things off by observing that if there is an ultrafilter on $\omega$, then there are at least $2^\omega$ many ultrafilters, as follows. By labeling the nodes of the tree $2^{\lt\omega}$ one can build a family of continuum many infinite subsets of $\omega$ with pairwise finite intersection (an almost disjoint family). Each set in the family is isomorphic to $\omega$, and hence has the induced isomorphic ultrafilter, but since these sets are almost disjoint, they give rise to distinct ultrafilters on $\omega$.

In this way, one builds continuum many ultrafilters from one, without using AC.

To get $2^c$ many ultrafilters, however, the ZFC argument I know uses well-orders in a strong way, and so I'm not sure how one might do it without any AC. I guess by $2^c$ one should mean a bijection between the collection of ultrafilters and $P(\mathbb{R})$.

share|cite|improve this answer
I suspect that if you start with a model of determinacy and force to adjoin a nontrivial ultrafilter on $\omega$ (using infinite subsets of $\omega$ as forcing conditions), then the only ultrafilters in the resulting model should be the ones you get from the generic one and principal ones by iteratively taking limits (of previously produced ultrafilters along previously produced ultrafilters). I further suspect that this will produce altogether just continuum many ultrafilters. – Andreas Blass Dec 18 '10 at 23:28
>To get $2^c$ many ultrafilters, however, the ZFC argument I know uses well-orders in a strong way... Here's my simplification of the argument in Gillman and Jerison: Write $X$ for the set of all function $[0,1]$ to $\{0,1\}$. $X$ has cardinality $2^c$. Now topologize $X$ as a product of $c$ copies of $\{0,1\}$. $X$ is compact. Write $Y$ for the set of functions in $X$ with only finitely many discontinuities, only at rational numbers. $Y$ is countable and dense in $X$. $\omega$ bijects with $Y$. Maximal compactification at least as large. No well-orders!! – David Feldman Dec 19 '10 at 0:09
David, that's an interesting argument, but can we expect the maximal compactification to exist without assuming lots of ultrafilters in the first place? – Joel David Hamkins Dec 19 '10 at 0:28
@Joel Re: "but can we expect...?" No. But the points of my big compactification yield big filters, and the Boolean Prime Ideal Theorem promises you that can extend each of these to (distinct) ultrafilters. So the Boolean Prime Ideal Theorem guarantees $2^c$ ultrafilters without using the well-ordering principle. In fact, ZF+BPIT is a weaker system than ZFC. – David Feldman Dec 19 '10 at 2:02
David, using only BPIT, do you still know that X is compact? That would seem to use Tychonoff's theorem. – Joel David Hamkins Dec 19 '10 at 12:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.