Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
Schroeder-Bernstein, restricted to suitable subsets of measure 1. –  Andres 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. –  Andres 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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
@Joel: Doesn't another proof follow from the fact that if you have the reductions, then the corresponding embeddings "factor through each other"? –  Andres 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

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.