Prove a property of a bijective function $f$ Function $f: \mathbb{N} \times \mathbb{N} \to  \mathbb{N} \times \mathbb{N}$ is a bijection. ($0 \in \mathbb{N}$.) It has the following property:
$f(x+y) = f(x) + f(y)$, where $(a,b)+(c,d) = (a+c, b+d)$
How do I prove (if possible) that this must hold:
$f((a,b)) = (c,d) \implies a+b=c+d$
This is an intuition I have (otherwise there would be "holes" in $\mathbb{N} \times \mathbb{N}$, but that can't be since $f$ is a bijection), but I can't think of a formal proof.
Actually when I try to "materialize" my intuition: I have the feeling that in this case $f(f(x)) = x$ must hold. But I have no idea how to prove it.
 A: Some hints:
What can you say about $f((0,0))$?
Note that for any $(a,b) \in \mathbb{N}^2$ (except for $(0,0)$ which is covered above) we have $(a,b) = (1,0) + \cdots + (1,0) + (0,1) + \cdots + (0,1)$ with $a$ copies of $(1,0)$ and $b$ copies of $(0,1)$.  Therefore, $f$ is uniquely determined by $f((0,1))$ and $f((1,0))$.
Call $(a,b) \in \mathbb{N}^2$ "irreducible" if whenever $(x,y) + (x',y') = (a,b)$ then either $(x,y)=(0,0)$ or $(x',y')=(0,0)$.  What are the irreducible elements of $\mathbb{N}^2$?  Show that if $(a,b)$ is irreducible, then $f((a,b))$ must also be irreducible.
A: Suppose that $f$ verifies your claim. By linearity, 
$$
f(n,m) = f((n,0) + (0,m)) = f(n,0)  + f(0,m).
$$
Inductively you can prove that $f(n,0) = f((1,0) + (n-1,0)) = f(1,0) + f(n-1,0)$, and so
$$
f(n,m) = nf(1,0) + mf(0,1). \tag{1}
$$
for each $n,m$ with at least one nonzero. So $f$ is determined by its values on $(1,0)$, $(0,1)$ and $(0,0)$. Note that if $f(n,m) = 0$, then $f(2n,2m) = f(n,m) + f(n,m) = 0$ by injectivity thus $n = 2n, m = 2m$ and so $n = m = 0$. So far, we have seen that $f$ fixes zero. Now, if $f(a,b) = (c,d)$, then
$$
af(1,0) + bf(0,1) = (c,d)
$$
so
$$
af(1,0)_1 + bf(1,0)_1 = c, \\
af(1,0)_2 + bf(1,0)_2 = d.
$$
and by hypothesis this implies $a+b = c+d$,
$$
a(f(1,0)_1+f(1,0)_2) + b(f(0,1)_1+f(0,1)_2) = c+d = a+b.
$$
We are assuming this holds for any $a,b$, so in particular if $a = 0,b=1$, then
$$
f(0,1)_1+f(0,1)_2 = 1
$$
and taking $a = 1, b= 0$, we get $f(1,0)_1+f(1,0)_2 = 1$. Since these are natural numbers (including zero), necessarily one summand of each sum is $1$ and the other one zero. By injectivity, we can't have $f(0,1) = f(1,0)$, so the only possible choices are 
$$
\begin{align}
&f(0,1) = (0,1), f(1,0) = (1,0) \quad \text{ or } \\
&f(0,1) = (1,0), f(1,0) = (0,1).
\end{align}
$$
That is, $f$ is either the identity $\operatorname{id}_{\mathbb{N} \times \mathbb{N}}$ or $f(x,y) = (y,x)$. These functions in fact verify the claim, so they are all the possible options (note that for this conclusion we didn't need surjectivity at all). 
Hence the question reduces to proving whether there are "linear bijections" that are not the identity or the permutation of coordinates (which I will denote $\sigma$). Equation $(1)$ holds by linearity and so we can restrict to classifying the functions via the images of $f(0,1)$ and $f(1,0)$. By surjectivity there exist $a,b$ such that 
$$
af(1,0) + bf(0,1) = f(a,b) = (1,0).
$$
Thus,
$$
af(1,0)_1 + bf(0,1)_1 = 1,\\
af(1,0)_2 + bf(0,1)_2 = 0.
$$
By injectivity it can't be that $f(1,0)_2 = f(0,1)_2 = 0$. Thus one is nonzero and  consequently either $a$ or $b$ must be zero. From the first equation, then, the other coefficient has to be one. So either $f(1,0) = (1,0)$ or $f(0,1) = (1,0)$. By a similar calculation for $(0,1)$ we see that in effect, any "linear bijection" is either $\sigma$ or the identity, and these verify $f(a,b) = (c,d) \Rightarrow a+b = c+d$.
Moreover, since this characterizes such functions, we can see that as you have predicted, $f^2 = id$.
