Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Tim Little on 18 Jun 2010 01:49 On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Cantor's proof does *not* demonstrate that Reals are uncountable, it > just proves there can be no explicit enumeration of them. It proves that there is no enumeration of them, explicit or not. I have no idea where you are getting this strange notion of "explicitness". - Tim
From: Tim Little on 18 Jun 2010 01:59 On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message >> Cantor's construction applied directly to lists of computable numbers >> shows almost nothing. Given any list of computable reals, you can >> produce an antidiagonal real not on the list. Unfortunately the >> construction says nothing about whether the antidiagonal is computable >> or not. > > Of course its computable. It is a trivial programming exercise to form a > computable number not on the list, by simply doing digit substitutions. Only if the list itself is a computable function. Cantor's proof does not depend on any such assumption. > Cantor's proof provides an explicit and simple algorithm to form > such a number, and it is extremely easy to compute. If there exists no algorithm for computing the original list, how do you propose to use Cantor's proof to make an algorithm for the antidiagonal of that list? >> It takes quite a bit of extra work (not part of Cantor's proof) to >> deduce that there is no computable list of all computable reals. > > Cantor's proof applied to computable numbers proves it immediately and > simply. First you have to define the notion of "computable list", and set up the theorems proving properties about how computable lists and computable numbers relate. >> I agree. It was Herc's deranged ramblings that brought computability >> into this discussion in the first place, when they really are >> completely irrelevant to Cantor's proof. >> > > Well, they are relevant if you try and make the mental jump from > "cannot be listed" to "are therefore uncountable". This simply does > not follow. It follows immediately from the definitions. You appear to have some bizarre definition of "list" that Cantor never used, employing concepts not developed until many decades later. > The computable Reals cannot be listed either, but they are > definitely countable. The computable reals can be listed and are countable. > A Cantor construction applied to a purported list of all computable > Reals will identify a computable Real not on the list. No, it will not. > The diagonal is explicitly constructible given the list. The definition of computable number does not include any presupposition of being supplied with infinite lists of infinite digit sequences. To be computable, a number must be constructible by a finite algorithm *without* being given the list. Don't take my word for it, look up the definition yourself. - Tim
From: Tim Little on 18 Jun 2010 02:02 On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > The diagoinal number is clearly computable. There is a very simple algorithm > for generating it, and this algorithm is easily implemented in a Turing > Machine. Only if you presuppose that the list is initially encoded on the tape of the Turing Machine. No such proviso is made in the definition of computable number: it must start from a blank tape. The rest of your post is based on your false premise and so snipped. - Tim
From: Newberry on 18 Jun 2010 02:07 On Jun 15, 9:46 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > WM says... > > > > >On 15 Jun., 16:32, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > >> The proof does not make use of any property of infinite lists. > >> The proof establishes: (If r_n is the list of reals, and > >> d is the antidiagonal) > > >> forall n, d is not equal to r_n > > >As every n is finite, it belongs to a finite initial segment of the > >infinite list. > > I'm not sure what you are saying. The fact is, we can prove > that for every real r_n on the list, d is not equal to r_n. > That means that d is not on the list. How do you know that it does not prove that an anti-diagonal does exist i.e. that an antidiagonal is a contradiction in terms?
From: Peter Webb on 18 Jun 2010 02:17
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m1tk.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> There are a countable number of computable Reals. > > Correct. > >> You can apply the Cantor construction to any purported list of all >> computable Reals to form a computable Real not on the list. > > No, you can apply the Cantor construction to any purported list of all > computable Reals to form a *non*computable Real not on the list. > Wrong. Cantor's diagonal construction explicitly forms a Real not on that list, and the Cantorm diagonal number is obviously constructibe if every item in the list is constructible. Cantor provides a very simple, explicit algorithm for constructing the diagonal number. > >> This proves that the computable Reals cannot be listed. > > It proves no such thing. Well, that is what Cantor's proof exactly shows. It shows that if there was a list of all Reals, we can produce a Real not on the list, so the Reals cannot be listable. > > >> It does *not* prove the computable Reals are uncountable, and in >> fact they are not. > > Of course the computable reals are countable. I never claimed > otherwise. You are the one claiming that they cannot be listed, a > statement equivalent to their uncountability. No, they are not the same. If you believe that you have a list of all computable Reals, I can use a diagonal argument to explicitly construct a Real not on the list. This number is obviously computable; Cantor provides an explicit algorithm for constructing it, which can be implemented in a few lines of code or in a TM. > > >> In exactly the same manner, Cantor proved that the Reals cannot be >> listed. This does *not* automatically mean they are uncountable, >> any more than the same proof applied to computable Reals proves they >> are uncountable. These are different concepts. (Although they were >> not when Cantor produced his proof). > > Computability as a concept did not even exist when Cantor produced his > proof. Correct. > You are extremely confused. > No. You seem to think that the computable Reals can be listed. They can't. Given a list of computable numbers, we can compute (explicitly construct) the diagonal number, and prove its not on the list. But yet they are countable. Cantor did not prove that the Reals are uncountable using his diagonal proof, and as far as I am aware he didn't claim that it did. Computable numbers can't be listed either, and they are countable. These are different concepts which you (incorrectly) seem to think are the same thing. > > - Tim |