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 digitalization argument.

  1. Oct 19, 2003 #1
    A question on Cantor's second diagonalization argument.

    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
     
    Last edited: Oct 19, 2003
  2. jcsd
  3. Oct 19, 2003 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Let's write down an enumeration of your list:

    Code (Text):

    r1  = 0.0105110...
    r1' = 0.1001001...
    r2  = 0.4132043...
    r2' = 0.4032043...
    r3  = 0.8245026...
    r3' = 0.8205026...
    ...
     
    Then, just like any other enumeration, you apply Cantor's diagonal argument and you can generate a number that cannot appear in the list. In this case, 0.110010...
     
  4. Oct 19, 2003 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    It doesn't help to post the same question twice.
     
  5. Oct 19, 2003 #4
    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
     
  6. Oct 19, 2003 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Last edited: Oct 19, 2003
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 digitalization argument.
Loading...