# Proof that NxN~N

by cragar
Tags: nxnn, proof
 P: 2,466 I thought of a way to use Gaussian integers to show that NxN~N We look at (1+i)(1-i) and this corresponds to the coordinate (1,1) then (1+2i)(1-2i)-->(1,2) then (1+3i)(1-3i)-->(1,3).... and you keep doing this, so we have injected NxN into N.
 P: 2,466 actually there is a problem with this (x,y) and (y,x) get mapped to the same integer
 Mentor P: 21,313 It looks to me like your mapping goes from N to N x N. Is that what you intended? (1 + i)(1 - i) = 1 - i2 = 1 + 1 = 2. So here the integer 2 is mapped to (1, 1). Did you mean for it to go the other way?
 Math Emeritus Sci Advisor Thanks PF Gold P: 39,568 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 "one-to-one" but not "onto".
Mentor
P: 18,334
 Quote by HallsofIvy 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 "one-to-one" but not "onto".
But ##\mathbb{N}## is equivalent to ##\mathbb{N}\times\mathbb{N}##...
P: 1,066
 Quote by HallsofIvy 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 "one-to-one" but not "onto".
The rationals and the naturals do have the same cardinality.

 Related Discussions Calculus & Beyond Homework 3 Calculus & Beyond Homework 5 Calculus & Beyond Homework 21 Calculus & Beyond Homework 1 Calculus & Beyond Homework 1