Register to reply

Proof that NxN~N

by cragar
Tags: nxnn, proof
Share this thread:
cragar
#1
Mar26-14, 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)(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.
Phys.Org News Partner Mathematics news on Phys.org
Researcher figures out how sharks manage to act like math geniuses
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
cragar
#2
Mar27-14, 03:16 AM
P: 2,468
actually there is a problem with this (x,y) and (y,x) get mapped to the same integer
Mark44
#3
Mar27-14, 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 - i2 = 1 + 1 = 2. So here the integer 2 is mapped to (1, 1). Did you mean for it to go the other way?

HallsofIvy
#4
Mar27-14, 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 "one-to-one" but not "onto".
micromass
#5
Mar27-14, 02:57 PM
Mentor
micromass's Avatar
P: 18,345
Quote Quote by HallsofIvy View Post
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}##...
Jorriss
#6
Mar27-14, 03:01 PM
P: 1,072
Quote Quote by HallsofIvy View Post
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.


Register to reply

Related Discussions
Another proof involving orders of groups. Please help me make this proof air-tight. 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