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

Cantor's diagonal argument

  1. Jun 23, 2008 #1
    Hi
    I've some trouble understanding (or maybe accepting) Cantor's diagonal argument. When I was young I had no trouble accepting it and it seemed perfectly logical, but after a long hiatus and returning to my original interests, I seem less than convinced (must be some age-related or brain decay issue :-)

    Now let's say I have the set of all positive integers. This set is clearly countable/enuimerable, so I can place all its members in a sequential list. What stops me from applying the diagonal argument to this list, and getting a positive integer that does not belong to the set, which by definition contains all positive integer? what gives?
     
  2. jcsd
  3. Jun 23, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Have you tried an example?
     
  4. Jun 23, 2008 #3
    An example of the original argument? yes of course. But the problem is that seemingly I can apply the same reasoning to just the integers to get a contradictory result and I don't see where the fault is....
     
  5. Jun 23, 2008 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    How do you propose to apply the diagonal argument to the list? Are you proposing to write the integers like this, in say binary:

    ....0000001
    ....0000010
    ....0000011


    and so on? We may go ahead and apply the argument to it and prove that the infinitely long string of digits has only finitely many non-zero entries on it. This will be difficult since you'll have to make the n'th digit (from the right) in the n'th string non-zero for all n greater than about 3 (since n>log_2 n for n>2). Trying other bases won't help: eventually n> log n for any base.


    Usually people try to misapply the argument to the (decimal) representations of rational numbers. In doing so at least they construct a real number. Erroneously they assume that it must be rational.
     
  6. Jun 23, 2008 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No; I mean an example of the new 'argument'. (By the way, what sort of example did you apply the original argument to?)

    Don't just say "it seems so" -- try it. Pick your favorite list of all integers and try to apply the diagonal argument. Have you obtained a result contradicting the hypothesis it was a list of all integers? (matt has already answered this question)
     
  7. Jun 23, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    To reiterate matt grime: all natural numbers have a finite number of non-zero digits. The number you produce by "mimicing" Cantor's method may NOT have only a finite number of non-zero digits.
     
  8. Jun 25, 2008 #7
    Well, the typical set of reals in which you flip a digit (of their decimal representation) each time, producing a new real.

    Ok, let's say I have the list of integers. For each integer, I pick a random digit position (different from the ones picked previously), zero-padding if necessary and change it.
     
  9. Jun 25, 2008 #8
    Yes, but I have trouble seeing that the diagonal argument applied to integers implies an integer with an infinite number of digits. I mean, intuitively it may seem obvious that this is the case, but then again it's also obvious that for every integer n there's another integer n+1, and yet this does not imply there is an actual integer with an infinite number of digits, nevermind that n+1->inf when n->inf.
     
  10. Jun 25, 2008 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If you took the natural listing that I gave, then it is clear that the diagonal argument produces the string

    ...1111100

    which is not a natural number's binary expansion. For an arbitrary listing, then it will be hard to prove it directly (but it will still be true). Of course, we don't have to! It is up to you to demonstrate that this string which potentially has an infinite number of 1s in it doesn't.
     
  11. Jun 25, 2008 #10

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You understand, don't you, that Cantor's method involves changing one digit for every number on the list. Suppose you were to do this: list all positive integers (that's easy). Now go through that list doing the following: if the nth digit of the nth integer is a "5", write a "6" for the nth digit of the new number.

    If you did that to any infinite list of real numbers rather than integers, you would get a real number with all digits either "5" or "6"- and because your list is infinite, . That would have to be a real number that is NOT on the list (since it differs from the nth number in the nth decimal place) and so the set of all real numbers cannot be "listed"- is not "countable".

    But with an infinite list of integers you would still get an infinite (because you get one digit from each integer) list of digits (all "5"s or "6"s) which is NOT an integer.
     
    Last edited: Jun 25, 2008
  12. Jun 25, 2008 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Don't merely say you have a list: explicitly choose one! (Or, at least, choose an initial segment of such a list)

    Again, don't just say... do.

    (And preferably do all of this in the simplest possible way, so that you can see what's happening)
     
  13. Jun 25, 2008 #12
    Ok, understood. Wouldn't it be possible, though, that an infinite amount of these digits be zeros?
     
    Last edited: Jun 25, 2008
  14. Jun 25, 2008 #13
    matt, not to mean disrespect but I believe saying "it's so because it is" is not very illuminating, at least if you're trying to be didactic (as opposed to viewing this as a confrontation or who-knows-more contest). You of course don't have to prove that I'm wrong, but since you take the trouble of answering, you should at least try to prove that you are right, and not merely drop a statement and say it's true because you or some authority says so.

    Anyawy HallsofIvy's reasoning has (almost) convinced me.
     
    Last edited: Jun 25, 2008
  15. Jun 25, 2008 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I can prove it since the natural numbers are (by definition) countable, surely that proof is sufficiently obvious as to not require explicitly saying? Sorry if you don't like indirect proofs, but sometimes that is all you get. I did give you a constructive demonstration for the natural binary listing, and for the natural listing in any other base. It might well be possible to give a constructive proof for an arbitrary listing. Try it. The proof would probably require you to show that you can divide the list into chunks (probably of variable lengths) in such a way that at least one of the diagonal elements (i.e. the n'th digit in the n'th number in the list) must be zero via some counting argument.
     
  16. Jun 25, 2008 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    View it this way. Do your argument. You have two assumptions

    a) That we have a bijection from N to N (the listing)
    b) that the string produced has finitely many digits.

    We know we have a contradiction, therefore one (or both) of these is false. That is all the argument tells us. On its own it is neither sufficient to prove the natural numbers are countable, nor that they are uncountable. We have no way of deciding which from this information alone. Thus if we wish to prove they are countable or otherwise, then we have to look elsewhere. Trivially they are countable. This proves that bijections exist. If f is such then it must be the case that b) is false.

    The standard argument uses only one assumption: that there is a bijection from R to N - there is no assumption on the string produced yielding a real number - it does so by construction. Since we reach a contradiction, this must be false.
     
    Last edited: Jun 25, 2008
  17. Jun 25, 2008 #16

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    If you do it as I said, you all digits must be "5" or "6"- no "0"s allowed!
     
  18. Jun 30, 2008 #17
    Actually I'm not assuming that the produced number has a finite amount of non-zero digits (since it may have an infinite amount of leading zeros and still be an integer)

    But anyway I've been convinced. Thanks to everyone for your answers
     
  19. Jun 30, 2008 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You (that's a generic you) are assuming that it is a finite number of non-zero digits when you assume it is an integer, and if it's assumed to not be an integer then there's no problem. I really don't understand how you can say otherwise. Having a leading infinite string of zeroes in no way contradicts the assumption that there must be a finite number of non-zero entries for it to represent an integer.
     
    Last edited: Jun 30, 2008
  20. Aug 6, 2008 #19
    Hoping I may be permitted to make a belated contribution here.

    Summarising the key points from some of the other posts:
    The key to the problem is that the new 'number' generated by the diagonal argument will have an infinite number of non-zero digits resulting from the infinite number of leading zeros in the original numbers. Such a number is not an integer since, although the set of integers has an infinite number of members, each individual member is finite and must have a finite number of non-zero digits.

    I can accept this, but my question is: if 'numbers' such as ....111111111 are not integers, what are they? Are they reals? If they are reals and whole numbers, why are they not integers? Do they actually exist at all? If not why not?
     
  21. Aug 6, 2008 #20

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    They are not anything. It is possible to combine symbols in ways that make no sense! That's one of them.

    You are confusing "numbers" with "numerals". The way numbers are defined has nothing to do with numerals and certainly not with the base 10 numeration system.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cantor's diagonal argument
Loading...