11
$\begingroup$

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.

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

2 Answers 2

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Ville Salo
    Jul 4, 2020 at 20:09
  • $\begingroup$ This is great. This $f$ makes $f^{-1}\circ \sigma\circ f$ not preserve $=^*$ too, so it subsumes all my follow up questions $\endgroup$
    – Bjørn Kjos-Hanssen
    Jul 4, 2020 at 20:55
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Surprised to see Bratteli diagrams make an appearance here... amazing! $\endgroup$
    – Bjørn Kjos-Hanssen
    Jul 4, 2020 at 19:02
  • 1
    $\begingroup$ 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... $\endgroup$
    – Julien Melleray
    Jul 4, 2020 at 19:06
  • 1
    $\begingroup$ 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 $\endgroup$
    – Bjørn Kjos-Hanssen
    Jul 4, 2020 at 19:09
  • $\begingroup$ Offhand, I do not know how to answer that one. The anwser might well be different! $\endgroup$
    – Julien Melleray
    Jul 4, 2020 at 19:17
  • $\begingroup$ @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)$? $\endgroup$
    – Ville Salo
    Jul 4, 2020 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.