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

Cantors diagonals Listable vs. countable

  1. Feb 2, 2008 #1
    So i'm familier with cantos diagonals, but fail to see how something being unlistable makes it uncountable. Now a set being countable is to say it has a one to one corrospondance to the natural numbers, but using the diagonal method one can prove that the natural numbers are themselves unlistable.

    Given any table of all the natural numbers, one can construct a number not in the table, simply by chosing something other then the n'th character in each number given, (ofcause chosing anything when no character apears).

    Can someone clearify this for me? So far my conclusion is that either my textbooks are not being rigid enough in their proofs or the only thing cantors diagonal proof realy proves is that it's absurd to talk about a complete list of even a countable set.
     
  2. jcsd
  3. Feb 2, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A "list" means to have a "first", a "second" etc. A list is precisely a one-to-one correspondence with the natural numbers.

    I can't speak to whether your textbooks are not being rigid (did you mean "rigorous"?) enough but your "proof" that the natural numbers are unlistable doesn't work.
    "Choosing something other than the nth character in each number given" will, since there are an infinite number of natural numbers, result in a resulting infinite sequence of digits. That is NOT "a number not in the table" because it is NOT a natural number. All natural numbers have a finite number of digits.
     
  4. Feb 2, 2008 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What do you think a list is?
     
  5. Feb 3, 2008 #4
    Well as they refere to a list in my textbook, they refere to "imaginary" listings like on a blackboard, and while this implies a ordering, it also requires both a first element and a last element, which the natural numbers have not.

    But thank you HallsofIvy for the answer, I understand now that the key point isn't the existance of a diagonal, but that the natural numbers are finite sequences, even though there are infinite many such sequences.
     
  6. Feb 3, 2008 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A list must always have a "first member" and there must always be a "next" member. But there does not have to be a "last" member.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cantors diagonals Listable vs. countable
Loading...