1. ## [SOLVED] Relations

Define f: ℕ×ℕ→ℕ as follows: For each (m,n) ∈ ℕ×ℕ, $f(m,n) =2^{m-1}*(2n-1)$
Prove that f is an injection.
I don't know how to go about doing this one.

2. Originally Posted by dwsmith
Define f: ℕ×ℕ→ℕ as follows: For each (m,n) ∈ ℕ×ℕ, $f(m,n) =2^{m-1}*(2n-1)$
Prove that f is an injection.
I don't know how to go about doing this one.
Suppose that $f(m,n)=f(m',n')$, then we'd have that $2^{m-1}(2n-1)=2^{m'-1}(2n'-1)$.

So let me ask you this, we can assume WLOG that $m\leqslant m'$, right? So this means that $m'-1-(m-1)=m'-m\geqslant 0$ and so dividing through we get $2^{m'-m}(2n-1)=2n'-1$. Now, if $m'-m>0$ what would the problem be with that?
Spoiler:
think parity

3. Originally Posted by Drexel28
Suppose that $f(m,n)=f(m',n')$, then we'd have that $2^{m-1}(2n-1)=2^{m'-1}(2n'-1)$.

So let me ask you this, we can assume WLOG that $m\leqslant m'$, right? So this means that $m'-1-(m-1)=m'-m\geqslant 0$ and so dividing through we get $2^{m'-m}(2n-1)=2n'-1$. Now, if $m'-m>0$ what would the problem be with that?
Spoiler:
think parity
I don't know or understand what the problem would be.

4. Originally Posted by dwsmith
I don't know or understand what the problem would be.
How do you know automatically that $2x\ne 2y+1,\text{ }x,y\in\mathbb{Z}$?

5. Originally Posted by Drexel28
How do you know automatically that $2x\ne 2y+1,\text{ }x,y\in\mathbb{Z}$?
No integer can satisfy that equation to make it true.

6. Originally Posted by dwsmith
No integer can satisfy that equation to make it true.
Because...why?

7. Originally Posted by Drexel28
Because...why?
Because to make that equation true we need an integer and fraction.

8. Originally Posted by dwsmith
Because to make that equation true we need an integer and fraction.
I'm looking for a specific phrase here "The LHS is ____ but the RHS is ____"

9. The left is even and the right is odd.

10. Originally Posted by dwsmith
The left is even and the right is odd.
And how does the help us with $2^{m'-m}(2n-1)=2n'-1$?

11. Originally Posted by Drexel28
And how does the help us with $2^{m'-m}(2n-1)=2n'-1$?
The left is even and the right is odd but what does that have to with m'-m>0?

12. Originally Posted by dwsmith
The left is even and the right is odd but what does that have to with m'-m>0?
If $m'-m>0$ it is true the LHS is even and the RHS is odd, right? But, as we said that's ridiculous. So it can't be true that $m'-m>0$ and since $m'-m\geqslant0$ for sure and it's an integer what may we conclude?

13. Originally Posted by Drexel28
If $m'-m>0$ it is true the LHS is even and the RHS is odd, right? But, as we said that's ridiculous. So it can't be true that $m'-m>0$ and since $m'-m\geqslant0$ for sure and it's an integer what may we conclude?
Well if it equals zero, the left is odd and the right is odd. If it is >0, the right is even and the left is odd.

14. [QUOTE=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd. [quote]
Which is good!

If it is >0, the right is even and the left is odd.

So...it must be true that?!

15. [quote=Drexel28;499961][quote=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd.
Which is good!