|
|
Re: Why can no one in sci.math understand my simple point?
Posted:
Jun 21, 2010 7:18 PM
|
|
"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message
news:4c1eb265$0$11181$afc38c87@news.optusnet.com.au...
>
> "Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in
message
> news:a_mdnZe4xaoOxIPRnZ2dnUVZ8umdnZ2d@brightview.co.uk...
> > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message
> > news:4c1d86f0$0$18229$afc38c87@news.optusnet.com.au...
> >>
> >> "Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in
> > message
> >> news:NNqdnTtg2LuExoDRnZ2dnUVZ8lKdnZ2d@brightview.co.uk...
> >> > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message
> >> > news:4c1c6be3$0$17177$afc38c87@news.optusnet.com.au...
> >> >>
> >> >> "Tim Little" <tim@little-possums.net> wrote in message
> >> >> news:slrni1om15.jrj.tim@soprano.little-possums.net...
> >> >> > On 2010-06-19, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au>
> > wrote:
> >> >> >> So Cantor's proof when applied to computable Reals proves exactly
> >> >> >> what in your opinion?
> >> >> >
> >> >> > That there is a real not on the list.
> >> >> >
> >> >> >
> >> >> >> I might remind you that as the form of proof is identical to that
> >> >> >> used by Cantor for all Reals, whatever you believe that Cantor's
> >> >> >> proof applied to computable Reals proves, his proof applied to
all
> >> >> >> Reals must prove the same thing.
> >> >> >
> >> >> > It does prove exactly the same thing: in both cases, all such
lists
> >> >> > omit at least one real.
> >> >> >
> >> >> >
> >> >> >> Its the same proof, after all, except limitting the set to just
> >> >> >> computable Reals.
> >> >> >
> >> >> > No, there is a slight difference: the antidiagonal is a real
number.
> >> >> > It does not necessarily produce a computable real number.
> >> >> >
> >> >>
> >> >> Of course it is computable. Cantor provides a simple construction
for
> > the
> >> >> number.
> >> >
> >> > No, you're misunderstanding the meaning of computable.
> >> >
> >> > Hopefully you will be OK with the following definition:
> >> >
> >> > A real number r is computable if there is a TM (Turing machine)
> >> > T which given n as input, will produce as output
> >> > the n'th digit of r.
> >> >
> >> > So let us suppose there is a list L (not a "computable list", just a
> >> > "list")
> >> > of computable numbers in [0,1], covering all computerable numbers.
> >> >
> >> > [You have your own strange definition of "list", but I am using the
> >> > term
> >> > with it's standard mathematical meaning: L is just a function
mapping
> >> > N
> >> > (natural numbers) to CR (computable reals). Perhaps we should also
> > insist
> >> > that lists are injections (no duplicates) - that's fine. YOU seem to
> > want
> >> > to define "list" to only include "computable" functions from N to CR,
> > but
> >> > that is NOT what everybody else (including Cantor) means by "list"!]
> >> >
> >> > L : N --> CR
> >> >
> >> > so we have the sequence (=list) of computable reals:
> >> >
> >> > ( L(0),
> >> > L(1),
> >> > L(2),
> >> > ....)
> >> >
> >> > Each computable real has it's digital representation, so this list
can
> > be
> >> > written: (using d(m,n) for n'th digit of L(m)
> >> >
> >> > L(0) digits : d(0,0), d(0,1), d(0,2), ...
> >> > L(1) digits : d(1,0), d(1,1), d(1,2), ...
> >> > L(2) digits : d(2,0), d(2,1), d(2,2), ...
> >> > ...
> >> >
> >> > Now, given m and n, is there necessarily a TM that can take m and n
as
> >> > inputs, and ouput d(m,n)?
> >> >
> >> > Well, each L(m) individually is computable: there is a corresponding
> >> > TM,
> >> > TM_m such that given n as input it will compute d(m,n). We could
say:
> >> >
> >> > TM_m (n) = d(m,n)
> >> >
> >> > But all the TMs can be different and completely unrelated to each
> >> > other.
> >> >
> >> > Can we say there will always be a *single* TM TM_ALL_m, which
> >> > "subsumes"
> >> > all
> >> > the TM_n, i.e. if given m and n as input, will compute d(m,n)? I.e.
> >> >
> >> > for all m,n: TM_ALL_m (m,n) = d(m,n) ?????
> >> >
> >> > Unfortunately for your argument, the answer is NO.
> >> >
> >> > But that is exactly what you would need to argue that the
anti-diagonal
> > is
> >> > computable: You need a TM that could calculate d(m,m), but this
needs
> > the
> >> > TM TM_ALL_m, and we do not have that!
> >> >
> >> > I know what you want to say at this point! :) You want to say that I
> > have
> >> > "explicitly given you" d(m,n), and I can only do this if d(m,n) is
> >> > computable. (Right?) And you want to tell me that Cantor's diagonal
> >> > proof
> >> > is the same?
> >> >
> >> > Well, this is a misreading of Cantor's proof! Look closely:
> >> >
> >> > Paraphrasing of Cantor's proof:
> >> >
> >> > Given a function L: N --> [0,1], there
> >> > exists r in [0,1], such that
> >> > for all n, r != L(n) [i.e. r is not in the list]
> >> >
> >> > Proof:
> >> > 1) Suppose L: N-->R
> >> > 2) Define LD: (NxN)-->{0,1,2,3,4,5,6,7,8,9}
> >> > such that LD(m,n) = n'th digit of L(m)
> >> > 3) Define RD: N-->R
> >> > such that RD(m) = [...antidiagonal digit m...]
> >> > 4) Then RD determines a real r in [0,1]
> >> > 5) Show for all n, r != L(n) from defn. of r above.
> >> >
> >> > Where in this proof does Cantor require LD(m,n) to be computable?
> > (Answer
> >> > =
> >> > nowhere.)
> >> >
> >> > I think maybe you are thinking it must be computable, due to your
> >> > misleading
> >> > use of the phrase "explicitly given", but actually all Cantor does is
> >> > argue
> >> > that IF a (any) function L (not necessarily computable) EXISTS
mapping
> >> > N
> >> > to
> >> > [0,1], the mere existence of L implies the existence of a
corresponding
> >> > real
> >> > r not in the list L. There is nothing requiring real computer
programs
> > to
> >> > actually compute anything here! It's just a mathematical proof of
> >> > existence
> >> > of something.
> >> >
> >>
> >> What you are writing above is *not* Cantor's diagonal proof as it
appears
> > on
> >> a million websites.
> >
> > Well, I claim that it is at least OBVIOUSLY EQUIVALENT to what Cantor is
> > saying. It's true I didn't go to a web site and cut and paste any
> > "official" text from his original document, but in essence my
> > understanding
> > is:
> >
> > 1. Cantor shows that any map from N to R cannot be "onto" R.
> > 2. That my proof above sketches this out:
> > - Cantor equates real numbers with their digit sequences
> > (This is why I go from L to LD)
> > - Cantor shows the existence of a new digit sequence, via
> > the antidiagonal argument
> > (That is what I do in step (3). RD is my new digit sequence.)
> > - Cantor proves that RD is a new digit sequence
> > - and that consequenctly the corresponding real number
> > is not in the original map L.
> >
> > So I think my proof follows Cantor's pretty closely, although it is my
own
> > notation. Given the amount of effort I put into trying to help you, I'm
> > disappointed you can't get over some minor notationaly differences to
> > follow
> > what I'm saying.
>
> The whole point of what I am doing is to use his original proof in its
> original form.
>
> Introducing new notation is a crank's way of arguing.
>
> Why not look at my proof, which follows Cantor's proof, instead of
changing
> te notation to produce a proof which you claim is equivalent and arguing
> about that different proof, which you claim differs only in notation?
>
OK, I said I'd do that below, so we'll see. I'd not actually seen any
statement from you of the full Cantor proof that you keep referring to.
Still, it's on "millions of websites", so I'm expecting when it finally
comes it will be super precise and thorough, and so really easy for me to
pin down the flaw you're asking for. Especially as my proof above was
already pretty detailed, but that wasn't good enough for you... :)
>
>
> > You've also given no indication of in what way you think
> > my proof differs from Cantors! (Well, that would be OK if my proof was
> > "nothing like" Cantor's but that's clearly not the case as I've just
> > explained, so I'm left mystified by your claim...)
> >
> >>
> >> The whole point of my post was to use Cantor's proof exactly, which
alows
> > me
> >> to demonstrate that Cantor's proof does *not* in of itself prove the
> >> uncounatbility of the Reals.
> >>
> >> Perhaps if you were to tell me where you think the error in my very
> >> simple
> >> proof is, then we would be making progress.
> >
> > Sure I'll do this. To avoid a further "that's not Cantor's proof" claim
> > from you, please quote exactly what proof of Cantor's you want me to
> > comment
> > on.
> >
>
> There can be no list of all Reals.
>
> Imagine such a list of purported Reals exists. Compute the anti-diagonal
> number as follows ... blah blah. This Real is not on the list.
Um... Seriously?
That's your version of Cantor's proof that appears on "millions of websites"
and is your final and most detailed statement of the proof that you're
capable of? You do realise that my own proof said the same but in more
precise terms than you, e.g. not missing out important key steps? (I don't
think you do...)
Still, I said I'd do it so I'll try and work with you.
Also you've missed out a key bit, presumably because it's not important to
you, but it's the bit you're overlooking!
OK, here's Cantor's official proof (according to you, but
I've added a key step which you missed out, and funnily enough it's the bit
you've overlooked.):
Thm: There can be no list of all Reals.
Proof:
1. Imagine such a list of purported Reals exists.
2. Compute the anti-diagonal number as follows ...
blah blah.
[I'm quite happy with the blah blah bit :) ]
[But I'm NOT happy with your use of the verb
"Compute" since it could suggest the formal
maths meaning of "computable function", whereas
in fact we just mean "DEFINE the antidiagonal..."
Still, let's carry on with your word, and just
keep this in mind]
3a. The antiadiagonal corresponds to a REAL NUMBER
Reason: ANY DIGIT SEQUENCE CORRESPONDS TO A
REAL NUMBER.
3b. This Real is not on the list.
Now I do a "change all" from Real to Computable Real to get your alleged
proof:
Thm: There can be no list of all computable Reals.
Proof:
1. Imagine such a list of purported computable Reals exists.
2. Compute the anti-diagonal number as follows ...
blah blah.
[I'm quite happy with the blah blah bit:)]
[But I'm NOT happy with your use of the verb
"Compute" since it could suggest the formal
maths meaning of "computable function", whereas
in fact we just mean "DEFINE the antidiagonal..."
Still, let's carry on with your word, and just
keep this in mind]
3a. The antiadiagonal corresponds to a COMPUTABLE REAL NUMBER
Reason: ANY DIGIT SEQUENCE CORRESPONDS TO A
COMPUTABLE REAL NUMBER.
3b. This computable Real is not on the list.
The wrong step is (3a). (The one missed out from your version of Cantor's
proof.)
It is not true that any digit sequence corresponds to a computable real
number. The antidiagonal is a Real number, since ANY digit sequence
determines a Real number, but if you want to claim it's computable, actual
proof is required for this.
Note also, if we did a "change all" instead from Real to "rational Real" the
proof would break down in exactly the same place. (As others on this thread
have already pointed out.)
Maybe you think you can patch up (3a) and prove the conclusion so the proof
can carry on from there? (In fact, it's obvious you think this from your
posts.) However, already you've failed in your original claim which was
that simply by doing the "change all" Cantor's proof must "automatically"
remain valid, while you can see from above that it does not.
Feel free to try and prove (3a) yourself and complete the proof, but
remember the definition of "computable real" used in (3a) does not allow
algorithms with infinite input data. Anyway, I've done what I said I would
do here which is point out where the "change all" argument goes wrong...
Regards,
Mike.
|
|
