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.

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

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.

  • $\begingroup$ Thank you, this is perfect $\endgroup$ – Ilan Aizelman WS Jul 12 at 13:58

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.