Coding $\omega$-sequences of 0,1 with $\mathbb{Z}$-sequences of 0,1

Question

This is a question from the talk here on page 115. Define an equivalence relation $\sim$ on ${}^\mathbb{Z}2$ by $f\sim g$ iff $f$ is a constant shift of $g$ (i.e. we are forgetting the origin). What is an example of an injection from ${}^\omega 2$ to ${}^\mathbb{Z}2/\sim$, the equivalence classes of ${}^\mathbb{Z}2$ under $\sim$? Do we need the axiom of choice for this?

Answer 1

Choice is not needed here.

One easy approach is the following: given a $\mathbb{N}$-indexed sequence $\alpha=(a_i)_{i\in\mathbb{N}}$, let $\hat{\alpha}=(\hat{a}_i)_{i\in\mathbb{Z}}$ be defined by $$\hat{a}_i=\begin{cases} 0 & \mbox{ if } i<-1\\ 1 & \mbox{ if } i=-1\\ a_i & \mbox{ if } i\ge 0. \end{cases}$$

The point is that the "$...0001$"-part tells us exactly where the origin is, and so if $\alpha\not=\beta$ we get $\hat{\alpha}\not\sim\hat{\beta}$. (Note that the $i=-1$ clause is important: if we set $\hat{a}_i=0$ for all $i<0$, we would lose injectivity since e.g. any two elements of $^\mathbb{N}2$ with exactly one $1$ would be sent to $\sim$-equivalent sequences.)

Choice is however needed for an injection $^\mathbb{Z}2/{\sim}\rightarrow{}^\mathbb{N}2$.