1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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