# 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.

• What is $N$? Natural numbers? – Wuestenfux Jul 12 at 12:46
• @Wuestenfux Yup – Ilan Aizelman WS Jul 12 at 12:47
• Likely yes by induction – Quang Hoang Jul 12 at 12:48
• No. Hint: Consider $35$. – Kumar Jul 12 at 12:59

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.