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?
Rudin–Keisler equivalence
-
0Schroeder-Bernstein, restricted to suitable subsets of measure 1. – 2011-01-24
-
0@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.) – 2011-01-24
-
0Porton, 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). – 2011-01-24
1 Answers
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?)
-
0@Joel: Doesn't another proof follow from the fact that if you have the reductions, then the corresponding embeddings "factor through each other"? – 2011-01-24
-
0That 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. – 2011-01-24
-
0I 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$)? – 2011-01-28
-
0Oh, I understood myself: If it is identity then it is decomposable into two converse bijections. – 2011-01-28
-
0Does the phrase "for some finite iterates $i$ and $j$ of $f$" imply $i,j>0$? – 2011-04-06
-
0@JDH: Your proof is with an error. The relation of two elements to lie in the same connected component is defined by the formula $x\sim y \Leftrightarrow \exists i,j \in \mathbb{N} : ( y = f^i(x) \wedge x = f^j(y) )$ not $x\sim y\leftrightarrow \exists i,j \in \mathbb{N} : f^i(x)=f^j(y)$ – 2011-04-06
-
0@JDH Just a small correction: Given this definition of $A$, it's not necessarily true that $x\in A\implies x\notin A$. For example, in a $5$-cycle there are two elements that are minimal distance $2$ from the chosen $y$, and one maps to the other via $f$. – 2016-03-30
-
0In his article *Ultrafilters and set theory*, Blass writes "For any function $f\colon X\to X$, there is a partition of $\{x\in X\mid f(x)\neq x\}$ into three pieces, each disjoint from its image under $f$... The proof of this fact proceeds by a direct analysis of functions $f$, best viewed as directed graphs with an arrow from each $x$ to $f(x)$. Were it not for cycles of odd length $\geq 3$, partitions into two parts would suffice. The third part is used for exactly one point on each odd cycle; that decision essentially forces the rest of the construction of the partition." – 2016-03-30
-
0Yes, this uniform two-piece argument is not quite right. But it is easy to fix, along the lines suggested by Alex. Alternatively, just argue like this: if the ultrafilter concentrates on cycles, then it is easy; and otherwise, the problematic issue disappears. Blass's idea is a uniform treatment that avoids the need to consider cases. – 2016-04-02