# Rudin–Keisler equivalence

Wikipedia says that if $a\le b$ and $b\le a$ in Rudin–Keisler order for ultrafilters $a$ and $b$, then $a$ and $b$ are Rudin–Keisler equivalent. How to prove this?

-
Schroeder-Bernstein, restricted to suitable subsets of measure 1. – Andrés E. Caicedo Jan 24 '11 at 18:13
@Andres: 1. I don't understand how to apply Schroeder-Bernstein to my situation (Schroeder-Bernstein is a consequence of my statement, I don't see that it would be also vice versa). 2. About which measure do you speak? (My ultrafilters are not necessarily countable.) – porton Jan 24 '11 at 18:50
Yes, sorry, I am terribly busy at the moment, or I would have explained the terribly cryptic remark. Once/if I have some time, I'll try to make sense of it. – Andrés E. Caicedo Jan 24 '11 at 19:53
Porton, when someone says that a set $X$ has "measure one" with respect to an filter $F$, they just mean $X\in F$. Similarly, the measure zero sets are those whose complement are in the filter. And a set $X$ is said to have positive measure if it does not have measure zero (which is the same as measure one for ultrafilters, but for mere filters, it is a weaker notion). – JDH Jan 24 '11 at 21:34

By composing the two witness functions, it suffices to prove the following fact, which is due I think to Solovay.

Theorem. If $\mu$ is an ultrafilter on a set $I$ and $f:I\to I$ has the property that $X\in\mu\leftrightarrow f^{-1}X\in\mu$, then $f$ is the identity function on a set in $\mu$.

Proof. If we regard the function $f$ as a set of ordered pairs, it makes a directed graph on vertex set $I$. By the Axiom of Choice, let $D$ select exactly one member from each connected component of this graph. The components of this graph are the same as the equivalence classes under the relation $x\sim y\leftrightarrow f^i(x)=f^j(y)$ for some finite iterates $i$ and $j$ of $f$. Thus, for every point $x\in I$ there is a unique $y\in D$ such that $f^i(x)=f^j(y)$ for some finite iterates $i$ and $j$ of $f$. Let $A$ be the set of $x$ for which the minimal such $i+j$ is even. Note that if $f(x)\neq x$, then $x\in A\implies f(x)\notin A$, since there will be exactly one more application of $f$. In other words, if $E$ is the set of fixed points of $f$, then $A-E$ is disjoint from $f[A-E]$. From this, it follows by our assumption that $A-E\notin\mu$, since otherwise we would have $A-E\in\mu$ and hence $f[A-E]\in\mu$, but these are disjoint. Thus, $E\in\mu$, and so $f$ is the identity on a set in $\mu$. QED

This argument uses AC, and I think I recall hearing that AC is required. Thus, I would be very curious to see an argument appealing to Schroeder-Bernstein, since that argument does not use AC. But I suppose that there is a certain affinity of this argument and the Schroeder-Bernstein proof, and perhaps this is what Andres meant. (In any case, does anyone know a reference for showing that the result can fail without AC?)

-
@Joel: Doesn't another proof follow from the fact that if you have the reductions, then the corresponding embeddings "factor through each other"? – Andrés E. Caicedo Jan 24 '11 at 22:15
That is an interesting idea. But such a proof would reduce to the need to prove the implication that $j=h\circ j$ implies $h$ is the identity, where $j:V\to M$ and $h:M\to M$ are elementary embeddings. I know how to prove this when $j$ is an ultrapower, using the fact above, but I don't know any indepenent proof. I suspect that any proof would amount to an argument of the fact above, because the implication is not true of all embeddings---one can make a counterexample with an $\omega$-iteration of a measure. – JDH Jan 24 '11 at 23:22
I don't understand what you obtain by "composing the two witness functions". Isn't the obtained fact equivalence of the filter $a$ with itself (rather than with filter $b$)? – porton Jan 28 '11 at 17:27
Oh, I understood myself: If it is identity then it is decomposable into two converse bijections. – porton Jan 28 '11 at 17:31
Does the phrase "for some finite iterates $i$ and $j$ of $f$" imply $i,j>0$? – porton Apr 6 '11 at 20:10