For $x \in \mathbb{N}$ and $1\le y \le x$, $g(x,y)=\frac{1}{2}x(x-1) + y$ is injective.

Question

For $x \in \mathbb{N}$ and $1\le y \le x$, define $g(x,y)=\frac{1}{2}x(x-1) + y$. Then $g$ is injective.

I'm trying to show this. So let $1 \le y' \le x'$ and $g(x,y)=g(x',y')$. I need to show that $x=x'$ in this case, then automatically $y=y'$.

What I have so far is $g(x,1) \le g(x,y) < g(x+1,1)\le g(x+1,y)$.

But I can't quite figure out how to show that $x=x'$. How can we show this?

Answer 1

What I have so far is $g(x,1) \le g(x,y) < g(x+1,1)\le g(x+1,y)$.

You are basically done and haven't noticed, because your argument can be extended by induction to

$g(x,1) \le g(x,y) < g(x+n,1)\le g(x+n,k)$ for $n,k\in\mathbb{N}$ and $k\leq x+n$

Now let $x,x',y,y'\in\mathbb{N}$ with $y\leq x$ and $y'\leq x'$. Assume $g(x,y)=g(x',y')$. We want to show $x=x'$ and $y=y'$.

Assume that this wouldn't be the case. Consider $x=x'$ and $y\neq y'$, that immediately leads to contradiction (because $g(x,y)\neq g(x',y')$ contradicting our initial assumption). Then because of symmetry of the following argument we only need to consider $x'<x$ and $y'\leq y$. But then we get $$g(x',y')<g(x,1)\leq g(x,y)$$ with the inductive version of your argument, leading to the contradiction $g(x',y')< g(x,y)$.