Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
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
add comment

4 Answers

up vote 9 down vote accepted

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Thank you, Joseph! –  Santi Spadaro Mar 10 '13 at 19:20
add comment

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.

share|improve this answer
    
Great ! –  Joel David Hamkins Mar 11 '13 at 2:24
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.