# Proving a multi variable function bijective

I understand the theory of how to prove a mutli variable function bijective, however I somehow can neither prove this function injective or surjective:

$$f: \mathbb N\times \mathbb N \rightarrow \mathbb N, (a, b) \mapsto {(a+b)}^{2} + a$$

I tried to start with $$f(a, b) = f(a', b')$$ but I don't really know how to continue from there. To prove it surjective I started with: show that for every $$n$$ there is $$(a, b)$$ with $$f(a, b) = m$$ but was not successful there either. To make matters worse I don't even know yet if this function is injective, surjective, neither or both. Any help would be appreciated!

• In the context of this problem, does $\mathbb{N}$ include $0$? Also, for what values $(x,y)$ does $f(x,y) = 8$? – Brian Mar 4 at 16:44
• As Brian already pointed out, checking surjectivity is very simple.. just check for small numbers, say try finding $(a,b)$ which map to $3$ – Sebastian Schulz Mar 4 at 16:55
• @BrianS it does not include 0, checking small values is something I should have considered of course – Pascalony Mar 4 at 20:08

It is helpful to arrange the values of $$f(a,b)$$ in a table, thus:

$$\begin{matrix} \vdots & \vdots & \vdots & \vdots \\ 9 & 17 & 27 & 39 & \cdots \\ 4 & 10 & 18 & 28 & \cdots \\ 1 & 5 & 11 & 19 &\cdots \\ 0 & 2 & 6 & 12 & \cdots \end{matrix}$$

Here we visualize the set of all $$a,b \in \mathbf{Z}_{\geq 0}$$ as the upper-right quadrant.

You can see that the entries along the $$b$$-axis are the squares $$0,1,4,9$$ and that as you move down and to the right the entries go up by exactly $$1$$. This shows that the function is injective but not surjective, and that the numbers it misses are precisely those between $$a^2+a$$ and $$a^2+2a+1=(a+1)^2$$ for each non-negative $$a$$ (once you prove that these patterns always hold; details below). Incidentally, it also shows that you could, by modifying the domain slightly, obtain a bijection from a subset of $$\mathbf{Z}^2$$ to $$\mathbf{Z}_{\geq 0}$$.

Details of the proof: observe that $$f(a+1,b-1)=(a+1+b-1)^2+a+1=(a+b)^2+a+1=f(a,b)+1$$ and that $$f(a,0)=a^2+a for all $$a \geq 0$$.

The map is certainly not surjective, as it has been pointed out in the comments.

Let us try to prove injectivity. I will rewrite the function $$(a+b)^2+a$$ as $$c^2+a$$ where $$c=a+b$$, and in particular note $$c\geq a$$ because $$b\in\mathbb{N}$$. Argue by contradiction, suppose there exist $$a, c, \hat{a}, \hat{c}$$ with $$c\neq \hat{c}$$ and $$a\neq \hat{a}$$ such that $$c^2+a=\hat{c}^2+\hat{a},$$ noting the case $$c=0$$ and the case $$\hat{c}=0$$ are excluded because they would imply $$a=b=\hat{a}=\hat{b}=0$$.

Without loss of generality, let $$c>\hat{c}$$. Write $$c^2=\hat{c}^2+\hat{a}-a,$$ and we try to prove the LHS is strictly larger than the RHS, deriving a contradiction. We prove it for the "best" case, $$a=0$$, which then proves it for $$a>0$$ as well. Thus we write $$c^2=\hat{c}^2+\hat{a},$$ and since $$\hat{a}\leq \hat{c}$$ the RHS is bounded above by $$\hat{c}^2+\hat{c}$$. We had $$c>\hat{c}$$; taking the best case scenario again we try $$c=\hat{c}+1$$, which yields $$c^2=\hat{c}^2+2\hat{c}+1$$, strictly larger than the upper bound on the RHS, which yields the contradiction.

• This makes sense to me but I don't understand why this is without a loss of generality. How can you just assume c > c^? – Pascalony Mar 4 at 20:10
• We can say for sure that $c\neq\hat{c}$, otherwise we get $a=\hat{a}$ too and we are not really looking at different points. One of $c$ and $\hat{c}$ must be larger than the other. If $c>\hat{c}$, we are fine. If $c<\hat{c}$, we just relabel the variables (swapping the hats), and end up with $c>\hat{c}$ again. – R_B Mar 4 at 20:22