(adsbygoogle = window.adsbygoogle || []).push({}); 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?)

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**