• Support PF! Buy your school textbooks, materials and every day products Here!

Set Theory, One to One Correspondence

  • Thread starter moo5003
  • Start date
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?)
 

Answers and Replies

Dick
Science Advisor
Homework Helper
26,258
618
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.
 
207
0
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.
 
Last edited:
Dick
Science Advisor
Homework Helper
26,258
618
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.
 

Related Threads for: Set Theory, One to One Correspondence

  • Last Post
Replies
3
Views
8K
Replies
2
Views
13K
Replies
3
Views
1K
Replies
6
Views
2K
Replies
13
Views
2K
Replies
8
Views
2K
  • Last Post
Replies
3
Views
2K
Top