# Homeomorphisms and “mod finite”

Suppose $$f:C\to C$$ is a homeomorphism, where $$C=\{0,1\}^{\mathbb N}$$ is Cantor space. Suppose $$f$$ preserves $$=^*$$ (equality on all but finitely many coordinates). Does it follow that $$f$$ also reflects $$=^*$$? That is, if $$x=^* y \implies f(x)=^* f(y)$$ does it follow that: $$x=^* y \iff f(x)=^* f(y)?$$

Using Axiom of Choice we can show that a bijection of $$C$$ that preserves $$=^*$$ need not reflect $$=^*$$, so the continuity assumptions are not superfluous.

• @samerivertwice for $f\in\{0,1\}^{\mathbf{N}}$ and $n\in\mathbf{N}$ the $n$-th coordinate of $f$ is $f(n)$. – YCor Jul 4 at 18:42

Define $$f : C \to C$$ by the formula $$f(x) = x_0 \cdot (x \oplus \sigma(x))$$ where $$\cdot$$ is word concatenation, $$\oplus : C \times C \to C$$ is coordinatewise xor, and $$\sigma(x)_i = x_{i+1}$$ is the shift. Clearly this map is continuous and preserves $$=^*$$. It is a bijection because you can deduce the preimage one coordinate at a time, which amounts to summing the prefix, $$f^{-1}(x)_i = \bigoplus_{j \leq i} x_i$$. By compactness $$f$$ is a homeomorphism. However, $$f(0^\omega) = 0^\omega$$ and $$f(1^\omega) = 10^\omega$$, so $$f$$ does not respect $$=^*$$.

The idea is that a surjective non-injective one-dimensional cellular automaton forgets a finite amount of ("global") information on every step. I picked the xor CA $$x \mapsto x \oplus \sigma(x)$$ and also wrote the single bit that's forgotten (in the form of the first coordinate) to make it a homeomorphism.

This is simple enough that you can randomly stumble upon the formula, but turning xor injective this way is actually a pretty important idea in cellular automata theory. To name just one example, Kari's proof of the undecidability of reversibility of cellular automata on free abelian groups of rank $$\geq 2$$ (i.e. whether the CA is a homeomorphism on the full shift) uses this trick to turn a cellular automaton injective if a Turing machine halts; you are applying xor on a one-dimensional snake and you cut off its head if the machine halts.

• As for the follow-up question from the comment on the other answer, the preservation of $E_0$ is uniform with $m_0 = n_0+1$. – Ville Salo Jul 4 at 20:09
• This is great. This $f$ makes $f^{-1}\circ \sigma\circ f$ not preserve $=^*$ too, so it subsumes all my follow up questions – Bjørn Kjos-Hanssen Jul 4 at 20:55

Even with a homeomorphism, preserving $$=^*$$ does not imply reflection. There might be an easy example, I'm not sure; at any rate it follows from a result in topological dynamics (the "absorption lemma" of Giordano–Putnam–Skau) that such examples exist.

Let me elaborate a bit: by results of Giordano–Putnam–Skau, there exists a minimal homeomorphism of $$X=\{0,1\}^{\mathbb N}$$ which induces the relation that you denote $$=^*$$ (and which is often denoted $$E_0$$); there is an explicit construction (via a Bratteli diagram) in a paper of Clemens. By this, I mean that being in the same $$\varphi$$-orbit is the same as being $$=^*$$-equivalent.

Denote such a homeomorphism by $$\varphi$$, fix some point $$x \in X$$, and let $$E$$ be the relation obtained from $$=^*$$ by splitting the class of $$x$$ in its positive semi-orbit under $$\varphi$$, and its negative semiorbit. (So, all classes are the same as $$=^*$$, except that the class of $$x$$ has been split in two pieces). Giordano–Putnam–Skau prove that there is a homeomorphism $$g$$ of $$X$$ such that for all $$x,y \in X$$ one has $$x=^*y \Leftrightarrow g(x) \mathrel E g(y).$$

Since $$E$$ is contained in $$=^*$$, yet not equal to it, such a $$g$$ preserves $$=^*$$ without reflecting it.

Edited to add: the book "Cantor minimal systems" by Ian Putnam is a good reference for information and bibliographical data about this area. Clemens's paper can be found here: Generating equivalence relations by homeomorphisms.

• Surprised to see Bratteli diagrams make an appearance here... amazing! – Bjørn Kjos-Hanssen Jul 4 at 19:02
• I'm not sure how needed they are to answer your question. They do play a key part in Giordano--Putnam--Skau's work, via a connection that Vershik made with topological dynamics. Equivalence relations induced by minimal homeomorphisms of the Cantor space are surprisingly complicated... – Julien Melleray Jul 4 at 19:06
• My follow-up question would be whether it helps if $E_0$ is preserved uniformly in the sense that whenever $x(n)$ and $y(n)$ agree above $n_0$ then there is an $m_0$ depending only on $n_0$ such that $f(x)(m)$ and $f(y)(m)$ agree above $m_0$... but that's for another day perhaps – Bjørn Kjos-Hanssen Jul 4 at 19:09
• Offhand, I do not know how to answer that one. The anwser might well be different! – Julien Melleray Jul 4 at 19:17
• @JulienMelleray: Pardon my orbit-equivalence ignorance, but what's the result you are referring to that implies there exists a homeomorphism $g$ such that $x =^* y \iff g(x) E g(y)$? – Ville Salo Jul 4 at 20:29