Return to Answer

Proof that $h_*(\mathcal W) = \mathcal W$ implies $[h]_\mathcal W= [\text{id}]_\mathcal W$: Assume not, and so without loss of generality $h(x) \neq x$ for all $x\in X$. Consider the graph $G$ with vertex set $X$ and edge set $E = \{\{x,y\}\in [X]^2 : h(x) = y\}$. We claim $G$ is $3$-colorable. Any finite connected induced subgraph $H$ of $G$ with $n$ vertices contains at most $n$ edges (as $x\mapsto \{x,f(x)\}$ is a partial surjection). A finite graph with fewer edges than vertices is a tree and so is 2-colorable. Therefore removing one edge of $H$ yields a $2$-colorable graph, and this easily implies $H$ is $3$-colorable. By compactness, $G$ is $3$-colorable. Therefore there is a partition $\{A_0, A_1, A_2\}$ of $X$ such that $G\restriction A_n$ is discrete for $n =0,1,2$. This means that $h^{-1}[A_n]\cap A_n\neq \emptyset$ for $n =0,1,2$. Therefore if $A_n\in \mathcal W$, then $A_n\notin h_*(\mathcal W) =\mathcal W$, contradiction.

Proof that $h_*(\mathcal W) = \mathcal W$ implies $[h]_\mathcal W= [\text{id}]_\mathcal W$: Assume not, and so without loss of generality $h(x) \neq x$ for all $x\in X$. Consider the graph $G$ with vertex set $X$ and edge set $E = \{\{x,y\}\in [X]^2 : h(x) = y\}$. We claim $G$ is $3$-colorable. Any finite connected induced subgraph $H$ of $G$ with $n$ vertices contains at most $n$ edges (as $x\mapsto \{x,f(x)\}$ is a partial surjection), and hence contains at most one cycle. Therefore removing at most one edge of $H$ yields an acyclic and hence 2-colorable graph, and this easily implies $H$ is $3$-colorable. By compactness, $G$ is $3$-colorable. Therefore there is a partition $\{A_0, A_1, A_2\}$ of $X$ such that $G\restriction A_n$ is discrete for $n =0,1,2$. This means that $h^{-1}[A_n]\cap A_n\neq \emptyset$ for $n =0,1,2$. Therefore if $A_n\in \mathcal W$, then $A_n\notin h_*(\mathcal W) =\mathcal W$, contradiction.

If one allows an arbitrary signature, the answer to this question is fairly well-known. Consider the structure $(\lambda,A)_{A\subseteq \lambda}$. Let $(M,R_A)_{A\subseteq \lambda}$ be the common ultrapower by $\mathcal U$ and $\mathcal V$. Note that $A\in \mathcal U$ if and only if $[\text{id}]_U \in R_A$ by the definition of an ultrapower. Fix functions $f,g:\lambda\to \lambda$ such that $[f]_\mathcal V = [\text{id}]_\mathcal U$ and $[g]_\mathcal U = [\text{id}]_\mathcal V$. We have $f_*(\mathcal V) = \mathcal U$: for any $A\subseteq \lambda$, $A\in \mathcal U$ if and only if $[\text{id}]_\mathcal U\in R_A$ or equivalently $[f]_\mathcal V\in R_A$, which by definition means $\{\alpha < \lambda : f(\alpha) \in A\}\in \mathcal V$ or $f^{-1}[A]\in \mathcal V$; that is, $A\in f_*(\mathcal V)$. Similarly $g_*(\mathcal U) = \mathcal V$. It follows that $(g\circ f)_*(\mathcal V) = \mathcal U$. A fundamental theorem (discovered independently by Rudin, Keisler, Blass and others by Katetov, proof below) states that for any ultrafilter $\mathcal W$ over $X$ and any $h :X\to X$, if $h_*(\mathcal W) = \mathcal W$ then $[h]_\mathcal W =[\text{id}]_\mathcal W$ Therefore $[g\circ f]_\mathcal V = [\text{id}]_\mathcal V$. Hence there is a set $A\in \mathcal V$ such that $g\circ f\restriction A$ is the identity. In other words, $f$ is one-to-one on a set in $\mathcal V$. It is then not hard to modify $f$ on a null set to make it a permutation.

