# Set Theory, One to One Correspondence

1. Homework Statement

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?)

Related Calculus and Beyond Homework Help News on Phys.org
Dick
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.

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".

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:
Dick