Register to reply

Proof that NxN~N

by cragar
Tags: nxnn, proof
Share this thread:
cragar
#1
Mar26-14, 11:41 PM
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.
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
cragar
#2
Mar27-14, 03:16 AM
P: 2,466
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,291
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,552
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,299
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,066
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