## February 12, 2022

### 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.

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.

Posted at February 12, 2022 2:30 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3382

### 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 most 1. 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 connected graphs 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 be infinite trees. 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”.)

Posted by: lambda on February 12, 2022 8:32 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

Thank you, lambda. It sounds as if we have the same pictures in our head. While I was figuring out the proof of this, I was drawing lots of diagrams of the type you’re describing, with cycles and trees growing out of them. But the way you recount the proof in the second paragraph of your comment is compelling (and I hadn’t thought of it quite like that). It’s a really nice way to look at it.

Posted by: Tom Leinster on February 12, 2022 11:10 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

Let’s use two functions, and replace $f^{-1}$ with $f^{-1} \cup g^{-1}$, and adjust definitions accordingly. Then the main theorem still holds, via a partition theorem that uses more colours.

Posted by: unekdoud on February 17, 2022 2:14 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

Can you be more specific? What is the statement of the version of the main theorem you have in mind, and what is the statement of this variant partition theorem?

Posted by: Tom Leinster on February 17, 2022 3:35 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

I was thinking something along these lines:

Consider functions $T:X\to P(X)$. The set of such functions inherits a Boolean algebra structure from $P(X)$. Define $W(T)=\{x\in X:x\in T(x)\}$. Then: $W(T_1 \cup T_2)=W(T_1) \cup W(T_2)$ $W(T_1 \cap T_2)=W(T_1) \cap W(T_2)$ $W(f^{-1})=Fix(f)$

Call a function $c:X\to I$ a colouring of $T$, and say $T$ is $|I|$-colourable, if for all $x\in T$, $c(T(x))\cap c(\{x\}\setminus W(T))=\emptyset$.

Then the partition theorem just says $f^{-1}$ is 3-colourable.

Lemma. Let $c_1$ be a colouring of $T_1$ and $c_2$ be a colouring of $T_2$. Then the Cartesian product $c=(c_1,c_2)$ is a colouring of both $T_1 \cup T_2$ and $T_1 \cap T_2$.

Proof. For $T_1 \cup T_2$, we only need to consider $x$ which are not in either $W(T_i)$. By assumption, $c(\{x\})$ is disjoint from $c(T_1(x))$ (because their first coordinates do not overlap), and $c(T_2(x))$, hence it is also disjoint from their union, which equals $c(T_1(x) \cup T_2(x))$.

For $T_1 \cap T_2$, we only need to consider $x$ which are not in both $W(T_i)$. By assumption, $c(\{x\})$ is disjoint from either $c(T_1(x))$ or $c(T_2(x))$, hence it is disjoint from their intersection, which contains $c(T_1(x) \cap T_2(x))$.

Corollary. $f^{-1}\cup g^{-1}$ is 9-colourable.

Theorem. Let $\mathcal{U}$ be an ultrafilter on a set $X$. Let $f,g:X \to X$ be maps such that for $A \subset X$, $A \in \mathcal{U} \Leftrightarrow (f^{-1}A \cup g^{-1}A)\in \mathcal{U} .$ Then $Fix(f) \cup Fix(g)=\{x\in X:x \in f^{-1}(x) \cup g^{-1}(x)\}\in \mathcal{U}$.

Proof. As above, let $T=f^{-1}\cup g^{-1}$. Use the corollary to partition $X$ into $X_1$ to $X_9$ and $W(T)$, such that $T(X_i)\cap X_i=\emptyset$. By assumption, none of the $X_i$ can be in $\mathcal{U}$, so $W(T)$ must be.

Posted by: unekdoud on February 20, 2022 1:32 AM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

To fix and simplify that middle definition:

Call a function $c:X\to I$ a colouring of $T$ (and say $T$ is $|I|$-colourable) if for all $x\in X\setminus W(T)$, $c(x) \notin c(T(x))$.

Posted by: unekdoud on February 20, 2022 1:40 AM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

We can get away with not proving the partition theorem, as follows.

Every set admits a total order relation $\lt$. So choose a total order on $X$.

We will call $x \in X$ a forward point if $x \lt f(x)$, and a backward point if $f(x) \lt x$.

Lemma. We can color the set $F = \{x \in F \:|\: x \lt f(x)\}$ of forward points with two colors (say red and green) so that if $x \in F$ and $f(x) \in F$, then $x$ and $f(x)$ get different colors. Proof. Form a graph whose vertices consist of the forward points. Connect two vertices $x,y$ with a directed edge if and only if $y = f(x)$. This graph is directed and acyclic (since $y \gt x$ whenever $x$ and $y$ have an edge between them), and therefore admits a two-coloring. This two-coloring has the desired property. Qed.

We can color the set of backward points similarly (say yellow and blue).

This allows us to write the set $X$ as a disjoint union of the following five sets:

1. Red forward points $F_r$,
2. Green forward points $F_g$,
3. Blue backward points $B_b$,
4. Yellow backward points $B_y$,
5. Fixed points of $f$.

Let us show that $F_r$ does not belong to the ultrafilter. If we had $F_r \in \mathcal{U}$, then by the defining property of the endomorphism $f$ we’d have $f^{-1}(F_r) \in \mathcal{U}$ as well. But by the defining property of the coloring on $F$, the elements of $f^{-1}(F_r)$ cannot be red forward points. So $f^{-1}(F_r) \cap F_r = \emptyset \in \mathcal{U}$, a contradiction.

An identical argument shows that $F_g$, $B_b$, $B_y$ cannot belong to the ultrafilter $\mathcal{U}$ either. Consequently, $\mathcal{U}$ must contain the fixed points of $f$ as desired.

Posted by: Z. A. K. on February 17, 2022 5:14 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

Every set admits a total order relation $\lt$.

It’s a linear order relation, rather than a total order relation $\leq$. And I’m not sure if either of “Every set admits a linear order relation” or “Every set admits a total order relation” is true constructively.

### Re: Ergodic Set Theory is Trivial

No one’s claiming anything’s true constructively, are they?

And I always understood “linear order” and “total order” to be interchangeable.

Let’s try to keep comments positive and helpful. If someone makes a mistake, by all means correct it. But quibbling over widely understood terminology, or taking someone to task for their arguments not being constructive when they haven’t claimed they were constructive, isn’t great for the atmosphere.

Posted by: Tom Leinster on February 28, 2022 7:13 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

It’s a linear order relation

No, I meant what I wrote. Every set admits a total order relation $\lt$ obeying the expected three axioms: irreflexivity, transitivity, connectedness. Some call this a “strict” total order, although the terminology is not in any way consistent.

This statement doesn’t (and cannot) have a constructive proof: it is independent even of ZF itself, so much stronger than anything provable in constructive set theories CZF/IZF.

But it does follow from an easy compactness argument, so is at most as strong as the Ultrafilter Lemma. I think the Ultrafilter Lemma is a fairly benign assumption to make when one proves theorems about non-principal ultrafilters (themselves non-constructive objects).

Alas, you will not find a constructive proof of any of the theorems mentioned above, in my post or in the article: even the partition theorem is non-constructive.

Posted by: Z. A. K. on March 2, 2022 3:52 PM | Permalink | Reply to this

### Re: Ergodic Set Theory is Trivial

Sorry, I have no idea what went wrong with the threading. This should belong under Madeleine Birchfield’s comment above.

Posted by: Z. A. K. on March 2, 2022 5:44 PM | Permalink | Reply to this

Post a New Comment