Find all functions $f: \mathbb{Z}_{\ge 0}\rightarrow \mathbb{Z}_{\ge 0}$ such that $f(f(m)+f(n))=m+n$

Question

Find all functions $f: \mathbb{Z}_{\ge 0}\rightarrow \mathbb{Z}_{\ge 0}$ such that $f(f(m)+f(n))=m+n.$

My idea was to set $m_0$ such that $f(m_0)=0$ and then:

$$ f(f(m_0)+f(n))=f(0+f(n))=f(f(n))=m_0+n$$

Then to set $m=n$:

$$ f(2f(n))=2n $$

But here I run out of ideas, as I don't know what to do to get $f(n)$ instead of $f(f(n))$ or $f(2f(n))$. Could somebody show me some hints?

Answer 1

The surjectivity is pretty much trivial. For the injectivity assume that $f(m) = f(n)$, then there exists (from surjectivity) $f(m_1) = m$, $f(n_1) = n$ and $f(k) = 0$. So we have:

$$m_1 + k = f(f(m_1) + f(k)) = f(m) = f(n) = f(f(n_1) + f(k)) = n_1 + k \implies m_1 = n_1 \implies m=n$$

Therefore the function is bijective. Now assume that $f(k) = 0$. Then:

$$f(f(k) + f(k)) = 2k = f(f(2k) + f(0))$$

From the bijectivity we have: $f(2k) + f(0) = f(k) + f(k) = 0$. But as $f(x) \ge 0 $ we get that $f(0) = 0$. Finally:

$$f(f(m) + f(n)) = m+n =f(f(m+n) + f(0)) \implies f(m+n) = f(m) + f(n)$$

The last equation can be easily solved using induction and later you can find a suitable value for $f(1)$.

Answer 2

If $f(m)=f(n)$ then $m=n$

There is a solution to $f(x)=n$, for every $n$

Write $m_2,m_3,m_4,...$ in terms of $m_0$ and $m_1$

Answer 3

As Max noted in his comment, surjectivity is straightforward to prove, so I'll leave that one for you. As for injectivity, if we have $f(m) = f(n)$, then $f(f(m) + f(n)) = f(f(n) + f(n))$, and so $m + n = 2n$, which says $m = n$. Therefore $f$ is a bijection.

Taking $f(m_0) = 0$, we obtain $f(f(n)) = m_0 + n$ and $f(0) = 2m_0$, so that $f(f(f(n)) + f(0)) = f(n) = f(3m_0 + n).$ Clearly bijectivity implies $m_0 = 0$, so $f(0) = 0$. Then $f(f(m+n) + f(0)) = f(f(m) + f(n)) = m+n$ (just as Stefan showed); thus, because $f$ is injective, $f(m) + f(n) = f(m + n)$. Thus $f(n) = nf(1)$, and so surjectivity requires $f(1) = 1$, and thus $f(n) = n$.