Let $f,g:\mathbb{Z}\to \{0,1\}$ be maps such that the preimages of both 0 and 1 under both $f$ and $g$ are infinite, i.e. $$ |f^{-1}(0)|=|f^{-1}(1)|=|g^{-1}(0)|=|g^{-1}(1)|=\infty. $$

In other words, if we think of $f$ and $g$ as infinite sequences of $0$'s and $1$'s, then both of these sequences contain infinitely many $0$'s and $1$'s.

Question: Does there exist a bijection $\phi:\mathbb{Z}\to \mathbb{Z}$ such that $f\circ \phi =g$?

For simple examples of $f$ and $g$ I can construct such a map $\phi$ explicitly. Does $\phi$ exist in general, and if so, how can this be shown? Does the existence of $\phi$ follow from the axiom of choice?


Yes, for given two functions $\varphi_0:g^{-1}\{0\}\to f^{-1}\{0\}$ and $\varphi_1:g^{-1}\{1\}\to f^{-1}\{1\}$. Since $\Bbb Z=g^{-1}\{0\}\cup g^{-1}\{1\}$ as disjoint union, there exists one and only one function $\varphi:\Bbb Z\to\Bbb Z$ extending both $\varphi_0$ and $\varphi_1$ and we have $f\circ\varphi=g$.

The condition \begin{align} &g^{-1}\{0\}\neq\varnothing\implies f^{-1}\{0\}\neq\varnothing& &g^{-1}\{1\}\neq\varnothing\implies f^{-1}\{1\}\neq\varnothing \end{align} is necessary and sufficient for the existence of such map $\varphi$.

Finally, the axiom of choice is not required, for if we pick $a\in f^{-1}\{0\}$ and $b\in f^{-1}\{1\}$, then we can take $$\varphi(x)= \begin{cases} a&g(x)=0\\ b&g(x)=1 \end{cases}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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