Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Set Theory, One to One Correspondence

  1. Apr 3, 2008 #1
    1. The problem statement, all variables and given/known data

    Show that the equation f(m,n) = 2^m(2n+1)-1 defines a one-to-one correspondence between w x w to w.

    Where w (omega) is a symbol used to represent the 0,1,2,3,4,5,6...

    Question: The book defines a one to one correspondence as a one to one function from A onto B. Is this in effect a bijection since its also onto?

    Further Question: The next question asks to find a one to one correspondence between [0,1] and (0,1) in the reals. This leads me to believe that the function does not have to be onto since I dont believe it is possible to have a bijection between a closed dense set to an open one. What do you make of this?

    3. The attempt at a solution

    I keep coming back to induction though it gets messy quickly and I cant seem to resolve some of my problems.

    f(m,n) = 2^m(2n+1)-1
    Induction on m
    Base: Let m = 0 then f(0,n) = 2n

    Must show that if f(m',n') = f(0,n) then m' = 0 and n'=n

    Proof by induction on n

    Base: Let n = 0 then f(0,0) = 0
    Suppose by contradiction that m' or n' do not equal 0
    Implying that 2n'+1 >or= 3 or 2^m' >= to 2
    Implying f(m',n') >or= 1 > 0 Contradiction thus m'=n'=0

    Induction Step: n implies n^+ (Successor operation also read as n+1)
    f(0,n^+) = 2n^+ = 2n+2 = f(0,n)+2 I'm unsure where to go from here, I assume I need to use my induction hypothesis somehow.

    Ie: If f(m',n') = f(0,n) then m' = 0 and n' = n.

    ALSO NOTE: This is only to prove that the function is injective, any ideas on how to prove its onto (If needed?)
  2. jcsd
  3. Apr 3, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Try to describe a method to find the inverse. If I give you N, how would you try to find an m and n such that N=f(m,n)? Hint: think about the prime factorization of N+1. Once you get that, you may be able to answer the 'onto' question as well.
  4. Apr 3, 2008 #3
    Well if its even then m = 0 and n is given by 2n = N

    If its odd then remove as many factors of 2 from N+1 and then n is dictated by whatever odd number is left (or 0).

    Problem: I'm not sure how this can be a rigorous proof, we have not proved prime factorization nor do I believe I can just say "remove all factors of 2".

    I'll think about it

    Well I got the bijection between [0,1] and (0,1)

    [0,1] -> [0,1)
    1/n for all n in w to 1/(n+1)
    Leave the rest

    [0,1) -> (0,1)
    n/(n+1) for all n in w to (n+1)/(n+2)
    Leave the rest

    Compose them.
    Last edited: Apr 3, 2008
  5. Apr 3, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    Right. That is a perfectly rigorous proof. You've given a perfectly deterministic and unique way of finding m and n given N. And, sure, it depends on unique prime factorization. But I don't think you can do it any other way.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook