Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof that NxN~N

  1. Mar 26, 2014 #1
    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.
     
  2. jcsd
  3. Mar 27, 2014 #2
    actually there is a problem with this (x,y) and (y,x) get mapped to the same integer
     
  4. Mar 27, 2014 #3

    Mark44

    User Avatar
    Insights Author

    Staff: Mentor

    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?
     
  5. Mar 27, 2014 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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".
     
  6. Mar 27, 2014 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    Insights Author

    But ##\mathbb{N}## is equivalent to ##\mathbb{N}\times\mathbb{N}##...
     
  7. Mar 27, 2014 #6
    The rationals and the naturals do have the same cardinality.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted