1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Use Cantor's Diagonalization on the set of Natural Numbers?

  1. Jan 24, 2010 #1
    1. The problem statement, all variables and given/known data

    This is actually only related to a problem given to me but I still would like to know the answer. From my understanding, Cantor's Diagonalization works on the set of real numbers, (0,1), because each number in the set can be represented as a decimal expansion with an infinite number of digits. This means 0.5 is not represented only by one digit to the right of the decimal point but rather by the "five" and an infinite number of 0s afterward.

    My question then is can the set of natural numbers be represented similarly, ie instead of 5, have an infinite number of 0s preceding it (to the left of it) so the number is represented instead as ...000000005. Then the set of natural numbers can be aligned similarly as done in Cantor's Diagonalization with all numbers represented in its own row with each digit represented as d1, d2, d3, and so on with d being an element of {0,1,2,3,4,5,6,7,8,9}. The difference however would be that the digits in the rows, instead of going from left to right, would go from right to left. d1 would the the rightmost digit (the "ones" digit), d2 would be to the left, and so on. If we create a new number, n = d1d2d3d4... where dI = {1 if dII !=1, 2 if dII = 1}, then this new number will be different than every number in the table which should have represented all the natural numbers. Thus the set of natural numbers is not countable. Sorry if this was confusing, I didn't want to rewrite Cantor's Diagonalization but I didn't want to leave too much out.

    2. Relevant equations

    Everything.

    3. The attempt at a solution

    The only thing I can come up with is that natural numbers cannot be represented with an infinite number of 0s to the left of the number. However, I don't understand then how that differs from representing all decimals as having an infinite number of 0s to the right of the rightmost positive integer.
     
    Last edited: Jan 24, 2010
  2. jcsd
  3. Jan 24, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That is a creatively weird argument, I'll give you that. But if you change the first digit in ...00005 to a 1 then what natural number is that supposed to represent?
     
  4. Jan 24, 2010 #3
    Thanks for the reply.

    To answer your question: "But if you change the first digit in ...00005 to a 1 then what natural number is that supposed to represent? "

    I'm assuming by "first digit" you mean the leftmost. Isn't that comparable to asking what changing the last digit of a decimal expansion in Cantor's Diagonalization would represent? It never really reaches there, right? My oddball diagonalization starts with the top right so the left most digit won't be changed until the end, which won't ever arrive.

    So you know, the original homework problem was for me to find an error in a proof that showed the set (0,1) is countable. The proof assumes I can mirror a decimal expansion across the decimal point to get a natural number. For example, 0.5 will be 5, 0.15 will be 51, 0.91421 will be 12419. That's what got me started on this.

    Thanks for any help.
     
    Last edited: Jan 24, 2010
  5. Jan 24, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper



    Infinite strings of digits are generally uncountable. That doesn't prove the natural number are uncountable. I can represent the finite set {0,1} using infinite strings of digits. That doesn't prove it's uncountable.
     
  6. Jan 24, 2010 #5
    Thanks for replying.

    I think I have to take back that second attempt without the zeroes. I can't come up with a closed interval subset of the natural numbers that will allow me to use diagonalization to arrive at a new number in the subset. So scratch that. Thanks.

    But I'm still confused about the original proposal, even if it is a bit odd. The diagonalization does in that case come up with a new number that is a natural number and is not listed even though all natural numbers should be listed.
     
  7. Jan 24, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Maybe we should just work on what's wrong with that proof. You can't 'mirror' a decimal expansion across the decimal point for every number in (0,1), can you? Only numbers that have a terminating decimal expansion. And they are countable.
     
  8. Jan 24, 2010 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    100.....0005 with an infinite number of zeros is not a natural number.
     
  9. Jan 24, 2010 #8
    Oh, that's where I'm going wrong. So an infinitely large number is not a natural number. I'll do some research to figure out why.

    Thanks for the help. I think I know which way to go on my homework assignment now. And just because it's interesting, I ran into another http://mathforum.org/library/drmath/view/51845.html" (third post) who had the same argument that I'm having but constructed it better. He likewise was forced to try to define how a number with no defined leftmost digit would act.

    Thanks for all the quick replies, I appreciate it.
     
    Last edited by a moderator: Apr 24, 2017
  10. Jan 25, 2010 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'll save you a little bit of trouble. 100...005 isn't a natural number because they are defined inductively. n=1 is the first one. Every natural number has a successor defined by n=n+1. The natural numbers are 1 and all of it's successors. You can prove by induction that they all have finite decimal expansions. 100...005 isn't one of them.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Use Cantor's Diagonalization on the set of Natural Numbers?
  1. Cantor Sets (Replies: 5)

  2. Cantor Set (Replies: 2)

Loading...