Results 1 to 6 of 6
Like Tree3Thanks
  • 2 Post By Plato
  • 1 Post By Plato

Math Help - Bijection question

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    Denmark
    Posts
    2

    Bijection question

    Hello,

    I need to show that (m,n) \mapsto 2^{m-1}(2n-1) is a bijection of \mathbb{N} \times  \mathbb{N} on \mathbb{N}

    I think I need to show that the expression is both injective and surjective, but I am not sure how to do that.

    Maybe a kind person can help me in some direction?

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Bijection question

    Quote Originally Posted by peter89 View Post
    I need to show that (m,n) \mapsto 2^{m-1}(2n-1) is a bijection of \mathbb{N} \times  \mathbb{N} on \mathbb{N}.
    Any positive integer is the product of a power of two times an odd number.
    EXAMPLES:
    21=2^0(2(11)-1),~32=2^5(2(1)-1),~44=2^2(2(6)-1).

    If
    \\2^n(2m-1)=2^k(2j-1)\\2^{n-k}(2m-1)=(2j-1)

    Because LHS is even and RHS is odd, then n=k.

    Can you finish?
    Thanks from topsquark and peter89
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2013
    From
    Denmark
    Posts
    2

    Re: Bijection question

    Thanks for your reply. I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2. I can see it works by doing some examples, but how I precisely can show it? Hmm, maybe a hint?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Bijection question

    Quote Originally Posted by peter89 View Post
    I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2.
    Frankly, I do not know. It is a basic fact of number theory. You did post this in a number theory forum.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Bijection question

    Quote Originally Posted by peter89 View Post
    I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2.
    This can be shown by strong induction. However, you need to decide what facts you can rely on. You are not going to prove commutativity of addition, right? Similarly, it is somewhat obvious that dividing a positive integer repeatedly by 2 will eventually yield an odd number because with each division the number is getting smaller, and this can't go on forever.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868

    Re: Bijection question

    Definition of "even": a natural number, n is even if and only if n= 2k where k is a natural number.

    If N is a natural number, it can be written as N= 2K for some natural number K. If K is odd, you are done- N is "2 to the 1 power" times n odd number. if K is even, K= 2M for some integer M. If M is odd, you are done: N= 2K= 2(2M)= 4M is "2 to the 2 power" times an odd number. If M is even, M= 2J for some integer J. If J is odd....
    Note that N> K> M> J... so that will eventually terminate.
    Last edited by HallsofIvy; October 6th 2013 at 12:47 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question involving showing there's a bijection
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 14th 2012, 04:53 PM
  2. simple question on bijection
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 13th 2010, 10:33 AM
  3. Bijection
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 11th 2009, 05:28 AM
  4. bijection help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 7th 2008, 08:41 AM
  5. Bijection
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 22nd 2006, 03:42 PM

Search Tags


/mathhelpforum @mathhelpforum