Homeomorphisms and "mod finite"

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.


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.