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

Is the Rudin-Keisler order of ultrafilters linear?

Is it a well ordering?

share|cite|improve this question
I changed the tags to set-theory and ultrafilters. – Joel David Hamkins Feb 27 '11 at 22:29
up vote 6 down vote accepted

This would be more suitable as a comment, but I do not have enough reputation points. Among the first results that google spits out for Rudin Keisler is the paper Anatoly Gryzlov: On the Rudin-Keisler order on ultrafilters; It claims that there are incomparable ultrafilters (with respect to R-K order) and provides several further references.

share|cite|improve this answer
Only now I noticed that you ask about "Kleister" not "Keisler". Typo, I guess? – Martin Sleziak Feb 27 '11 at 14:45

As Martin Sleziak already pointed out, there are Rudin-Keisler incomparable ultrafilters on $\omega$ (while Joel is talking about ultrafilters on a measurable cardinal). This is provable in ZFC.

Andreas Blass showed that under Martin's Axiom, there are actually $2^{\mathfrak c}$ pairwise R-K incomparable ultrafilters, i.e., as many as you could possibly have. Here $\mathfrak c$ is $2^{\aleph_0}$. He also showed that the real line can be embedded into the R-K order of ultrafilters on $\omega$ (this again assumes Martin's Axiom).
Blass' results actually talk about $P$-points, which need not exist at all by a result of Shelah.

share|cite|improve this answer
The ZFC proof of existence of RK-incomarable ultrafilters is due to Mary Ellen Rudin and Saharon Shelah ["Unordered types of ultrafilters" in Topology Proceedings 3 (1978) pp. 199-204]. They actually show that on any infinite cardinal $\kappa$ there are $2^{2^\kappa}$ pairwise RK-incomparable ultrafilters. – Andreas Blass Feb 27 '11 at 20:19

One often considers the Rudin-Keisler order in the large cardinal context of a measurable cardinal $\kappa$, where one considers only $\kappa$-complete nonprincipal ultrafilters on $\kappa$. So let me provide the answer for this context, which is that it is independent of ZFC whether the Rudin-Keisler order on such ultrafilters is linearly ordered.

Two ultrafilters are Rudin-Keisler equivalent if and only if they are isomorphic, if and only if they give rise to the same ultrapower embedding of the universe (I believe this was a topic of some of your previous MO questions). One ultrafilter $\mu$ is RK-below another $\nu$ if and only if the ultrapower $j_\nu$ by $\nu$ can be factored as $j_\nu=h\circ j_\mu$ for some elementary embedding $h:M_\mu\to M_\nu$. It follows that the Rudin-Keisler minimal ultrafilters are precisely the normal measures.

On the one hand, in the canonical inner model $L[\mu]$ having one measurable cardinal $\kappa$, it turns out that every ultrapower embedding by a $\kappa$-complete ultrafilter on $\kappa$ is equivalent to a finite iteration of $\mu$. That is, every $\kappa$-complete nonprincipal ultrafilter is Rudin-Keisler equivalent to a finite product $\mu^n$ of $\mu$ with itself. Such measures form an increasing $\omega$-sequence, and so in this model, the Rudin-Keisler order on measures on $\kappa$ is a linear order isomorphic to $\omega$.

On the other hand, in contrast, one can perform forcing so as to create many normal measures. In such a model, the Rudin-Keisler order cannot be linear, since normal measures, being minimal, are incomparable with respect to the Rudin-Keisler order.

Update. Meanwhile, the Rudin-Keisler order on this collection of ultrafilters is well-founded, which fulfills part of what you had requested. The reason is that we can associate to each $\kappa$-complete ultrafilter $\mu$ on $\kappa$ the least ordinal $\delta$ generating the whole embedding, that is, for which $M_\mu=\{j_\mu(f)(\delta)\mid f:\kappa\to V\}$. It turns out that $\mu\lt_{RK}\nu$ implies $\delta_\mu\lt \delta_\nu$, and so the Rudin-Keisler order is well-founded.

share|cite|improve this answer
Can you please provide a reference for the equivalence of the RK ordering and the ordering on induced elementary embeddings inherited from if a factoring exists? One direction is obvious, but a factoring need not be induced by an RK-reduction, so it isn't clear how one would even find a factoring that is. – vhspdfg Apr 20 at 1:41
If $j_\mu$ is factor of $j_\nu$, meaning that $j_\mu=k\circ j_\mu$ for some elementary map $k:M_\mu\to M_\nu$, then notice that $X\in\mu\iff [id]_\mu\in j_\mu(X)\iff k([id]_\mu)\in k(j_\mu(X))=j_\nu(X)$. But $k([id]_\mu)=[f]_\nu$ for some function $f$, and it follows easily that $\mu$ is reduced from $\nu$ via $f$ for the RK reduction. So if an ultrapower is a factor, then it is RK below. – Joel David Hamkins Apr 20 at 1:48

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.