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

A question on Cantor's second diagonalization argument

  1. Oct 19, 2003 #1
    Hi,

    Cantor used 2 diagonalization arguments.

    On the first argument he showed that |N|=|Q|.

    On the second argument he showed that |Q|<|R|.

    I have some question on the second argument.

    From Wikipedia, the free encyclopedia:
    http://en.wikipedia.org/wiki/Cantor's_diagonal_argument

    The proof by contradiction proceeds as follows:
    • (1) Assume that the interval (0,1) is countably infinite.
    • (2) We may then enumerate the numbers in this interval as a sequence, { r1, r2, r3, ... }
    • (3) We shall now construct a real number x between 0 and 1 by considering the nth digit after the decimal point of the decimal expansion of rn. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows.
    r1 = 0 . 0 1 0 5 1 1 0 ...
    r2 = 0 . 4 1 3 2 0 4 3 ...
    r3 = 0 . 8 2 4 5 0 2 6 ...
    r4 = 0 . 2 3 3 0 1 2 6 ...
    r5 = 0 . 4 1 0 7 2 4 6 ...
    r6 = 0 . 9 9 3 7 8 3 8 ...
    r7 = 0 . 0 1 0 5 1 3 0 ...
    ...
    The digits we will consider are indicated in bold. From these digits we define the digits of x as follows.

    o if the nth digit of rn is 0 then the nth digit of x is 1
    o if the nth digit of rn is not 0 then the nth digit of x is 0
    For the example above this will result in the following decimal expansion.
    x = 0 . 1 0 0 1 0 0 1 ...
    The number x is clearly a real number between 0 and 1.
    • (4) However, it differs in the nth decimal place from rn, so x is not in the set { r1, r2, r3, ... }.
    • (5) This set is therefore not an enumeration of all the reals in the interval (0,1).
    • (6) This contradicts with (2), so the assumption (1) that the interval (0,1) is countably infinite must be false.

    Note: Strictly speaking, this argument only shows that the number of decimal expansions of real numbers between 0 and 1 is not countably infinite. But since there are expansions such as 0.01999... and 0.02000... that represent the same real number, this does not immediately imply that the corresponding set of real numbers is also not countably infinite. This can be remedied by disallowing the decimal expansions that end with an infinite series of 9's. In that case it can be shown that for every real number there is a unique corresponding decimal expansion. It is easy to see that the proof then still works because the number x contains only 1's and 0's in its decimal expansion.


    My question is:

    The first assumption was that we have a bijection between |N| and |R| iff R list is complete.

    Then Cantor showed that there is a way to construct a real number x between 0 and 1, that cannot be put in 1-1 correspondence with any natural number.

    Therefore, there are more real numbers between 0 and 1 then all natural numbers.

    Now I construct the list in another way.

    ...
    r7' = 0 . 0 1 0 5 1 3 8 ...
    r6' = 0 . 9 9 3 7 8 0 8 ...
    r5' = 0 . 4 1 0 7 0 4 6 ...
    r4' = 0 . 2 3 3 5 1 2 6 ... New list
    r3' = 0 . 8 2 0 5 0 2 6 ...
    r2' = 0 . 4 0 3 2 0 4 3 ...
    r1' = 0 . 1 0 0 1 0 0 1 ...(= Cantor's switching function resultes)
    ----------------------
    r1 = 0 . 0 1 0 5 1 1 0 ...
    r2 = 0 . 4 1 3 2 0 4 3 ...
    r3 = 0 . 8 2 4 5 0 2 6 ...
    r4 = 0 . 2 3 3 0 1 2 6 ... Original list
    r5 = 0 . 4 1 0 7 2 4 6 ...
    r6 = 0 . 9 9 3 7 8 3 8 ...
    r7 = 0 . 0 1 0 5 1 3 0 ...
    ...

    By constructing the above list I show that there are infinitely countably many r' numbers that are not covered by Cantor's switching function.

    Therefore Cantor's digitalization's second argument doesn't hold.


    Please someone show my mistake.


    Thank you.


    Organic
     
  2. jcsd
  3. Oct 19, 2003 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Uh, that you didn't understand Cantor's argument?

    In the first, place, it is not an "assumption" that "we have a bijection between |N| and |R| iff R list is complete." Since N is countable, any bijection must be a complete list. It is incorrect to say (as you may be) that Cantor is saying that there is no bijection because that particular list is not complete- the list was arbitrary. What Cantor showed was that ANY list must be incomplete.

    What do you mean "not covered by Cantor's switching function"?

    You appear to have constructed the same list except that you have replace the "diagonal" digit by something that is neither the original digit nor Cantor's new digit. What is your point? There is no reason to believe you HAVE a "new" list. It is quite possible that the numbers you have in the new list were already somewhere in the old list- you don't know. An important point about going specifically down the "diagonal" in Cantor's proof is showing the the resulting new number CAN'T be in the list anywhere- because it differs from the nth number in the nth digit.

    In any case, Cantor did NOT say "if the number is not 1, replace it by 1, if it is 1 replace it by 0". He only needs to set up some regular scheme for replacing each digit by some other digit in a clear way. In fact, what that shows is that, given any list, not only does there exist A number not on the list, but in fact, there exist an infinite number of real numbers not on the list.
     
  4. Oct 19, 2003 #3
    Hi HallsofIvy,


    By complete I mean that there are no numbers left out not in R and not in N (means bijection between N and R).

    The R list is arbitrary and it is one and only one list.
    "New list" and "Original list" are the same one list.

    All what I showed is that we can construct it in such a way that Cantor's function can never reach all of it.

    Here it is again:
    ...
    r7' = 0 . 0 1 0 5 1 3 8 ...
    r6' = 0 . 9 9 3 7 8 0 8 ...
    r5' = 0 . 4 1 0 7 0 4 6 ...
    r4' = 0 . 2 3 3 5 1 2 6 ... "New list"
    r3' = 0 . 8 2 0 5 0 2 6 ...
    r2' = 0 . 4 0 3 2 0 4 3 ...
    r1' = 0 . 1 0 0 1 0 0 1 ...(= Cantor's function resultes)
    ----------------------
    r1 = 0 . 0 1 0 5 1 1 0 ...
    r2 = 0 . 4 1 3 2 0 4 3 ...
    r3 = 0 . 8 2 4 5 0 2 6 ...
    r4 = 0 . 2 3 3 0 1 2 6 ... "Original list"
    r5 = 0 . 4 1 0 7 2 4 6 ...
    r6 = 0 . 9 9 3 7 8 3 8 ...
    r7 = 0 . 0 1 0 5 1 3 0 ...
    ...

    You Wrote:
    Then I use r'', r''' ,r'''' ,... on top of your list.


    Organic
     
    Last edited: Oct 19, 2003
  5. Oct 19, 2003 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And the diagonal argument applies to each of those as well.
     
  6. Oct 19, 2003 #5
    Hi Hyrkyl,

    As I see I it, we Don't need r'' ,r''' , r'''' ,... and so on.

    r' is enough to show that Coator's argument can't work, if we construct the list as I did.

    There are always countably many numbers that Cantor's function does not reach.

    More than that, because it is an arbitrery list, there is no first number in the list, and this is how I constructed it.

    It always goes to infinity in both directions but only a part of it is in the the range of Contor's function:
    ...
    r7' = 0 . 0 1 0 5 1 3 8 ...
    r6' = 0 . 9 9 3 7 8 0 8 ...
    r5' = 0 . 4 1 0 7 0 4 6 ...
    r4' = 0 . 2 3 3 5 1 2 6 ... "Out of Contor's function range"
    r3' = 0 . 8 2 0 5 0 2 6 ...
    r2' = 0 . 4 0 3 2 0 4 3 ...
    r1' = 0 . 1 0 0 1 0 0 1 ...(= Cantor's function resultes)
    r1 = 0 . 0 1 0 5 1 1 0 ...
    r2 = 0 . 4 1 3 2 0 4 3 ...
    r3 = 0 . 8 2 4 5 0 2 6 ...
    r4 = 0 . 2 3 3 0 1 2 6 ... "In range"
    r5 = 0 . 4 1 0 7 2 4 6 ...
    r6 = 0 . 9 9 3 7 8 3 8 ...
    r7 = 0 . 0 1 0 5 1 3 0 ...
    ...



    Please show me what mathematical logic forces me to define the first row to the checked list ?




    (Dear Hurkyl please close or delete the other thread with the wrong name "digitalization" instead of "diagonalization", thank you)

    Organic
     
    Last edited: Oct 19, 2003
  7. Oct 19, 2003 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    See step (2) in the proof you wrote in the original post:


    This is a key step to the diagonal argument that you are neglecting.

    You have a (countable) list, r' of decimals in the interval (0, 1). Your list may be enumerated as a sequence {s1, s2, s3, ...}, and the sequence s has exactly the same elements as r' does. Steps (3)-(5) prove the existance of a decimal, x, in (0, 1) that is not in the enumeration s, thus x must also not be in r'.

    (a previous post gives an example of such a sequence s)


    No matter how much effort you make in creating (countable) lists structured in complicated ways trying to circumvent this proof, step (2) always allows the list to be rewritten as a sequence and the proof holds.
     
  8. Oct 19, 2003 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    In other words, you don't understand the word "countable", you don't understand the word "list", and you don't understand Cantor's proof.
     
  9. Oct 20, 2003 #8
    Thank you Hurkyl and HallsofIvy,

    Cantor's proof holds because one and only one reason.

    It compares between a list of numbers that have finite number of digits or infinitely many digits (with repetitions over scale, therefore they are Q numbers), and a list of numbers with infinitely many digits without repetitions over scales (irrational numbers).

    If we take a list of all Q numbers with infinitely many digits and use Cantor's function, can we clearly show that we always get as a result an irrational number ?

    Thank you.


    Organic
     
    Last edited: Oct 20, 2003
  10. Oct 20, 2003 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member


    The (second) diagonalization argument has nothing to do with rational and irrational numbers.


    If we take a list of all rational numbers and we use the diagonal argument to prove the existance of a real number not on that list, then of course that number has to be irrational.
     
  11. Oct 20, 2003 #10
    Hi Hurkyl,

    Thank you for your reply.

    My question is: can we prove that the new number can never be a rational number ?

    I mean no repetitions over scales.


    I can construct a list of infinitely many rational numbers and than I can show that there is a new rational numbet, which is not in the list.

    For example:

    0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
    0 . 3 0 2 3 0 2 3 0 2 3 0 2 ...
    0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
    0 . 5 5 9 0 6 5 5 9 0 6 5 5 ...
    0 . 7 8 1 1 1 7 8 1 1 1 7 8 ...
    0 . 7 4 3 3 3 0 7 4 3 3 3 0 ...
    0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
    0 . 1 2 3 0 1 2 3 0 1 2 3 0 ...
    0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
    0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
    0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
    0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
    ...
    ...
    ...

    In this case x = 0.010101010101... , which is a new rational number not in the list of infinitely many rational numbers.

    Therefore (by Cantor's first and second agruments) there are more rational numbers than rational numbers.

    If we add this number to the list, we can rearenge the list in such a way that define a new rational number not in the list, and so on and so on.


    Can you prove that the number of rearengments is finite ?



    Thank you.




    Organic
     
    Last edited: Oct 20, 2003
  12. Oct 20, 2003 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How does that follow?

    Are you assuming that the list you provided contains every rational number? Why would you think that?

    Cantor's first diagonal argument constructs a specific list of the rational numbers that is not the list you provided.
     
  13. Oct 21, 2003 #12
    Hi Hurkyl,

    My list is a decimal representation of any rational number in Cantor's first argument spesific list.

    For example:

    0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
    1 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
    0 . 5 5 9 0 6 5 5 9 0 6 5 5 ...
    0 . 7 8 1 1 1 7 8 1 1 1 7 8 ...
    2 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
    3 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
    0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
    0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
    0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
    ...
    ...
    ...

    Every non-zero decimal digit can be any number between 1 to 9.



    Organic
     
    Last edited: Oct 21, 2003
  14. Oct 21, 2003 #13

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, it proves that there are more rational numbers than were on your list. I can play that game too: 1, 2, 3, 4, ..., the list of all natural numbers, is a list of rational numbers. The number 1/2 is not on it! That proves nothing at all.

    The point of Cantor's argument was to say "suppose we have a list of all real numbers" and then show that that leads to a contradiction.

    If you are going to try to do the same thing with rational numbers- assume a list of all rational numbers and then construct a rational number that is not on it, the onus is on you to show that that number IS rational.

    This makes no sense at all. You haven't given a list, you give a few numbers, (not well defined, in fact it is not even clear that the numbers on the list ARE rational numbers) and no general formula for putting numbers on the list.
     
  15. Oct 21, 2003 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Really?

    Where does 1/3 appear in your list? What about 4/7? How about 10/99?

    (If you only answer one of these questions, do it for 10/99)
     
  16. Oct 21, 2003 #15
    Hi Hurkyl ,Hi HallsofIvy,


    The main idea of Cnator's second argument is to show that the real numbers list can never be a complete list.

    If we have to correct the list by adding to it infinitely many Cantor's function results, it means that there can never be a bijection between |R| and |N|.

    Cantor's first argument clearly shows that there is a bijection between |N| and |Q|.

    There is no problem to represent any rational number by its decimal form.

    And Q numbers decimal's form is finite or it is infinitely many digits with repetitions over scales.

    But when we use Cantor's second argument on the decimal representations of Q numbers, we find exactly the same results as Cantor found between |N| and |R|.

    |N|=|Q| by Cantor's first argument, but |N|<|Q| by Cantor's second argument.

    My list is a decimal representation of any rational number in Cantor's first argument specific list.

    For example:

    0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
    1 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
    0 . 5 5 9 0 6 5 5 9 0 6 5 5 ...
    0 . 3 3 3 3 3 3 3 3 3 3 3 3 ...
    2 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
    3 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
    0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
    0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
    0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
    ...
    ...
    ...

    Hurkyl, every non-zero decimal digit can be any number between 1 to 9, Because I use Cantor's function where the rules are:

    A) Every 0 in the original diagonal number is turned to 1 in Cantor's new number.

    B) Every non-zero in the original diagonal number is turned to 0 in Cantor's new number.

    So, there is no problem to use 0.333333... in the list because 3 (or any digit between 1 to 9) is always turned to 0, therefore our new number can always be a rational number.


    Organic
     
    Last edited: Oct 21, 2003
  17. Oct 21, 2003 #16

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    You miss understand the argument, what Cantor showed is that given any list of any size natural numbers vs irrational numbers between 1 and 0 it is always possible to prove that there are irrational numebsr not contained on the list, the reverse is not true however.
     
  18. Oct 21, 2003 #17
    Hi jcsd,

    please go one post back form your first post in this thread, and please answer to my agrument about |N| and |Q|.

    Thank you.


    Organic
     
  19. Oct 21, 2003 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There is no bijection between |N| and |R| because every function from |N| to |R| is missing at least one real number.


    Your use of the phrase "can never" seems to imply you think that, in the mathematical sense, something might not exist now but it could exist in the future. That is an incorrect interpretation of mathematics. A mathematical statement that is true now will be true 100 years from now and was true 1000 years ago; all that changes is what we've discovered.


    So tell me, where does 10/99 appear in your list?
     
  20. Oct 22, 2003 #19
    Hi Hurkyl,

    you wrote:
    Well, I think it is depended on your point of view, which in this case is Platonism, which says that mathematics only discover timeless objective truth.

    Let us say that I take this point of view, so I can easily change what I wrote to fit it to the Platonism point of view.

    Here it is (and also added 10/99 to my list):

    The main idea of Cnator's second argument is to show that the real numbers list can never be a complete list.

    If we have to correct the list by adding to it infinitely many Cantor's function results, it means that there is no bijection between |R| and |N|.

    Cantor's first argument clearly shows that there is a bijection between |N| and |Q|.

    There is no problem to represent any rational number by its decimal form.

    And Q numbers decimal's form is finite or it is infinitely many digits with repetitions over scales.

    But when we use Cantor's second argument on the decimal representations of Q numbers, we find exactly the same results as Cantor found between |N| and |R|.

    |N|=|Q| by Cantor's first argument, but |N|<|Q| by Cantor's second argument.

    My list is a decimal representation of any rational number in Cantor's first argument specific list.

    For example:

    0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
    1 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
    0 . 1 0 1 0 1 0 1 0 1 0 1 0 ...
    0 . 3 3 3 3 3 3 3 3 3 3 3 3 ...
    2 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
    3 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
    0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
    0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
    0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
    0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
    ...
    ...
    ...

    In this case Cantor's function result is 0.0101010101010101.... which is not in the list.

    Every non-zero decimal digit can be any number between 1 to 9, Because I use Cantor's function where the rules are:

    A) Every 0 in the original diagonal number is turned to 1 in Cantor's new number.

    B) Every non-zero in the original diagonal number is turned to 0 in Cantor's new number.

    For example, there is no problem to use 0.333333... in the list because 3 (or any digit between 1 to 9) is always turned to 0, therefore our new number can always be a rational number.


    Organic


    Last edited by Organic on 10-21
     
    Last edited: Oct 22, 2003
  21. Oct 22, 2003 #20

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You keep claiming "therefore our new number can always be a rational number" but you have given no proof of that. HOW can you prove that the new number WILL (not can) always be a rational number? Each digit of the new number is dependent upon the corresponding digit of a DIFFERENT rational number. HOW do you prove that those digits will either eventually be all zeroes or eventually repeat? That seems very unlikely to me.

    For example, if the list of rational numbers between 0 and 1 starts (this is based on the standard listing used in the proof that rational numbers are countable):
    0.50000...
    0.33333...
    0.66666...
    0.25000...
    0.50000...
    0.75000...
    0.40000...
    0.16666...
    0.60000...
    etc.

    then your function (set the digit to 1 if the original digit is 0, otherwise to 0) gives 0.000111101 etc. I see no evidence that this will eventually repeat. Since you are claiming that it will, it your responsibility to prove that.

    By the way, please do not start getting "mystical" and appealing to different philosophies of mathematics. One's philosophy of mathematics has no bearing on how one proves theorems (with the possible exception of those weird "Brouwer-Constructionists!). I am certainly not a "Platonist" but I understood Hurkyl's statements completely.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A question on Cantor's second diagonalization argument
Loading...