Ultrafilters and self-injections

In this answer, if I understand it right, the following theorem is stated:

Let $X$ be a set and $f:X \to X$ an injective map. Let $\mathcal U$ be an ultrafilter on $X$ such that $f(U) \in \mathcal U$ for all $U \in \mathcal U$. Then $Fix(f) := \{x \in X \mid f(x) = x\} \in \mathcal U$.

I would be interested in a proof or a reference for this fact.

Thank you very much in advance!

Solution 1:

I know the following theorem on fixed point free mappings:

If $Y$ is a set and $f:Y \to Y$ has no fixed points, then there is a decomposition of $Y$ into three disjoint sets $Y_1,Y_2,Y_3$ such that $f(Y_k)\cap Y_k = \emptyset$ $(k=1,2,3)$.

In the case of the situation of the question assume that $Fix(f) \notin \mathcal{U}$. As $\mathcal{U}$ is an ultrafilter we have $$ Y:=X \setminus Fix(f)= \{x \in X: f(x)\not= x\} \in \mathcal{U}. $$ Since $f$ is injective we get $f(Y) \subseteq Y$. The decomposition above now satisfies $Y_1 \cup Y_2 \cup Y_3 \in \mathcal{U}$ and (again since $\mathcal{U}$ is an ultrafilter) $Y_j \in \mathcal{U}$ for at least one $j$. But then $f(Y_j) \in \mathcal{U}$, so $\emptyset \in \mathcal{U}$, a contradiction.

The theorem mentioned above can be found in

M. Katetov: A Theorem on mappings. Comment. Math. Univ. Carol. 8 (1967), 431-433.

Solution 2:

Consider the equivalence relation $E$ on $X$ generated by the relation $f(x) = y$ (the reflexive, symmetric, transitive closure of this relation). For each $E$-class $C$, $f$ restricts to an injective function $C\to C$, and $(C,f)$ is isomorphic to $(\mathbb{N},S)$, $(\mathbb{Z},S)$, or $(\mathbb{Z}/n\mathbb{Z},S)$ for some $n$, where $S(x) = x+1$ is the successor function in each case. For each $E$-class, pick an isomorphism with one of these three structures, so we can refer to the elements of $C$ by names from $\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{Z}/n\mathbb{Z}$.

Define a subset $Y\subseteq X$ which contains, for each $E$-class $C$: (1) the odd natural numbers, if $C\cong \mathbb{N}$, (2) the odd integers, if $C\cong \mathbb{Z}$, (3) the odd numbers $k$ with $0\leq k \leq n-1$, if $C\cong \mathbb{Z}/n\mathbb{Z}$.

Case 1: $Y\in U$. Then $f(Y)\in U$, but $Y\cap f(Y) = \varnothing$, contradiction.

Case 2: $Y\notin U$. Let $Z = X\setminus Y$, let $W = Z\cap f(Z)$, and note that $W\in U$. Now $W$ contains no elements of any $E$-class $C$ isomorphic to $\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{Z}/n\mathbb{Z}$ when $n$ is even, since $Z\cap C$ is the even elements of $C$, which are disjoint from their images under $f$. But $W$ contains exactly one element, $0$, from each $E$-class $C$ isomorphic to $\mathbb{Z}/n\mathbb{Z}$ when $n$ is odd (since $n-1$ and $0$ are both in $W$, and $f(n-1) = 0$).

Finally, let $W' = W\cap f(W)$. $W'$ contains exactly one element $0$, from each $E$-class $C$ isomorphic to $\mathbb{Z}/1\mathbb{Z}$, and no elements from any other classes. That is, $W' = \text{Fix}(f)$.

This answer is essentially the same as Gerd's, I've just wrapped in a proof of the theorem of Katetov referred to in Gerd's answer. The three sets $Y_1$, $Y_2$, and $Y_3$ in the theorem can be taken to be: $Y_1 = $ the odd elements from each class, $Y_2 = $ the even elements from each class (except not $0$ from $\mathbb{Z}/n\mathbb{Z}$ when $n$ is odd), and $Y_3 = $ the elements $0$ from each class isomorphic to $\mathbb{Z}/n\mathbb{Z}$ with $n$ odd.