The n-Category Café

Theorem  Let $\mathcal{U}$ be an ultrafilter on a set $X$. Let $f: X \to X$ be a map such that for $A \subseteq X$,

$$A \in \mathcal{U} \iff f^{-1}A \in \mathcal{U}.$$

Then $\{x \in X \colon f(x) = x\} \in \mathcal{U}$.

I don’t know who first proved this theorem. Not me! For example, Andreas Blass referred to it in a 2012 stackexchange answer. I guess it’s decades old.

The theorem follows swiftly from another result, which I’ll call the “partition theorem”. It has nothing to do with ultrafilters: it’s purely a theorem about sets and functions.

Partition Theorem  Let $X$ be a set and $f: X \to X$ a map. Then there exist subsets $X_1, X_2, X_3 \subseteq X$ such that

$$X = X_1 \amalg X_2 \amalg X_3 \amalg Fix(f)$$

and $f X_i \cap X_i = \emptyset$ for all $i \in \{1, 2, 3\}$. Here $Fix(f) = \{x \in X : f(x) = x\}$.

Again, this result is sure to be old, but I don’t know who proved it first. More on the history later.

The partition theorem may look a bit peculiar (why 3?), but let’s just take it for granted for now and deduce the main theorem from it. We’ll come back to it.

Take a set $X$ with an ultrafilter $\mathcal{U}$, and a map $f: X \to X$ that’s measure-preserving in the sense above. Choose a partition of $X$ as in the partition theorem.

First notice that $X_i \cap f^{-1} X_i = \emptyset$ for each $i$. This follows from the fact that $f X_i \cap X_i = \emptyset$, by a one-sentence proof of the kind that’s easier to write out yourself than to read.

If $X_i \in \mathcal{U}$ for some $i \in \{1, 2, 3\}$ then also $f^{-1}X_i \in \mathcal{U}$ (by the measure-preserving hypothesis), so $X_i \cap f^{-1} X_i \in \mathcal{U}$ (since ultrafilters are closed under finite intersections), so $\emptyset \in \mathcal{U}$. This contradicts the definition of ultrafilter. Hence $X_i$ is not in $\mathcal{U}$ after all.

But $X = X_1 \cup X_2 \cup X_3 \cup Fix(f)$, so one of the subsets on the right-hand side must be in $\mathcal{U}$. It’s not $X_1$, $X_2$ or $X_3$, so it must be $Fix(f)$. This proves the main theorem: ergodic set theory is trivial.

Now let’s come back to the partition theorem. To understand why the statement is the way it is, a couple of observations are helpful:

• The number $3$ can’t be reduced any further. Consider a 3-element set $X$ and a 3-cycle $f$ on it. Then $Fix(f) = \emptyset$, and we can’t partition $X$ into two subsets $X_1$ and $X_2$ such that $f X_1 \cap X_1 = \emptyset$ and $f X_2 \cap X_2 = \emptyset$.

• We have to put the set of fixed points to one side, because if $x$ is a fixed point of $f$ then there can be no subset $A \subseteq X$ that contains $x$ and satisfies $f A \cap A = \emptyset$.

For a simple example of the partition theorem, take $X = \mathbb{Z}$ and $f(x) = x + 1$. Then we can take $X_1$ to be the odd integers, $X_2$ to be the even integers, and $X_3 = \emptyset$.

Here’s a sketch proof of the partition theorem.

Let $\sim$ be the equivalence relation on $X$ generated by $f(x) \sim x$ for all $x \in X$. Then $x \sim y$ if and only if $f^m(x) = f^n(y)$ for some $m, n \in \mathbb{N}$. The equivalence classes of $\sim$ are sometimes called the “grand orbits” of $f$.

We want to show that $X$ has a partition of a suitable kind. It’s enough to find a suitable partition of each of the grand orbits separately, because then we can just put them together to get a suitable partition of $X$. So, it suffices to prove the theorem when $X$ consists of a single grand orbit. Let’s assume that.

Now the argument splits into two cases — no one’s favourite style of proof, but I don’t know a better one.

• Suppose that $f$ has no periodic point. For each $x, y \in X$, we can choose natural numbers $m$ and $n$ such that $f^m(x) = f^n(y)$. There may be many choices of pairs $(m, n)$, but you can show that $n - m$ depends only on $x$ and $y$. Write $\delta(x, y) = n - m$. Fix $x$, then put $$X_i = \{ y \in X : \delta(x, y) \equiv i \mod{2} \}$$ ($i = 1, 2$) and $X_3 = \emptyset$.

• Suppose that $f$ has a periodic point. Fix one, $x$. You can check that every element of $X$ eventually arrives at $x$ after enough iterations of $f$. So given $y \in X$, we can define $n(y)$ to be the least natural number such that $f^{n(y)}(y) = x$. For $i = 1, 2$, put $$X_i = \{ y \in X \setminus\{x\}: n(y) \equiv i \mod{2} \}.$$ How do we define $X_3$? If $x$ is a fixed point, put $X_3 = \emptyset$, and if not, put $X_3 = \{x\}$. (OK, so the proof really splits into three cases.)

It’s not too hard to check that in all cases, this recipe works:

$$X = X_1 \amalg X_2 \amalg X_3 \amalg Fix(f)$$

and $f X_i \cap X_i = \emptyset$ for all $i$. This proves the theorem.

The case $Fix(f) = \emptyset$ of the partition theorem was proved in a 1967 paper of Miroslav Katětov:

Miroslav Katětov, A theorem on mappings. Commentationes Mathematicae Universitatis Carolinae 8 (1967), 431–433.

Katětov begins like this:

The theorem in question is of purely combinatorial character and a quite easy one. Probably, it has already appeared in the literature, at least implicitly. However, not having found an explicit reference, the present author preferred publishing a possibly well-known result to undertaking a long search.

Who knows whether others had published the result before him. The present author prefers writing a blog post on a possibly previously well-known result to undertaking a long search.

In any case, Katětov’s case $Fix(f) = \emptyset$ of the partition theorem can be used to prove a special case of the theorem on ultrafilters — namely, that where $f$ is injective. This is explained in another math.stackexchange answer, this one by user Gerd. The main point is that if $f$ is injective then $f$ restricts to an endomorphism of $X \setminus Fix(f)$, which is then fixed-point-free.

So there it is. If anyone has a reference for either the main theorem or the partition theorem, I’d be glad to know.