Prove/disprove that there are functions $f$ and $g$ that keep the condition, so that if $f$ is surjective and $g$ is injective.

Question

I'm translating from a different language so excuse me if it's not as formal as should be in English.

I need help to prove/disprove: Let $f,g: \mathbb{N} \to \mathbb{N}$ so that $f(n) = g\left(n^2\right)$.

Prove/disprove that there are functions $f$ and $g$ that keep the condition, so that $f$ is a surjective function and $g$ is an injective function.

Answer 1

I understand the question as: "can we find two maps $f, g : \mathbb N \to \mathbb N$ such that $f$ is surjective, $g$ is injective, and $f = g \circ q$, where $q : \mathbb N \to \mathbb N$ is the squaring map.

It's not possible. Indeed, if $f$ and $g$ were two such maps:

• Every $y \in \mathbb N$ could be written as $y = f(x) = g(x^2)$ for some $x \in \mathbb N$, so it would be in the range of $g$: this proves that $g$ is surjective.

• Since $g$ was injective all along, it would be a bijection. In particular, there is an inverse map $g^{-1}$, also a bijection.

• Now, the relation could be written as $q = g^{-1} \circ f$. But a composition of surjections is a surjection, and $q$ isn't, so we have our contradiction.