Re: Cantor


Pedro wrote:
> I think I'm getting sidetracked by giving poor examples. Can't see the
> forest for the trees, and all that... Let me ask it one more way, if I may.
>
> It's obviously impossible to actually present a "complete" list of reals
> prior to initiating the diagonalization method as the list is infinitely
> long. Rather, the diagonalization method is a thought experiment that says,
> in effect, "no matter how complete one makes the list, one can use this
> typographical method to find with certainty a number not on the list".
>
> But I can make the same conceptual argument about the natural numbers (or
> non-negative integers, if you prefer). In my example below, SSSS0 differs in
> the first position from 0, differs in the second position from S0, etc...,
> thereby giving a number that differs from all others on the list and
> demonstrating an absurdity: that the natural numbers are not enumerable.
> (The only new assumption / constraint I've placed on this example is that
> the list be ordered. That doesn't seem to be an unreasonable thing to do
> with the natural numbers.)
>
> So I'm obviously missing something fundamental about the whole
> diagonalization thing. Any idea what it is?

This point is made below by James Dolan. I'm just putting in
my two cents worth.

In the "diagonalization" proof that [0,1] is uncountable, the
form of the proof is:

1. Let f:N->[0,1] be any mapping from N to [0,1].
2. There exists x in [0,1] such that x does not equal
f(n) for any n in N.

The construction of x in step 2 relies on a theorem that
any string of digits 0.ssssss... represents an x in [0,1].

Remember, the purpose of the construction is not to produce
a sequence, but to generate a single value x which, by the
construction, is not mapped by any f(n). This number x has
the property that its n-th digit differs from the n-th digit
of f(n).

So the corresponding proof in the natural numbers should be
trying to construct a corresponding m in N. But you do not
have the corresponding theorem that any (possibly infinite)
sequence of digits represents a natural number. Therefore
the construction can not be guaranteed to produce such a
number.

- Randy

.

Relevant Pages

  • Re: Cantor
    ... |I think I'm getting sidetracked by giving poor examples. ... |reals prior to initiating the diagonalization method as the list is ... |differs in the first position from 0, ... what all of the other digits are doing, because of the nature of real ...
    (sci.math)
  • Re: A simple question about integers
    ... (This is a standard construction, ... > sequence of digits we even cannnot define a greater/smaller ... considered as infinite decimal expansions (or expansions ...
    (sci.math)
  • Re: November 25 is Infinite Clause day!!
    ... infinite length are computable the conclusion of Cantor's proof relies ... on the existence of a new sequence of digits which is clearly non ... your construction can never be realised. ... places in the sequence are all covered. ...
    (sci.math)
  • Re: Ultimate debunking of Cantors Theory
    ... as a result of the construction. ... the Cantor construction fails in base 2. ... if one pairs off digits starting from the binary ... 1's while every list entry is a finite sequence of 1's. ...
    (sci.math)
  • Re: The complete infinite binary tree has only countably many infinite paths.
    ... part of the binary tree that contains 0.111... ... has not been used for construction. ... number that differs from every line of the list. ... Of course the last line is not subject to diagonalization, ...
    (sci.logic)