- 207

- 0

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