Set Theory, One to One Correspondence

[moo5003]

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 don't believe it is possible to have a bijection between a closed dense set to an open one. What do you make of this?

The Attempt at a Solution

I keep coming back to induction though it gets messy quickly and I can't 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?)

 

[Dick]

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.

 

[moo5003]

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.

 

[Dick]

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.