Page 1 of 3 123 LastLast
Results 1 to 15 of 34

Math Help - [SOLVED] Relations

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    [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.
    Last edited by dwsmith; April 23rd 2010 at 06:23 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dwsmith View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dwsmith View Post
    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}?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dwsmith View Post
    No integer can satisfy that equation to make it true.
    Because...why?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    Because...why?
    Because to make that equation true we need an integer and fraction.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dwsmith View Post
    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 ____"
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    The left is even and the right is odd.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dwsmith View Post
    The left is even and the right is odd.
    And how does the help us with 2^{m'-m}(2n-1)=2n'-1?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dwsmith View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    [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.
    Which is bad!


    So...it must be true that?!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    [quote=Drexel28;499961][quote=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd.
    Which is good!


    Which is bad!


    So...it must be true that?!
    I am confused on how that proves it is an injection though.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 3 123 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] Composition of two relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 7th 2009, 10:21 AM
  2. [SOLVED] Help with equivalence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2009, 07:44 PM
  3. [SOLVED] Equivalance Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 10th 2009, 03:10 AM
  4. [SOLVED] Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 22nd 2008, 09:28 PM
  5. [SOLVED] Transitivity in set relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: October 11th 2008, 05:48 PM

Search Tags


/mathhelpforum @mathhelpforum