Re: Cantor's wrong! (doubt it)

From: Mike Terry (news.dead.person.stones_at_darjeeling.plus.com)
Date: 06/20/04 

Date: Sun, 20 Jun 2004 20:54:54 +0100

"Russell Easterly" <logiclab@comcast.net> wrote in message
news:9vKdneeLTcsaVUjdRVn-uw@comcast.com...
>
> "Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in
message
> news:2jjk04F12j25hU1@uni-berlin.de...
> > "Russell Easterly" <logiclab@comcast.net> wrote in message
> > news:25KdnWyv0s2i5U_dRVn-gQ@comcast.com...
>
> > Here is what I think you really meant to say:
> >
> > Definition: a natural number is "oney" if it's decimal representation
> > consists entirely of a string of 1s.
> >
> > (e.g. 1, 1111, 111111 etc. are oney numbers)
> >
> > Definition: given the sequence {N_i}, we will construct a new *sequence*
> > {x_i} as follows:
> >
> > x_i = (smallest oney number which is greater than every oney number
> > appearing in the set {N_j: j<=i})
> >
> > (e.g. if N_i is the sequence 7, 2, 111, 5, 1111, ...
> > then x_i is the sequence 1, 1, 1111, 1111, 11111, ...)
> >
> > This is the construction you were getting at, right?
>
> Right.
>
> > This is a properly defined sequence {x_j}, and we can show it is
> > monotonically increasing. For each natural number j, you have derived a
> new
> > natural number x_j. Note you have not produced a number x_oo which is
> > "right at the end of the list", as the list has no end...
> >
> > Now, depending on the original sequence {N_i}, the corresponding
sequence
> > {x_i} may converge to a final value (x), or may be unbounded in which
case
> > there is no final (x) to which it converges.
>
> "Converges" is not the right word. Let's just say that the list, x,
contains
> a
> natural number that is not in list N.

But this is simply not true for all starting lists N. For example, if {N_i}
is the sequence {1, 11, 111, 1111, 11111, ...} then your corresponding
values of x_i match up like this:

i N_i x_i
--- ------ -------
1 1 11
2 11 111
3 111 1111
4 1111 11111
5 11111 111111
6 111111 1111111
....

Note that there is no value of x_i that does not appear somewhere in the
list {N_i}, so your method has failed to produce a value x missing from the
list.

(Unless I misunderstand how you want to turn the sequence x_i = {11, 111,
1111, 11111, ... } into a single "missing number x")

However, you're quite right in that the focus is not on "boundedness" or
"convergence", but simply on how the sequence {x_i} produces the missing
number x. This is the key step missing from your proof.

>
> > So where do you want to go now? You seem to be suggesting that the
> sequence
> > {x_i} always converges to a number x, which is not in the original
> sequence
> > {N_i}. Well, sure, if {x_i} does converge to a number x, then x is
> missing
> > from the original list. BUT what if your {x_i} is unbounded?
>
> My point is that these same objections can be applied to Cantor's diagonal
> argument.

No, the situation is quite different and the same objection fails when
applied to Cantor's argument - see below...

>
> For example, let's use the following rule to create our diagonal number:
> Let N be a list of real numbers and let x_i be ith digit of the diagonal
> number.
>
> If digit i of N_i = 1 then x_i = 2 else x_i = 1.
> Let N be the following list of real numbers:
>
> .000...
> .1000...
> .11000...
> .111000.
> .1111000...
> ...

OK, let's look at this scenario more closely. On the right, I've added the
value of x_i corresponding to each N_i, and the contribution it makes to the
final x which is produced by Cantor's argument:

i N_i x_i contribution to final "missing" x
----- ------------ ----- ---------------------------
1 .000... 1 0.1
2 .1000... 1 0.01
3 .11000... 1 0.001
4 .111000... 1 0.0001
5 .1111000... 1 0.00001
...

so Cantor's missing number is x=0.11111... (= 1/9 assuming above pattern
continues)

Note that Cantor's argument has ultimately identified a *single number*
x=0.11111... which is missing from the list. (The sequence {x_i} is only
useful in that it leads to the unique identification of the missing number
x).

> x_i is "unbounded" and x never "converges" to a real number not in N.

This is where you've misunderstood. (forget the "converges" and "unbounded"
tests and just concentrate on how/whether the list {x_i} identifies the
missing number!)

