# Is there a prefix-continuous bijection between finite words and eventually zero words?

Let $$X = \{x \in \{0,1\}^{\omega} \;|\; \exists m: \forall i \geq m: x_i = 0\}$$ (one-way infinite eventually zero words). Let $$\{0,1\}^*$$ denote the finite (not necessarily nonempty) words over $$\{0,1\}$$, and write $$\{0,1\}^{\leq k} = \{w \in \{0,1\}^* \;|\; |w| \leq k\}$$ where $$|w|$$ denotes length.

Is there a bijection $$\phi : X \to \{0,1\}^*$$ such that $$\exists n \in \mathbb{N}: \forall a \in \{0,1\}: \forall x \in \{0,1\}^{\mathbb{N}}: \exists b, c \in \{0,1\}^{\leq n}: \exists y \in \{0,1\}^*: \phi(x) = b \cdot y \wedge \phi(a \cdot x) = c \cdot y$$ holds, where $$\cdot$$ is concatenation?

This is a kind of coarse uniformity / bornologousness assumption: $$\phi$$ needs to be bornologous between the two sets, seen as metric spaces with the path metric of the graph structure where $$x$$ and $$y$$ are adjacent if $$y = ax$$ or $$x = ay$$ for some $$a \in \{0,1\}$$. This seems vaguely familiar to me but I don't know from where, and I'm not seeing how to construct $$\phi$$. The straightforward idea of cutting out the zero tail doesn't work because it's not surjective, and I run into trouble trying to fix that. But I also didn't manage to prove impossibility because there's a lot of freedom.

The question arises in some (leisurely) research, so asking here instead of math.SE even if it might be safer to start there with this one. Geometric group theory tag because this is related to Thompson's $$V$$, even if I didn't elaborate and I doubt it's useful (every countable group acts freely on $$\{0,1\}^*$$).

• The condition can be stated as $\phi$ being bornologous between the two sets, seen as metric spaces with the path metric of the graph structure where $x$ and $y$ are adjacent if $y = ax$ or $x = ay$ for some $a \in \{0,1\}$. May 28 '20 at 9:32
• The condition "$\exists n$, $\forall x$ $\exists c,d,e$, $\exists y$, $\phi(x)=cy$, $\phi(0x)=dy$, $\phi(1x)=ey$" is a priori a bit stronger (as in your condition you require one $y$ for each pair in the triple $\{\emptyset,0,1\}$), but is there really a reason you don't ask in this simpler way?
– YCor
May 28 '20 at 9:33
• To clarify, do we agree they are equivalent? If not, I wonder if I've made a mistake and will have to take another look at what I've written. May 28 '20 at 9:36
• I wrote it the way that looked most symmetric to me, the point is a small prefix change should become a small prefix change in the image, for some modulus of bornologuity. May 28 '20 at 9:39
• It might be equivalent... it's just that quantifying over pairs of a 3-element set is puzzling unless there's a serious reason to do so. It looks like there's one $y=y_{\emptyset,0}$ working for $\emptyset,0$, one $y_{\emptyset,1}$, and one $y_{0,1}$.
– YCor
May 28 '20 at 9:44

I believe the following works, but I might be missing something.

If $$x$$ has at least two 1s, then $$\phi(x)$$ is the sequence cut just before the last 1: $$\phi(0011101000\cdots) = 001110$$

If $$x$$ has at most one 1, then $$\phi(x)$$ is the sequence cut before the one, with an additional zero: $$\phi(000\cdots) = \varnothing,\qquad \phi(001000\cdots) = 000$$

The inverse bijection is $$\psi(\varnothing)=000\cdots$$, $$\psi(y)=y\cdot1000\cdots$$ when $$y$$ has at least one 1, and $$\psi(y\cdot0)=y\cdot 1$$ for $$y$$ consisting only of zeros (possibly $$y=\varnothing$$).

Then $$\phi(a\cdot x)=a\cdot\phi(x)$$ if $$x$$ has at least two 1s, and the case of $$000\cdots$$ is unimportant, up to taking a large $$n$$ (although $$n=1$$ works so far). Now if $$x$$ consists only of zeros, $$\phi(0\cdot y\cdot 1000\cdots)=0 \cdot y\cdot 0=00\cdot y\qquad\text{ and }\qquad\phi(1\cdot y\cdot 1000\cdots)=1\cdot y$$ while $$\phi(y\cdot1000\cdots)=y\cdot0=0\cdot y$$.

So the hypotheses are satisfied with $$n=1$$.

• Seems to work, nice! However, full disclosure, this is a sort of toy model of the actual problem I'm interested in, though I only realize that now that I see your solution. I'll perhaps make another question later with stricter requirements. (I can also think of a possibly more natural and general version of the present question, I'll see if it makes a good MO question too.) May 28 '20 at 19:21