# Periodic point-free maps and free ultrafilters.

Let $X$ be a set and $u$ be a free ultrafilter on $X$. We can consider a topology on $X$ by declaring every element of $u \cup \{\emptyset \}$ to be open.

El'kin's original motivation for looking at this topology is that $X$ is a space without isolated points which can't be split into disjoint dense subspaces. Another quirky feature: if $X$ is say $\mathbb{R}$ then translations are not continuous. This last fact makes me wonder: are there any periodic-point free continuous self maps at all on $X$ with this topology? In other words:

Is there a free ultrafilter $u$ on a set $X$ and a periodic point-free onto map $f: X \to X$ such that: $f^{-1}(A) \in u$, for every $A \in u$? Is there at least one such fixed-point free map?

-
Someone has apparently down-voted all three answers, but I'm unsure what the objection might be. –  Joel David Hamkins Mar 11 '13 at 10:19

Your question has been answered by Joseph with several references, but since this nice result has several attractive proofs, let me try to provide one.

Theorem. If $\mu$ is an ultrafilter on a set $X$ and $f:X\to X$ has the property that $A\in\mu\leftrightarrow f^{-1}A\in\mu$, then $f(x)=x$ for $\mu$-almost all $x$.

Proof. Consider the function $f$ as a directed graph, where each point $x$ has an edge to $f(x)$.

Suppose first that $\mu$ happens to concentrate on the set $A$ of points lying on a finite cycle. By the axiom of choice, let $D\subset A$ be a maximal set of non-adjacent points in $A$. So $D$ contains at least one of $a$, $f(a)$ and $f(f(a))$ for any $a\in A$. It follows that $A\subset D\cup f^{-1}D\cup f^{-2}D$, and so one of these sets must be in $\mu$. The main hypothesis then implies that actually all of these sets are in $\mu$. But notice that any point $y\in D\cap f^{-1}D$ must have $f(y)=y$, since otherwise $y$ and $f(y)$ would be adjacent points in $D$. So $\mu$ concentrates on fixed points of $f$, as desired.

To see that this is the only case, suppose next towards contradiction that $\mu$ concentrates on the set $B$ of points that are not yet on a cycle, but whose iterates eventually reach a cycle. Let $B_0$ be those points in $B$ that reach their cycle first after an even number of iterations of $f$, and $B_1$ the points that do so first after an odd number of iterates. These sets are disjoint, but $f^{-1}B_0\subset B_1$ and $f^{-1}B_1\subset B_0$, and so actually neither can be in $\mu$, contradicting $B=B_0\sqcup B_1\in\mu$.

Finally, assume toward contradiction that $\mu$ concentrates on the set $C$ of points whose iterates are not eventually periodic. This set is the union of those connected components of the graph that do not contain a cycle. (Each such component is therefore a tree.) By the axiom of choice, let $D$ select exactly one point from each component of $C$. Let $C_0$ be the points in $C$ whose shortest distance to a point in $D$ has even length, and $C_1$ the points with odd distance to $D$. Thus, $C=C_0\sqcup C_1$ is a partition of $C$, and $f^{-1}C_1\subset C_0$ and $f^{-1}C_1\subset C_0$, since applying $f$ once will change the distance by exactly one. So again, neither set can be in $\mu$, since either would force the other also into $\mu$, contradicting that they are disjoint.

So the only possible case is that $\mu$ concentrates on the fixed points of $f$. QED

The theorem appears to be first proved by Katetov, Commentations Math Univ Carolinae 8 (1967), 432-433, with a related result given by Frolik 1968, and Andreas Blass's dissertation (1970).

You may also be interested in the proof of the theorem written by Bob Solovay.

Finally, I note that the proof uses the axiom of choice, and I am given to understand that the theorem is not provable in ZF. Perhaps someone else can post an answer explaining how a positive answer to your question is consistent with ZF, even though it is ruled out in ZFC.

-
Although the question only states as its hypothesis the implication that $A\in\mu\to f^{-1}A\in\mu$, in fact this implies the biconditional $A\in\mu\leftrightarrow f^{-1}A\in\mu$, since if $A\notin\mu$, then $X-A\in\mu$ and so $f^{-1}(X-A)\in\mu$, which is disjoint from $f^{-1}A$. –  Joel David Hamkins Mar 11 '13 at 0:38
Hi Joel, thanks for the cute proof and the extensive references! –  Santi Spadaro Mar 11 '13 at 23:31

