Register to reply 
Proof that NxN~N 
Share this thread: 
#1
Mar2614, 11:41 PM

P: 2,468

I thought of a way to use Gaussian integers to show that NxN~N
We look at (1+i)(1i) and this corresponds to the coordinate (1,1) then (1+2i)(12i)>(1,2) then (1+3i)(13i)>(1,3).... and you keep doing this, so we have injected NxN into N. 


#2
Mar2714, 03:16 AM

P: 2,468

actually there is a problem with this (x,y) and (y,x) get mapped to the same integer



#3
Mar2714, 10:41 AM

Mentor
P: 21,408

It looks to me like your mapping goes from N to N x N. Is that what you intended? (1 + i)(1  i) = 1  i^{2} = 1 + 1 = 2. So here the integer 2 is mapped to (1, 1). Did you mean for it to go the other way?



#4
Mar2714, 02:37 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,683

Proof that NxN~N
The fundamental problem is that N x N is NOT equivalent to N, it has the same cardinality as the set of rational numbers. It appears that your assignment is "onetoone" but not "onto".



#5
Mar2714, 02:57 PM

Mentor
P: 18,345




#6
Mar2714, 03:01 PM

P: 1,072




Register to reply 
Related Discussions  
Another proof involving orders of groups. Please help me make this proof airtight.  Calculus & Beyond Homework  3  
Can someone peek at a proof? (metric spaces, basic proof)  Calculus & Beyond Homework  5  
Did I skip a major step in this proof? + Theory of this proof  Calculus & Beyond Homework  21  
Proof Involving Continuity, Irrational Numbers From Elementary Proof Class  Calculus & Beyond Homework  1  
Comparison Proof via axioms, almost done need hints for finish and proof read  Calculus & Beyond Homework  1 