Just to be clear up front, there *is* a similarity between the situation
here, and with your Natural number list method above:

* in both situations we have a sequence (list) {N_i}, for which we are
   trying to identify a missing number

* in both situations we have properly defined a "derived sequence" {x_i}

HOWEVER, in your situation, the sequence {x_i} does not necessarily lead to
the identification of any number that is not in the original list {N_i}.
(Sorry, it just doesn't! E.g. see my earlier example for the list {11, 111,
1111, 11111, ... })

In the situation in Cantor's proof the sequence {x_i} DOES (always) uniquely
identify a missing number in the list. E.g. in the example sequence you
gave above, the sequence {x_i} is {1, 1, 1, 1, 1, ...} and this can be used
as the digits of a SINGLE number x = 0.1111111...

Assuming your pattern of the sequence {N_i} continues in the obvious
fashion, the number x identified by Cantor's argument is
0.1111...(recurring) = 1/9. Now, you can't deny that 1/9 is a real number
between 0 and 1, and it's also clear that 1/9 is missing from your list
{N_i}, so everything's working correctly here.

In fact it should be clear that whatever list {N_i} you start with, the
sequence {x_i} will uniquely identify a real number between 0 and 1, via
it's decimal expansion...

> My problem with the diagonal argument is that it requires an infinite
> number of computations. There was a thread some time ago where
> we proved that the Halting problem is solvable if we allow a
> computer to perform an infinite number of calculations in finite time.
> The diagonal argument requires such a computer.

Cantor's proof is not a "computation". It is a mathematical proof. In
essence, it *defines* a function F that maps the set of "lists of real
numbers between 0 and 1" onto the set [0,1], such that for each list {N_i},
F({N_i}) is not in {N_i}.

Of course if you start talking about "computations" then in general you
should not be surprised if computation times involving real numbers are
infinite, since real numbers have infinite precision. E.g. to compute Pi
would require infinite time, but this does not mean Pi does not exist.
There are even real numbers that cannot be computed (on a Turing machine),
and this too does not mean they do not exist. :)

I don't see how looking at these computation times invalidates Cantor's
proof.

> Here is another example:
> Consider a set of sets of natural numbers written in unary.
>
> Unary numbering system:
> One = 1
> Two = 11
> Three = 111
> etc.
>
> Sets of unary numbers:
> N_1 = {1}
> N_2 = {1,11}
> N_3 = {1,11,111}
> etc.
>
> Notice that each of these sets contains a member whose length
> is equal to the cardinality of the set. For example:
>
> length of 1 = cardinality of N_1
> length of 11 = cardinality of N_2
> length of 111 = cardinality of N_3
>
> Now consider a N that contains every natural number in unary.
> Does this N contain a member whose length is equal to the cardinality of
N?

No. The cardinality of N is (countably) infinite, while the length of every
member of N is finite. (I'm not sure why you raise this example.)

Regards,
Mike.

Relevant Pages

  • Re: abundance of irrationals!)
    ... No such "sum" exists except as, and only as, the limit of the infinite ... If an infinite sequence does not have to "achieve" its limit, ... > It is only for lists not initially known not to be surjective that ...
    (sci.math)
  • Re: infinity
    ... from that two different infinite expansions in the same base can ... infinite lists are easily constructible in design ... only one sequence with all zeros, and only one sequence with all ones. ... For having one or more zeros with one or more ones there are infinitely ...
    (sci.math)
  • Re: In a Bad Mood
    ... >> the same digit can occur). ... > There is no unique sequence of digits to anti_diag. ... does the infinite list map to the entire number line? ... but the LISTS INFINITE FORM is required to ...
    (sci.logic)
  • Re: limitation to induction on finite bounds
    ... >told the infinite form of the set you break down. ... given your above non-standard "fairy maths" rule about infinite lists of ... sequences, here's another go at showing that the infinite sequence .333... ... let every member of the infinite list be an *infinite* sequence: ...
    (sci.logic)
  • Re: limitation to induction on finite bounds
    ... >told the infinite form of the set you break down. ... given your above non-standard "fairy maths" rule about infinite lists of ... sequences, here's another go at showing that the infinite sequence .333... ... let every member of the infinite list be an *infinite* sequence: ...
    (sci.math)