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!

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

  • $\begingroup$ 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^? $\endgroup$ – Pascalony Mar 4 at 20:10
  • $\begingroup$ 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. $\endgroup$ – R_B Mar 4 at 20:22

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.