Does there exist a bijection $f: \mathbb N \rightarrow \mathbb N$ such that if $f(a) = b$ then either $b = a^2$ or $a = b^2$ Does there exist a bijection $f: \mathbb N \rightarrow \mathbb N$ such that if $f(a) = b$ then either $b = a^2$ or $a = b^2$?
Any help would be highly appreciated.
 A: The answer is yes.
Let $S = \mathbb{N} \setminus \mathbb{N}^2$ be the set of numbers which are not perfect squares. Notice that $a\in S^m$ means that $a = b^m$ for some (unique) $b \in \mathbb{N}$ which is not a perfect square. Clearly $\mathbb{N} = \bigcup_{k \ge 0} S^{2^k}$ and this union is disjoint.
Define $f : \mathbb{N} \to \mathbb{N}$ as
$$f(a) = \begin{cases} a^2 , &\text{ if $a \in S^{2^k}$ where $k$ is even } \\ \sqrt{a}, &\text{ if $a \in S^{2^k}$ where $k$ is odd } \\ \end{cases}$$
Then $f$ is bijective with inverse
$$f^{-1}(b) = \begin{cases} b^2 , &\text{ if $a \in S^{2^k}$ where $k$ is odd } \\ \sqrt{b}, &\text{ if $a \in S^{2^k}$ where $k$ is even } \\ \end{cases}$$

For some motivation, notice that if $a \in S$ then necessarily $f(a) = a^2$, and if $b \in S$ it must be $f(b^2) = b$. Therefore $f$ necessarily bijectively maps $S \mapsto S^2$ and $S^2 \mapsto S$. It remains to somehow bijectively map the union of $S^4, S^8, S^{16}, \ldots$ to itself. The most natural thing is $$S^4 \mapsto S^8, S^8\mapsto S^4$$
$$S^{16} \mapsto S^{32}, S^{32}\mapsto S^{16}$$
and so on.
