How to prove this function is bijective? [duplicate]

Funtion $$f:\mathbb{N}^2\rightarrow\mathbb{N},\quad(x,y)\mapsto\frac{(x+y)(x+y+1)}{2}+x$$

Note that given $$z=f(x,y)\in\mathbb{N}$$,$$\,\,$$you can find $$x$$ and $$y$$ by bounded minimization.

• What has this to do with logic? – José Carlos Santos Dec 7 '18 at 9:59
• This exercise is in the last chapter of a course in Mathematical Logic. The chapter is about computable and recursive funcions. – MGF01 Dec 7 '18 at 10:00
• $f: \mathbb{R}^2 \mapsto \mathbb{R}$, how come to be bijective? – Ng Chung Tak Dec 7 '18 at 10:03
• I am sorry, I forgot that the function is between $N^2$ and $N$ – MGF01 Dec 7 '18 at 10:05
• Write down the values $f(x,y)$ for $x,y\in\{0,1,\dots,9\}$ in a $10\times 10$ grid and see if you can guess what is going on. – Christoph Dec 7 '18 at 10:18

It is not bijective because

$$f(0,0)=f(0,-1)=0$$

The map is surjetive because

$$x=f(x,-x)$$

If the domain is $$\mathbb{N}^2$$ to $$\mathbb{N}$$ you can fix $$y$$ and for every $$x_1,x_2$$ such that $$f(x_1,y)=f(x_2,y)$$ you have that $$x_1=x_2$$ because if, for example, $$x_1< x_2$$ you have that

$$\frac{(x_2+y)^2}{2}-\frac{(x_1+y)^2}{2}+\frac{1}{2}[-(x_1+y)+(x_2+y)]=$$

$$=x_1-x_2<0$$

But

$$\frac{1}{2}(x_2-x_1)(x_2+x_1)+\frac{1}{2}(x_2-x_1)>0$$

And it is not possibile.

• Note that the domain and codomain have been edited to $\mathbb N^2\to\mathbb N$. – Christoph Dec 7 '18 at 10:23

We can factor $$f$$ as $$\mathbb N\times\mathbb N\overset{f_1}\longrightarrow Z\overset{f_2}\longrightarrow \mathbb N$$ where $$Z = \{(x,z)\in\mathbb N\times\mathbb N \,|\, z\ge x\}$$ and the maps are given by \begin{align*} f_1(x,y) &= (x,x+y), \\ f_2(x,z) &= \frac{z(z+1)}2 + x. \end{align*} We see that $$f_1$$ is a bijection with inverse $$(x,z)\mapsto(x,z-x)$$, so we only have to show that $$f_2$$ is a bijection. For this note that $$z(z+1)/2$$ is a triangle number, so that $$f(x,z) = \sum_{k=1}^z k + x.$$ Now given any $$n\in\mathbb N$$, there is a unique $$z\in\mathbb N$$ such that $$n$$ sits between the $$z$$-th and $$(z+1)$$-th triangle number: $$\sum_{k=1}^z k \le n < \sum_{k=1}^{z+1} k = \sum_{k=1}^z k + (z+1)$$ Letting $$x = n - \sum_{k=1}^z k$$ we obtain $$n = \sum_{k=1}^z k + x,$$ where $$x by the choice of $$z$$. So we have $$n=f_2(x,z)$$.