Rudin–Keisler equivalence

Question

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?

Answer 1

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?)