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.

  • $\begingroup$ What has this to do with logic? $\endgroup$ – José Carlos Santos Dec 7 '18 at 9:59
  • $\begingroup$ This exercise is in the last chapter of a course in Mathematical Logic. The chapter is about computable and recursive funcions. $\endgroup$ – MGF01 Dec 7 '18 at 10:00
  • $\begingroup$ $f: \mathbb{R}^2 \mapsto \mathbb{R}$, how come to be bijective? $\endgroup$ – Ng Chung Tak Dec 7 '18 at 10:03
  • $\begingroup$ I am sorry, I forgot that the function is between $N^2$ and $N$ $\endgroup$ – MGF01 Dec 7 '18 at 10:05
  • $\begingroup$ 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. $\endgroup$ – Christoph Dec 7 '18 at 10:18

It is not bijective because


The map is surjetive because


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





And it is not possibile.

| cite | improve this answer | |
  • $\begingroup$ Note that the domain and codomain have been edited to $\mathbb N^2\to\mathbb N$. $\endgroup$ – 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<z+1$ by the choice of $z$. So we have $n=f_2(x,z)$.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.