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

How is the set of all natural numbers, N, denumerable?

  1. Oct 21, 2012 #1
    I know the history of how set theory came about and how Cantor showed the real numbers between (0,1) were non-denumerable.

    He did this by showing that they cant be put into a one-one correspondence with N (1, 2, 3...)
    ...So what does that really tell me? I know it tells me that the infinity of the reals is larger, but how does that tell me that N is countable itself?

    Did we just assume N is countable by putting a one-to-one correspondence from N to N itself?
    Why say "A set is countable if it can be put into a one-to-one correspondence with N."

    Why pick N for the role of determining the denumerability of other sets?
  2. jcsd
  3. Oct 21, 2012 #2
    I'm not big on number theory and I know others will post after me with much more knowledge but I will start it off by what makes sense to me.

    The definition, as you say, is that it can be mapped onto ℝ with a one to one correspondence. If it can we call it countable. Don't mess this up with your connotation of countable which, to almost everyone, means you can count it. You have to throw out your old version of countable and replace it with this one. When then asked why is ℝ is considered countable you simply say because it has a one to one correspondence with ℝ. It's almost like an axiom, you don't really ask why a point is called a point, any answer will most likely end up referring back to itself.

    In regards to why use ℝ I'm pretty sure they use it because it has the lowest cardinality of any infinite set.
  4. Oct 21, 2012 #3
    Isn't it just the definition? In practice, when you count a bunch of things, the number of items is one of the natural numbers. It's a bit like asking why 2 has the shape it does--it's just the definition we all agree on so we can easily communicate.

    Or said another way: there's nothing magical about definitions. Things are just defined the way they are because it has proven useful to define them that way. If you have an application where it makes sense to denumerate a set of items with -4 items, you can just define countable in that context to refer to the integers instead of the natural numbers.

    Maybe I'm missing the point of your question, though!
  5. Oct 21, 2012 #4
    Edit: just saw above. Oh okay, that makes sense. I wasn't sure if there was some exact reason.

    Yes, i understand what we mean by "countable."

    I didn't get why or where N came from for being THE set that all other sets need to be able to be mapped one-to-one to be called denumerable.

    Almost like an axiom makes sense I guess
  6. Oct 21, 2012 #5
    I did a little reading. I can't find an english translation of Cantor's paper, but I found a paper on jstor (http://www.jstor.org/stable/2975129) that discusses it. Corollary 2 of his Theorem 2 from "On a Property of the Collection of All Real Algebraic Numbers" is "The real numbers cannot be written as an infinite sequence. That is, they cannot be put into a one-to-one correspondence with the natural numbers."

    That suggests he was interested specifically in the natural numbers because those are often used to index a sequence of numbers.

    If anyone has an english translation of Cantor's actual paper, it might provide further interesting details.
  7. Oct 21, 2012 #6


    User Avatar
    Science Advisor

    Yes, the Naturals are a somewhat-canonical choice, but there is no reason not

    to alternatively search for a bijection with the Rationals, or a two-way injection (DADT ;) )

    with the Rationals , per Ricky-Schroder-Bernstein theorem.
  8. Oct 22, 2012 #7


    User Avatar
    2017 Award

    Staff: Mentor

    The definition could use any other countable set, but I think that N (and maybe Z) is the most convenient choice.
  9. Oct 22, 2012 #8


    User Avatar
    Science Advisor
    Homework Helper

    well what would you pick as the world's simplest example of an infinite set?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook