# Is the Rudin-Keisler order of ultrafilters linear?

Is the Rudin-Keisler order of ultrafilters linear?

Is it a well ordering?

-
I changed the tags to set-theory and ultrafilters. – Joel David Hamkins Feb 27 '11 at 22:29

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; http://dx.doi.org/10.1016/S0166-8641(96)00109-5 It claims that there are incomparable ultrafilters (with respect to R-K order) and provides several further references.

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

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.

-
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

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.

-
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