Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Beat me to the edit, too, @Asaf! + –  amWhy Feb 11 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 at 22:44
    
@Asaf I'll be sure to add it to my wish list! ;-) –  amWhy Feb 11 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 at 4:21

1 Answer 1

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|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 at 22:43
    
And to think that I took my time with this one... ;-) –  Asaf Karagila Feb 11 at 22:43
    
I don't believe that using induction here shows that $g$ is injective. –  Pubbie Feb 12 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 at 15:10

Your Answer

 
discard

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.