Although the question has already been thoroughly answered, it might be worthwhile to point out that the result can be separated into the combinatorial "meat", which doesn't involve ultrafilters, and a small corollary where the meat is fed to the ultrafilter problem. The meat is the following theorem, which is, if I remember correctly, explicit in the early references; it is essentially proved (though not stated) in Joel Hamkins's answer here. Given any set $X$ and any function $f:X\to X$, there is a partition of $X$ into four disjoint (possibly empty) sets $X=A_0\sqcup A_1\sqcup A_2\sqcup A_3$ such that $A_0$ is the set of fixed points of $f$ and each of the other three $A_i$'s is disjoint from its image under $f$. Once one has this result, one immediately sees that any ultrafilter on $X$ must contain one of the four $A_i$'s and if that $A_i$ isn't $A_0$ then the ultrafilter can't be $f$-invariant as in the question.

-

Such a map does not exist since a continuous map on $X$ must be constant almost everywhere. In other words, if $f:X\rightarrow X$ is a map such that $f^{-1}[A]\in u$ for each $A\in u$, then $\{x\in X|f(x)=x\}\in u$. For a proof, see the book The Theory of Ultrafilters by Comfort and Negrepontis Thm 9.2 or Andreas Blass's dissertation p. 12.

-
Thank you, Joseph! –  Santi Spadaro Mar 10 '13 at 19:20

To give a partial answer to Joel's challenge on the situation where the axiom of choice fails, we can have a case with a fixed point-free map.

Suppose that $A$ is a $2$-amorphous set, that is an infinite set which cannot be written as the union of two disjoint infinite sets, but has a partition that almost all parts are pairs, and we can even assume that all parts are pairs.

Note that the cofinite filter on $A$ is a free ultrafilter. Now fix a partition of $A$ into pairs, say $P$, and define the function $f(x)=y\iff\lbrace x,y\rbrace\in P$. Since this is a bijection cofinite sets are mapped to cofinite sets, but no point is a fixed point, as that would imply a singleton is in $P$.

However this map has a period of two, so the main question is still open.

-
Great ! –  Joel David Hamkins Mar 11 '13 at 2:24
I'm not sure this is of interest to anybody, but if you're willing to work in a model of ZF+DC+BP then many examples are furnished by a little bit of ergodic theory. The point is that if $E$ is any generically ergodic meager equivalence relation on Polish $X$, the collection of subsets of $X/E$ which have comeager lift to $X$ forms a ($\sigma$-complete!) ultrafilter. This ultrafilter is of course preserved by maps on the quotient induced by homeomorphisms of $X$, since they leave category on $X$ unchanged. [cont.] –  Clinton Conley Mar 11 '13 at 18:35
So for example one recovers a version of Asaf's example by looking at the complementation map on $2^\omega / E_0$ (or equivalently $\mathcal{P}(\omega)/\mathrm{FIN}$). For an example with no finite orbits, one can look at for instance the free part $X$ of the shift action of the free abelian group $\mathbb{Z}^2$ on generators $a, b$ acting on $2^{\mathbb{Z}^2}$. The map $[x]_A \mapsto [b\cdot x]_A$ works on $X/A$, where $A$ is the orbit equivalence relation of $\langle a \rangle$. –  Clinton Conley Mar 11 '13 at 18:36
@Clinton, thank you for this example. I am trying to expand my "counterexample sources" to models of ZF+DC+BP, but amorphous (and $\kappa$-amorphous) sets are still my first go to solution. They are just so lovely because they terrifyingly violate so many choice principles at once... –  Asaf Karagila Mar 11 '13 at 19:26
Asaf, I confess that my primary motivation for looking at such examples comes not from the perspective of choiceless math but rather from the attempt to understand descriptive set-theoretic complexity among orbit equivalence relations. Nevertheless, they are occasionally useful as sanity checks for what is provable from ZFDC. In any case, I think your example is very nice and has a more classical set-theoretic flavor. –  Clinton Conley Mar 12 '13 at 17:05