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

I Cantor's diagonal number

  1. Jan 11, 2019 #1
    Let me consider the reals between [0;1] and work in binary numeration system.
    I order the list like this: first number is 1, second is 0.0, third is 0.10. For the next numbers, the rule is that all the diagonal decimal digits are 0's. Cantor's diagonal number will then be 0.111111....=0.(1)=1. So, he failed to produce a number which is not on my list.
     
  2. jcsd
  3. Jan 11, 2019 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    There is a subtlety in the diagonal argument that the decimal expansion of a number is not unique. To stay in base 10, any terminating decimal has two expansions. E.g.

    ##0.1234##

    Can also be written as:

    ##0.123999 \dots##

    So, you need two further statements:

    First, where the decimal expansion is ambiguous, you choose the terminating one. I.e. ##0.1234## appears on the list once as ##0.1234##. And not as ##0.123999 \dots##

    Second, for the diagonal number you must avoid ending up with an infinite sequence of 9's. There are many ways to do this. One simple way is never to change a digit to a 9. You've always eight other digits to choose from.

    Your binary problem is quite nice. You need to ensure that the final number is not ##0.111 \dots ##. One way round it would be wait until you get a non-terminating decimal - which must be a mixture of 0's and 1's - and jump to the next digit that is 1 and change that to 0.
     
    Last edited: Jan 11, 2019
  4. Jan 11, 2019 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    Actually, to make a further point.

    Let's say that Cantor's diagonal argument uses numbers in base 10. Then, that constitutes a proof. That proof may not work directly if you change to binary. But, it doesn't have to. You have a valid proof. In particular, any difficulties (or even an impossiblity) of transferring a specific proof to binary representation makes no difference to the original proof.

    In different circumstances, you may switch to binary and produce a very nice proof (of something) exploiting the simplicity of binary numbers. But, the fact that your (binary) proof may not be directly transferable to base 10 wouldn't invalidate your binary proof. In fact, many mathematical proofs hinge on presenting the problem in a certain way.

    You can prove something using base 10, or you could prove something using binary, but you don't have to do both.
     
  5. Jan 11, 2019 #4
    How long should I wait?
    If you change a single 1 with 0 you obtain a rational number.
     
  6. Jan 11, 2019 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    The simplest argument is that it doesn't matter. Let's assume, for the sake of argument, that Cantor's diagonal proof doesn't work in binary representation. Let's assume that it needs at least 3 digits to work properly. Then the proof is still valid.
     
  7. Jan 11, 2019 #6
    Or alternatively, go down a different diagonal.
     
  8. Jan 11, 2019 #7

    fresh_42

    User Avatar
    2018 Award

    Staff: Mentor

    Don't we have the same phenomenon in any basis? Binary ##0.111\ldots = 1\,.##
     
  9. Jan 11, 2019 #8
    So, for numbers in binary system , reals could be countable?
    Proof it in binary. Countability cannot depend on the system used.
     
  10. Jan 11, 2019 #9

    fresh_42

    User Avatar
    2018 Award

    Staff: Mentor

    No. Even if you allow all doubles the argument still works.
     
  11. Jan 11, 2019 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    No. At worst you would need a different proof. If a proof doesn't work, all that means is that that proof is no good. It doesn't mean that the opposite is automatically true.

    In any case, it's the same list whether the numbers are expressed in base 10, binary or Roman numerals. The list is either complete or not. The diagonal proof (using base 10 representation) proves the reals are uncountable.
     
  12. Jan 11, 2019 #11

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    Exactly, you don't have to prove it using only binary. If you list the reals in binary, convert them to base 10 and apply Cantor's argument. That's it proved.

    Otherwise, you could argue that most of number theory is not proved, because no one has proved it using Roman numerals! You could argue that ##25 \times 7 = 175## may not be true until you have checked it in Roman numerals, or in binary, or in hexadecimal.

    In mathematics, one proof is enough. It might be nice to come up with another proof that the reals are uncountable. For example, not using the diagonal argument or applying some other constraint to make it harder. But, that doesn't affect the proof you already have.

    Otherwise, nothing would ever be proved. You could always say: prove it again, not using base 10 or not using the Zeta function or not using complex numbers, or whatever.

    A proof is a proof.
     
  13. Jan 12, 2019 #12
    Let's stay in binary and consider some rational's with periodic part (10). I arrange my list so that on diagonal is a succesion of 01's. Cantor's diagonal number will then be 0.(10). Because 0.(10) is missing from my initial list, it means this set is uncountable.
     
  14. Jan 13, 2019 #13

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    Strictly, speaking, what the diagonal argument proves is that there can be no countable list containing all representations of the real numbers in [0,1]. A representation being an infinite decimal (or binary) expansion. So the representation 0.01 and the representation 0.001111... are different representations, but they represent the same number.

    Of course, it's also true that there is no countable list containing every real number in [0,1]. The proof is a little bit messier, but not much.

    Note that the only reals that have double representations are ones that end in all 0s or all 1s in the binary expansion. So modify the diagonal argument so that it never produces one of those.

    Here's one way to do that: Start with your original list. Let ##f(n)## be the ##n^{th}## real on your list. Now define a new list ##\overline{f}(n)## as follows:
    • If ##n## is a multiple of 3, then ##g(n) = f(n/3)##
    • If ##n+1## is a multiple of 3, then ##g(n) = 0.000...##
    • If ##n+2## is a multiple of 3, then ##g(n) = 0.1111...##
    Now, diagonalize the new list ##g##. You're guaranteed to get a representation that does not appear anywhere on ##g##. If it's not on the list ##g##, then it is not on the list ##f##, either. And furthermore, you can prove that this number cannot end with all 0s or all 1s.
     
    Last edited: Jan 13, 2019
  15. Jan 13, 2019 #14

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    I'm not sure I understand what you're saying. But Cantor's argument goes like this:
    1. If a set ##S## is countable, then (by definition), there is an infinite list ##s_1, s_2, ...## that contains every element of ##S##.
    2. There is no list that contains every element of the reals.
    3. So, the reals are not countable.
    The rationals are countable. So you can produce a list that contains every rational number. If you use Cantor's trick to produce a real that is not on that list, then that diagonal number is guaranteed to be irrational.
     
  16. Jan 13, 2019 #15
    Cantor's Diagonalization Argument is one of the most elegantly simple proofs of a complex concept in all of mathematics. Unfortunately, it gets simplified even further to teach it to beginners. And almost all of the objections to it, that you will find, arise from these simplifications.

    Cantor wanted to prove that there can be sets that could not be counted. To do so, all he had to do was demonstrate one. And the one he used was not the set of real numbers. Let me repeat that: Cantor did NOT use diagonalization on any set of real numbers. He used the set of all possible binary strings. While "1.000..." and "0.1111..." may represent the same number in binary, "1000..." and "0111..." are still different strings. What you found was a string that was not in the set of strings that you counted, establishing that there was a string you didn't count exactly as Cantor intended.

    +++++

    Some comments:
    • The only infinite strings that most beginners will be familiar with, are the decimal representations of either irrational numbers or repeating rational numbers. It's easier to teach with familiar tools, then to define new ones. Unfortunately, it isn's as accurate.
    • Decimal representations of real numbers work fine in the proof, if care is taken to not use the digit "9" in a way where it could repeat indefinitely. It's simplest to just not use it at all.
    • The same caveat applies to any base B; to make the argument work with the real numbers, just don't use the character for B-1. But this isn't possible with binary representation.
    • You found a clever way to demonstrate why it isn't possible. Still, all you did was find a schema where the argument fails - that doesn't means it has to fail, just that you can't use that schema.
    • There's another simplification that tricks a lot of beginners. It isn't really a proof by contradiction. What the argument shows, is that (A) if there is a way to count a set ##S## of binary strings, (B) then that counting process can be used to show there is a binary string that is not in ##S##. Notice that I never claimed that ##S## included all such strings. Cantor didn't either.
     
  17. Jan 13, 2019 #16

    FactChecker

    User Avatar
    Science Advisor
    Gold Member
    2018 Award

    That is a very good point. One thing I like about the application to the reals in decimal form is that it gives some intuitive idea of how much greater the unlisted numbers are than any countable subset. Every decimal place gives a multiplier of 9 to the set of unlisted numbers. I think this makes one more easily accept that the rational numbers form a dense set of measure zero.
     
  18. Jan 13, 2019 #17
    0.(10) is rationa
    Diagonal 0.(10) is rational and is not on my initial list of rational's with period 10.
     
  19. Jan 14, 2019 #18
    To clarify what I said, the diagonal method with straight replacement of characters does not work on a set of real numbers when expressed in binary. It does work on the same set of real numbers if expressed in a base B>2, but only if care is taken to not use the character B-1. Or with a more complicated schema to change the characters. What stevendaryl said is true in decimal notation, or his modified method in binary. I'm sure he was thinking of that.
     
  20. Jan 15, 2019 #19
    OK, no binary.
    Supose I have the list of rationals.
    Can you prove that any diagonal number is irrational?
    No matter how I order my list.
     
  21. Jan 15, 2019 #20

    FactChecker

    User Avatar
    Science Advisor
    Gold Member
    2018 Award

    If you have the list of all rationals (assumed for a proof by contradiction) then any number not on the list must be irrational.

    The proofs that I have seen that a number is irrational have been specialized for that number. I don't know if there is a general method of proof that could be applied.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?