# Equivalence of two definitions of Rudin–Keisler equivalence

Let $U$ is an ultrafilter on a set $X$, and $V$ an ultrafilter on a set $Y$.

Wikipedia says: Ultrafilters $U$ and $V$ are Rudin–Keisler equivalent, $U\equiv_{RK}V$, if there exist sets $A\in U$, $B\in V$, and a bijection $f: A → B$ which satisfies the condition above. (If $X$ and $Y$ have the same cardinality, the definition can be simplified by fixing $A = X$, $B = Y$.)

where "the condition above" is:

$$C\in V\iff f^{-1}[C]\in U.$$

How to prove that the special case of the same cardinality is equivalent to the case of arbitrary $X$ and $Y$?

-
I'm not sure I get the question. –  Asaf Karagila Mar 4 '11 at 14:07
@Asaf Karagila: It's needed to prove that "If $X$ and $Y$ have the same cardinality, the definition can be simplified by fixing $A=X$, $B=Y$." –  porton Mar 4 '11 at 14:11
Isn't it trivial? What is it to have the same cardinality? It means that there is a bijection from the two sets. –  Asaf Karagila Mar 4 '11 at 14:17
@Asaf Karagila: It seems that it isn't trivial and requires that the filters $U$ and $V$ are ultrafilters. For $X$ and $Y$ to have the same cardinality means that there are a bijection from $X$ to $Y$. But how you'd use this bijection to prove that the definition can be simplified? –  porton Mar 4 '11 at 14:23
@Porton: You forgot to add that $U$ is an ultrafilter on $X$ and $V$ is an ultrafilter on $Y$. –  Andres Caicedo Mar 4 '11 at 16:17

Assume that we have $|X|=|Y|$, let $\mathcal{U}$, $\mathcal{V}$ ultarfilters on $X$ and $Y$ respectively and let $A\in\mathcal{U}$, $B\in\mathcal{V}$ and a bijection $f:A\to B$ such that $C\in\mathcal{V}\iff f_{-1}[C]\in\mathcal{U}$.

Observe that if $|X-A|=|Y-B|$ you are done since both these sets are not in $\mathcal{U}$ and $\mathcal{V}$ (respectively) and you can extend $f$ arbitrarily at these points. Now assume that $|X-A|<|Y-B|$. Let $B'\supset B$ such that $|X-A|=|Y-B'|$ while $|B|=|B'|$ (such $B'$ exists; to see this observe that $|B|=|Y|$). We need to find a bijection $g:B\to B'$ that satisfies the condition of RK. Then we would be done, since we would be able to extend $g\circ f$ as I described above. Let $D=B'\setminus B$ and notice that $D\notin\mathcal{V}$. Let $E\subset B$ an infinite set of size greater than or equal to that of $D$ such that $E\notin\mathcal{V}$. Let $h:E\to D\cup E$ some arbitrary bijection and let $g$ be the identity for every $x\in B\setminus E$ and equal to $h$ for the elements of $E$. This is the $g$ we are looking for.

-
I doubt injectivity of $g$ because I do not see that $(D\cup E) \cap (B\setminus E) = \emptyset$. Also I have not yet checked that $g$ conforms to RK condition. It seems for me that your proof is flawed, but I may mistake. –  porton Apr 26 '11 at 16:42
@porton:Indeed you are correct. But you can circumvent that by defining $D=B'\setminus B$ and using as $E$ an infinite set with cardinality greater than or equal to that of $D$. I will edit my answer later on. –  Apostolos Apr 26 '11 at 17:26
I have followed your proof and found it correct (not mentioning little omissions) writing more detailed version of the proof in my draft. If you want to be acknowledged in the article I am writing, you probably should tell me your real full name. –  porton Apr 26 '11 at 18:38
I hope the following works: Let $U, V$ be ultrafilters on $X$ and $Y$ respectively. One side is clear. If there is a bijection $f\colon X\rightarrow Y$ satisfying RK-condition then the restriction of $f$ to any $A\in U$ satisfies RK-condition and it is a bijection.
Now the other side: Assume that there is $A,B$ and a bijection $f\colon A\rightarrow B$ satisying RK-condition as given in the wikipedia page. Hence, we know that $f$ is defined at every point of $U,$ because $f$ satisfies RK-condition by assumption. Hence, we have a function $f\colon X\rightarrow Y$ and we want to show that it is 1-1 and onto. If $f$ is not onto, then $\exists C\subset Y$ such that $f(X)\cap C=\emptyset.$ Then trivially $f^{-1}(C)=\emptyset\in U$ by the RK-condition. This certainly not possible. Hence $f$ is onto.
Now, suppose that $f\colon X\rightarrow Y$ is not 1-1. This means there are $x_1,x_2\in X$ $x_1\neq x_2$ but $f(x_1)=f(x_2).$ Let $K:=\left\{x_1,x_2\right\}\subset X.$ If $K\cap A=\emptyset$ and $K\notin U$ then consider the set $A\cup K\in U$ since $U$ is an ultrafilter. The set $f(A\cup K)=f(A)\cup f(K)$ where $f(K)$ is a one point set. But since $V$ is an ultrafilter and $B\in B$ we necessarily have $f(K)\subset B$ which contradicts to $A\cap K=\emptyset.$ Hence, $A\cap K\neq \emptyset.$ $K$ contains two points. But these two points cannot be in $A$ simultaneously, because $f$ is a bijection on $A$. Therefore, WLOG say $x_1\in A$ and $x_2\notin A.$ But then consider $f(A)\in V.$ $f(A)$ contains $f(x_1).$ By RK-condition again inverse image $f^{-1}f(A)=A$ should contain $x_2$ too. This is again a contradiction.
Hence, $f\colon X\rightarrow Y$ is 1-1 and onto.
You say "$f$ is defined at every point of $U$". What "a point of $U$" means? –  porton Apr 20 '11 at 13:52
Your proof is clearly wrong: "Hence, we know that $f$ is defined at every point of $U$, because $f$ satisfies RK-condition by assumption." is a nonsense because the condition need to be satisfied only by subsets $C$ of $Y$. Please consult Wikipedia for details. –  porton Apr 26 '11 at 16:53