- #1
moo5003
- 207
- 0
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?)