# Proving a function is bijective.

I'm not asking that this particular proof be done for me, I merely am asking for some sort of hint.

Here is the question.

Show that $f:Z_+\times Z_+\rightarrow A$ is a bijection, where $A$ is the subset of $Z_+\times Z_+$ consisting of the pairs $(x,y$ for which $y\le x$, by the equation $f(x,y)=(x+y-1,y).$ Next prove that $f:A\rightarrow Z_+$ by the formula $g(x,y)=\frac{1}{2}(x-1)x+y$ is a bijection.

I have proved that $f$ is in fact a bijection, but I am struggling to show that $g$ is. Now, the way I typically show a function is a bijection is by setting $g(a,b)=g(x,y)$ which usually results in $(a,b)=(x,y)$, but I cannot do that here since $g$ does not return an ordered-pair.

-
Beat me to the edit, too, @Asaf! + – amWhy Feb 11 '14 at 22:43
@amWhy: You should buy a buckling spring keyboard, then you can type lots of words per minute and do things quickly enough! ;-) – Asaf Karagila Feb 11 '14 at 22:44
@Asaf I'll be sure to add it to my wish list! ;-) – amWhy Feb 11 '14 at 22:47
I still can not figure out the second part of this problem involving the function $g$. Could any one help? Thanks! – Pubbie Feb 12 '14 at 4:21

HINT: Try proving by induction on $n$ that if $g(x,y)=n=g(a,b)$ then $(x,y)=(a,b)$. Remember that you will have to use the fact that $x\geq y$ and $a\geq b$ at some point.
Another useful observation is that $\frac12(x-1)x=0+\ldots+x-1$.
I don't believe that using induction here shows that $g$ is injective. – Pubbie Feb 12 '14 at 12:49
@David: Suppose that for $n$ there is (at most) one pair $(x,y)$ such that $g(x,y)=n$. Now, if $x=1$ then $g(x,y)+1=g(x+1,y)=g(x,y+1)$ but because of the condition on $y\leq x$ we have to have that $y=1$ as well, so $y+1>x$ and therefore this is impossible. If $x>1$ then we have to have $g(x,y)+1=g(x,y+1)$, because $g(x+1,y)=g(x,y)+x$. – Asaf Karagila Feb 12 '14 at 15:10