### Ergodic Set Theory is Trivial

#### Posted by Tom Leinster

On the one hand, an ultrafilter on a set can be seen as a primitive sort of probability measure, in which every subset is assigned a probability of either 0 or 1 and the measure only has to be *finitely* additive.

On the other, ergodic theory studies measure-preserving endomorphisms of probability spaces.

What happens if you put the two together? That is, given an ultrafilter $\mathcal{U}$ on a set $X$, what can be said about the measure-preserving endomorphisms of $(X, \mathcal{U})$?

The answer is: very little. The situation is trivial. Essentially the only measure-preserving endomorphism of $(X, \mathcal{U})$ is the identity. A bit more exactly, such an endomorphism must be the identity almost everywhere.

Here’s why.

TheoremLet $\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 TheoremLet $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 Carolinae8 (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.

## Re: Ergodic Set Theory is Trivial

An alternative perspective on the partition theorem: given $f\colon X \to X$, let $\Gamma$ be the directed graph with vertex set $X$ and edges from $x$ to $f(x)$ for each $x$. This is a “functional digraph”, where each vertex has outdegree exactly 1. Let $\Gamma'$ be obtained from $\Gamma$ by deleting the fixed points. Then $\Gamma'$ is a digraph with no loops such that each vertex has outdegree

at most1. The partition theorem amounts to the statement that (the underlying graph of) such a digraph is 3-colourable.It is sufficient to prove this for

connectedgraphs of this type. Such a thing is either a tree or contains a single cycle (of length at least 2) with trees growing from it. This is basically the same decomposition as in Joyal’s proof of Cayley’s theorem, except now they can beinfinitetrees. Nonetheless, even infinite trees are 2-colourable, and cycles of length at least 2 are 3-colourable, and a graph obtained by joining two 3-colourable graphs at a vertex is still 3-colourable, so the result follows.(I think morally this is the same as the proof in the post, but I like thinking about it this way. In particular, the number 3 feels less mysterious if I read it as “the chromatic number of an odd cycle”.)