# [SOLVED] Relations

Show 40 post(s) from this thread on one page
Page 1 of 3 123 Last
• Apr 23rd 2010, 03:52 PM
dwsmith
[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.
• Apr 23rd 2010, 05:52 PM
Drexel28
Quote:

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
• Apr 23rd 2010, 06:03 PM
dwsmith
Quote:

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.
• Apr 23rd 2010, 06:04 PM
Drexel28
Quote:

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}$?
• Apr 23rd 2010, 06:05 PM
dwsmith
Quote:

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.
• Apr 23rd 2010, 06:07 PM
Drexel28
Quote:

Originally Posted by dwsmith
No integer can satisfy that equation to make it true.

Because...why?
• Apr 23rd 2010, 06:08 PM
dwsmith
Quote:

Originally Posted by Drexel28
Because...why?

Because to make that equation true we need an integer and fraction.
• Apr 23rd 2010, 06:09 PM
Drexel28
Quote:

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 ____"
• Apr 23rd 2010, 06:10 PM
dwsmith
The left is even and the right is odd.
• Apr 23rd 2010, 06:12 PM
Drexel28
Quote:

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$?
• Apr 23rd 2010, 06:14 PM
dwsmith
Quote:

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?
• Apr 23rd 2010, 06:16 PM
Drexel28
Quote:

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?
• Apr 23rd 2010, 06:20 PM
dwsmith
Quote:

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.
• Apr 23rd 2010, 06:21 PM
Drexel28
[QUOTE=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd. [quote]
Which is good!

Quote:

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

So...it must be true that?!
• Apr 23rd 2010, 06:24 PM
dwsmith
[quote=Drexel28;499961][quote=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd.
Quote:

Which is good!