Given this function: $(x + y)^2 + y$, how do I go about proving it's injective property of mapping $\mathbb{N}×\mathbb{N} \to \mathbb{N}$ ? Surjection is not required. My current attempts include proving by negation: assume $(x_1,y_1) \ne (x_2,y_2)$ yet $(x_1 + y_1)^2 + y_1 = (x_2 + y_2)^2 + y_2$, then attempt to arrive at a contradiction. I wasn't able to find a technique that would help me reach that goal. Geometrically, I can think of the square value to be a growing line but must have a length of certain values (square values). The addition of $y$ must not overwhelm the line to the next "border" of square values. Thus no other value of $y$ would provide the same total length. While $x$ is bound to stretch the line between square values only. My math jargon isn't refined, but that it is how I think of this question.
How to prove injective property of $(x + y)^2 + y: \mathbb{N}×\mathbb{N} \to \mathbb{N}$
elementary-set-theoryfunctionsnatural numbers
Best Answer
Assume $m=(x+y)^2+y$ for some $x,y\in\Bbb N$. Can we uniquely determine $x,y$ from $m$?
Let $n\in\Bbb N$ be maximal with $n^2\le m$ (or: $n=\lfloor \sqrt m\rfloor$). Then $$ (x+y)^2\le m=n^2<(x+y)^2+y + (2x+y+1)=(x+y+1)^2$$ and we conclude $n=x+y$. It follows that $y=m-n^2$ and then $x=n-y$.