Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Any helpful hints are welcome!

share|cite|improve this question
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$.

share|cite|improve this answer
Okay, I won't post! (Again, you beat me to it!) I should have known, given the (slightly incorrect) tag. – amWhy Feb 11 '14 at 22:43
And to think that I took my time with this one... ;-) – Asaf Karagila Feb 11 '14 at 22:43
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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