If one allows an arbitrary signature, the answer to this question is fairly well-known. Consider the structure $(\lambda,A)_{A\subseteq \lambda}$. Let $(M,R_A)_{A\subseteq \lambda}$ be the common ultrapower by $\mathcal U$ and $\mathcal V$. Note that $A\in \mathcal U$ if and only if $[\text{id}]_U \in R_A$ by the definition of an ultrapower. Fix functions $f,g:\lambda\to \lambda$ such that $[f]_\mathcal V = [\text{id}]_\mathcal U$ and $[g]_\mathcal U = [\text{id}]_\mathcal V$. We have $f_*(\mathcal V) = \mathcal U$: for any $A\subseteq \lambda$, $A\in \mathcal U$ if and only if $[\text{id}]_\mathcal U\in R_A$ or equivalently $[f]_\mathcal V\in R_A$, which by definition means $\{\alpha < \lambda : f(\alpha) \in A\}\in \mathcal V$ or $f^{-1}[A]\in \mathcal V$; that is, $A\in f_*(\mathcal V)$. Similarly $g_*(\mathcal U) = \mathcal V$. It follows that $(g\circ f)_*(\mathcal V) = \mathcal U$. A fundamental theorem (discovered independently by Rudin, Keisler, Blass Katetov, Frolík, and maybe others, proof below) states that for any ultrafilter $\mathcal W$ over $X$ and any $h :X\to X$, if $h_*(\mathcal W) = \mathcal W$ then $[h]_\mathcal W =[\text{id}]_\mathcal W$ Therefore $[g\circ f]_\mathcal V = [\text{id}]_\mathcal V$. Hence there is a set $A\in \mathcal V$ such that $g\circ f\restriction A$ is the identity. In other words, $f$ is one-to-one on a set in $\mathcal V$. It is then not hard to modify $f$ on a null set to make it a permutation.

If one allows an arbitrary signature, the answer to this question is fairly well-known. Consider the structure $(\lambda,A)_{A\subseteq \lambda}$. Let $(M,R_A)_{A\subseteq \lambda}$ be the common ultrapower by $\mathcal U$ and $\mathcal V$. Note that $A\in \mathcal U$ if and only if $[\text{id}]_U \in R_A$ by the definition of an ultrapower. Fix functions $f,g:\lambda\to \lambda$ such that $[f]_\mathcal V = [\text{id}]_\mathcal U$ and $[g]_\mathcal U = [\text{id}]_\mathcal V$. We have $f_*(\mathcal V) = \mathcal U$: for any $A\subseteq \lambda$, $A\in \mathcal U$ if and only if $[\text{id}]_\mathcal U\in R_A$ or equivalently $[f]_\mathcal V\in R_A$, which by definition means $\{\alpha < \lambda : f(\alpha) \in A\}\in \mathcal V$ or $f^{-1}[A]\in \mathcal V$; that is, $A\in f_*(\mathcal V)$. Similarly $g_*(\mathcal U) = \mathcal V$. It follows that $(g\circ f)_*(\mathcal V) = \mathcal U$. A fundamental theorem (discovered independently by Rudin, Keisler, Blass and others, proof below) states that for any ultrafilter $\mathcal W$ over $X$ and any $h :X\to X$, if $h_*(\mathcal W) = \mathcal W$ then $[h]_\mathcal W$. Therefore $[g\circ f]_\mathcal V = [\text{id}]_\mathcal V$. Hence there is a set $A\in \mathcal V$ such that $g\circ f\restriction A$ is the identity. In other words, $f$ is one-to-one on a set in $\mathcal V$. It is then not hard to modify $f$ on a null set to make it a permutation.

If one allows an arbitrary signature, the answer to this question is fairly well-known. Consider the structure $(\lambda,A)_{A\subseteq \lambda}$. Let $(M,R_A)_{A\subseteq \lambda}$ be the common ultrapower by $\mathcal U$ and $\mathcal V$. Note that $A\in \mathcal U$ if and only if $[\text{id}]_U \in R_A$ by the definition of an ultrapower. Fix functions $f,g:\lambda\to \lambda$ such that $[f]_\mathcal V = [\text{id}]_\mathcal U$ and $[g]_\mathcal U = [\text{id}]_\mathcal V$. We have $f_*(\mathcal V) = \mathcal U$: for any $A\subseteq \lambda$, $A\in \mathcal U$ if and only if $[\text{id}]_\mathcal U\in R_A$ or equivalently $[f]_\mathcal V\in R_A$, which by definition means $\{\alpha < \lambda : f(\alpha) \in A\}\in \mathcal V$ or $f^{-1}[A]\in \mathcal V$; that is, $A\in f_*(\mathcal V)$. Similarly $g_*(\mathcal U) = \mathcal V$. It follows that $(g\circ f)_*(\mathcal V) = \mathcal U$. A fundamental theorem (discovered independently by Rudin, Keisler, Blass and others by Katetov, proof below) states that for any ultrafilter $\mathcal W$ over $X$ and any $h :X\to X$, if $h_*(\mathcal W) = \mathcal W$ then $[h]_\mathcal W =[\text{id}]_\mathcal W$ Therefore $[g\circ f]_\mathcal V = [\text{id}]_\mathcal V$. Hence there is a set $A\in \mathcal V$ such that $g\circ f\restriction A$ is the identity. In other words, $f$ is one-to-one on a set in $\mathcal V$. It is then not hard to modify $f$ on a null set to make it a permutation.