Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 18 Jun 2010 04:20 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m63n.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> I made no premise. > > Sure you did: you assumed that no list of computable numbers can > exist. You also assumed an incorrect definition of "computable". > No, I assumed that a list of all computable numbers can exist. Then I gave a simple algorithm which forms a computable number which is not on the list. I therefore proved that no list of all computable numbers can exist. It is *exactly* the same as Cantor's proof that the Reals cannot be listed. It is of interest because it is known that the computable numbers are countable. Therefore the property "cannot be listed" is *not* the same as the property "is uncountable". Cantor's diagonal proof does *not* show the Reals are uncountable; it just proves the much weaker statement that "the Reals cannot be listed". > > - Tim
From: Peter Webb on 18 Jun 2010 04:26 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m68o.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Because Cantor's proof requires an explicit listing. This is a very >> central concept. > > Cantor's proof works on any list, explicit or not. > Really? How do you apply Cantor's proof to a list constructed as follows: "Define a list L such that the n'th entry on the list consists of all 1's if the n'th digit of Omega is 1, otherwise it is all 0's." (Your example). > The rest of your misconception snipped. > > > - Tim Perhaps if you could point out to me why you believe Cantor's proof that not all Reals can be listed (as it appears you do) but you don't believe my proof that not all computable Reals can be listed. They appear identical to me.
From: Tim Little on 18 Jun 2010 04:47 On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Of course this number is computable; there > is a simple algorithm to compute it. I see you still haven't consulted a definition of "computable number". No worries, let me know when you have. - Tim
From: Peter Webb on 18 Jun 2010 07:09 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1mcki.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Of course this number is computable; there >> is a simple algorithm to compute it. > > I see you still haven't consulted a definition of "computable number". Umm, yes I have. > No worries, let me know when you have. > > > - Tim There can be no list of all computable numbers. The proof is quite simple. Lets imagine that you have such a list of all computable numbers. Lets say it starts off ... ..111111... ..141592 ... ..71828 ... Take the 1st digit of the first number. If it is a "1", then make the first digit of the diagonal number "2", otherwise make it a "1". Well, the first digit of the first number is a "1", so the first digit of the diagonal number is a "2". Now take the second digit of the second number and do the same substitution. Its a "4", so the second digit of the diagonal number is "1". Now take the 3rd digit of the 3rd number ... its a "8", so the third digit of the diagonal number is a "1". Continue in this fashion. The number that is produced is clearly "computable", because we have computed it. Its also clearly not on the list. Therefore the list cannot have contained all computable numbers. Exactly the same as Cantor's proof that the Reals cannot be listed. However, this does *not* mean that there are an uncountable number of them. The computable numbers are countable. And similarly Cantor's proof does not show that there are an uncountable number of Reals. It proves exactly what Cantor claimed it did, which is that you cannot list all Reals.
From: Jesse F. Hughes on 18 Jun 2010 08:17
Newberry <newberryxy(a)gmail.com> writes: > 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? > Because every infinite sequence of digits represents a real number? And the antidiagonal is one such sequence? -- Jesse F. Hughes "Yesterday was Judgment Day. How'd you do?" -- The Flatlanders |